Progress and Obstacles in Distributed Graph Algorithms

Lower Bounds on the Communication of Distributed Graph Algorithms: Progress and Obstacles Rotem Oshman ADGA 2013

Overview: Network Models LOCAL CONGESTED CLIQUE CONGEST / general network ASYNC MESSAGE-PASSING X

Talk Overview I. Lower bound techniques a. CONGEST general networks: reductions from 2- party communication complexity b. Asynchronous message passing: reductions from multi-party communication complexity II. Obstacles on proving lower bounds for the congested clique

Communication Complexity ? ?,? = ? ? ?

Example: DISJOINTNESS DISJ? : ? ? = ? (?) bits needed ? {1, ,?} ? {1, ,?} [Kalyanasundaram and Schnitger, Razborov 92]

Applying 2-Party Communication Complexity Lower Bounds Textbook reduction: Given algorithm ? for solving task ? ? ? Simulate ? Based on ? Based on ? ? bits Solution for ? answer for DISJOINTNESS

Example: Spanning Trees Setting: directed, strongly-connected network Communication by local broadcast with bandwidth ? UIDs 1, ,? Diameter 2 Question: how many rounds to find a rooted spanning tree?

New Problem: PARTITION Inputs: ?,? 1, ,? , with the promise that ? ? = 1, ,? ? ? Goal: Alice outputs ? ?, Bob outputs ? ? such that ?,? partition {1, ,?}.

The PARTITIONProblem Trivial algorithm: Alice sends her input to Bob Alice outputs all tasks in her input Bob outputs all remaining tasks Communication complexity: ? bits Lower bound?

Reduction from DISJ to PARTITION Given input ?,? for DISJ : Notice: ? ? = iff ? ? = ? To test whether ? ? = ? : Try to solve PARTITIONon ?, ? ?,? Ensure ? ?,? ? Check if ?,? is a partition of ? : Alice sends Bob hash( ?), Bob compares it to hash(?)

From PARTITION to Spanning Tree Given a spanning tree algorithm ? 1 2 6 3 4 5 a b ? = {1,2,3} ? = {2,4,5,6}

From PARTITION to Spanning Tree Simulating one round of ? : 1 2 6 3 4 5 a b Node a s message Node b s message ? = {1,2,3} ? = {2,4,5,6}

From PARTITION to Spanning Tree When ? outputs a spanning tree: 1 2 6 3 4 5 a b ? = {1,2,3} ? = {2,4,5,6}

From PARTITION to Spanning Tree If ? runs for ? rounds, we use 2?? bits ? = ?/? One detail: randomness Solution: Alice and Bob use public randomness

When Two Players Just Arent Enough No bottlenecks in the network

When Two Players Just Arent Enough Too much information revealed

Multi-Player Communication Complexity Communication by shared blackboard Number-on-forehead Number-in-hand ??

The Message-Passing Model ? players Private channels Private ?-bit inputs ?1, ,?? Private randomness Goal: compute ? ?1, ,?? Cost: total communication

The Coordinator Model ? players, one coordinator The coordinator has no input

Message-Passing vs. Coordinator

Prior Work on Message-Passing For ? players with ?-bit inputs Phillips, Verbin, Zhang 12: ??for bitwise problems (AND/OR, MAJ, ) Woodruff, Zhang 12, 13: ?? for threshold and graph problems Braverman, Ellen, O., Pitassi, Vaikuntanathan 13: ?? for DISJ?,?

Set Disjointness ?2 ?1 ?3 ? ?5 ?4 ? ? ? DISJ?,?= ?? ?=1 ?=1

Notation : randomized protocol Also, the protocol s transcript ? : player ? s view of the transcript ?? = worst-case communication of ???? = min with error ???( ) in the worst case

Entropy and Mutual Information Entropy: ? ? = Pr ? = ? logPr ? = ? ? A lossless encoding of ? requires ? ? bits Conditional entropy: ? ? ? = ??? ? ? = ? ?(?)

Entropy and Mutual Information Mutual information: ? ?;? = ? ? ?(?|?) Conditional mutual information: ? ?;? ? = ??? ?;? ? = ? = ? ? ? ?(?|?,?)

Information Cost for Two Players [Chakrabarti, Shi, Wirth, Yao 01], [Bar-Yossef, Jayram, Kumar, Sivakumar 04], [Braverman, Rao 10], Fix a distribution ?, External information cost: ??,? ???; = ? ? ?? | | Internal information cost: ??,? ??; ? + ??,? ?(?; |X Extension to the coordinator model: ? [? ??; ??,? + ?(?; ?|??,?)] ?=1

Why is Info Complexity Nice? Formalizes a natural notion Analogous to causality/knowledge Admits direct sum theorem: The cost of solving ? independent copies of problem ? is ? times the cost of solving ?

Example ? ? ? DISJ?,?= ?? ?=1 ?=1

Example (Work in Progress) Triangle detection in general congested graphs Is there a triangle = ?1,?2,?3 is {?1,?2,?3}a triangle

Application of DISJ Lower Bound Open problem from Woodruff & Zhang 13: Hardness of computing the diameter of a graph We can show: ?? bits to distinguish diameter 3 from diameter Reduction from DISJ: given ?1, ,?? , Notice: ?1, ,?? disjoint iff ?1 ??= ?

Application of DISJ Lower Bound 3 2 4 ?2 ?3 1 5 ?1 ?3 ?4 6 ?1 ??= ? Diameter 3 ?1 ?? ? Diameter =

Part II: The Power of the Congested Clique CONGESTED CLIQUE

Conversion from Boolean Circuit Suppose we have a Boolean circuit ? Any type of gate, ?2 inputs Fan-in 2 Depth = polylog(?), #gates and wires = ?2polylog ? Step 1: reduce the fan-out to 2 Convert large fan-out gates to copying tree Blowup: ? log? depth, ? 1 size Step 2: convert to a layered circuit

Conversion from Boolean Circuit Now we have a layered circuit ? of depth polylog ? and size = ?2polylog ? With fan-in and fan-out 2 Design a CONGEST protocol: Fix partition of inputs ?1, ,?? of size ? each Assign each gate to a random CONGEST node Simulate the circuit layer-by-layer

Simulating a Layer If node ? owns gate ? on layer ?, it sends ? s output to the nodes that need it on layer ? + 1 Size of layer ? + 1 2 size of layer ? What is the load on edge ?,? ? For each wire from layer ? to layer ? + 1, Pr ???? ???????? ?? ?,? At most ?2polylog ? wires in total By Chernoff, w.h.p. the load is polylog ? = 1/?2

Conversion from Boolean Circuit A union-bound finishes the proof Corollary: explicit lower bounds in the congested clique imply explicit lower bounds on Boolean circuits with polylogarithmic depth and nearly-linear size. Even worse: Reasons to believe even (loglog?) bound hard

Conclusion LOCAL CONGESTED CLIQUE CONGEST / general network ASYNC MESSAGE-PASSING X