Report

The Role of Communication Complexity in Distributed Computing Rotem Oshman Background: Distributed Computing Distributed Computing • Typical model: – Local computation for free – Charge for “communication” Distributed Lower Bounds • “All or nothing”: – If , have not communicated, they know nothing about each other – If , communicated, they know everything about each other • Recently: interest in quantifying the amount of communication • Natural to use communication complexity Shared Memory • Processes communicate by accessing objects in shared memory – Read/write registers – Read-modify-write: CAS, T&S, … • Typically asynchronous: – Schedule = sequence of process IDs – Adversarially chosen – Sometimes processes may crash Shared Memory Lower Bounds • “Covering arguments” • Examples: – Deterministic consensus impossible if one process may fail [FLP’79] – Mutual exclusion requires shared registers [BL’90] • Can we introduce a cell-probe-like model for shared memory lower bounds? Message Passing • Processes communicate by sending messages – Over some network graph, often complete • Fully synchronous, fully asynchronous, or anywhere in between • Processes can crash, recover, cheat, lie,… • Many successful applications of CC Some differences… Distributed Computing Complexity #rounds (limited bandwidth) measure Comm. Complexity total #bits Problems Search Decision Input Number-In-Hand Number-onForehead (usually) Message-Passing Models #rounds total CC LOCAL SHARED BLACKBOARD CONGEST MESSAGE-PASSING Talk Overview I. Lower bound techniques a. CONGEST (#rounds): reductions from 2-party communication complexity b. Total CC with private channels II. Shared blackboard a. Number-in-hand b. “Not-quite-number-in-hand” The CONGEST Model • nodes communicate over a network graph (small diameter) • Computation proceeds in synchronous rounds • Each message = bits • Several variants: – Communication by unicast vs. local broadcast – Arbitrary graph vs. complete graph The CONGEST Model • Arbitrary graph topology: strong lower bounds – [Distributed Verification and Hardness of Distributed Approximation, by Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, Wattenhofer] • Nearly-tight lower bound on MST approximation • Non-tight lower bounds on all-pairs shortest path, minimum cut, shortest s-t path, … • Almost all lower bounds ≤ Ω / – Very few Ω / bounds known, no super-linear bounds The CONGEST Model • Complete graph topology, unicast: – Known to be extremely powerful, e.g., • Sort 2 values in log log rounds • MST construction in log ∗ rounds – No explicit super-constant lower bound known – [Drucker, Kuhn, O. ‘14]: even slightly superconstant lower bound ⇒ new ACC lower bound • Complete graph topology, broadcast = shared blackboard CONGEST Lower Bounds for Arbitrary Graphs … by reduction from 2-party disjointness 2-Party Reductions • Textbook reduction [Kushilevitz Nisan]: Given algorithm for solving task … Simulate Based on bits Based on Solution for ⇨ answer for, e.g., Disjointness 2-Party Reductions • More generally: Given algorithm for solving task … Based on Based on Solution for ⇨ answer for, e.g., Disjointness Multi-Player NIH Communication with Private Channels 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 ≈ Secure multi-party computation! Message-Passing Lower Bounds For players with -bit inputs… • Woodruff, Zhang ‘12: estimation • Phillips, Verbin, Zhang ’12: – Ω for bitwise problems (AND/OR, MAJ, …) • Woodruff, Zhang ‘13: – Ω for threshold and graph problems • Braverman, Ellen, O., Pitassi, Vaikuntanathan ‘13: Ω for disjointness Symmetrization [Phillips, Verbin, Zhang ’12] Lower bound for -player problem : • Choose hard 2-player problem 2 • Fix hard distribution 2 for 2 , let , ∼ 2 Bob: “Smear” across − 1 players Alice: Symmetrization [Phillips, Verbin, Zhang ’12] Lower bound for -player problem : Bob: “Smear” across − 1 players Alice: – -player distribution must be symmetric – Answer to ⇒ answer to 2 2 [ cost for 2 ] = ⋅ cost for Symmetrization Example: Bitwise-XOR • 2-party problem: – Input: uniform independent , ∈ 0,1 – Goal: Alice outputs Bob’s input, • Reduction: – Sample uniform ∈ , Alice sets = – Bob chooses − uniformly s.t. ⊕≠ = – From ⊕ℓ=1 ℓ , Alice can reconstruct Bob: Alice: Set Disjointness 2 1 3 ? 5 4 DIS J , = =1 =1 Symmetrization vs. Disjointness • Consider any symmetric distribution… Bob: Alice: • How many 0s in coord. , given =1 = 0? – More than one ⇒ Bob probably sees a zero • Ignore this coordinate – Only one ⇒ Pr[ Alice got it ] ≈ – 2-party CC ≤ log 1 [BEOPV’13] Lower Bound Outline DIS J , = =1 =1 1. Direct sum: DIS J , ≥ ⋅ AND 2. One-bit lower bound: AND ≥ Ω Reduction from DISJ to graph connectivity [Based on WZ’13] (Players) 1 1 (Elements) 2 2 3 4 input graph connected ⇔ ⋃ = ⇔ ⋂ = ∅ 5 6 ∖ ⋃ Number-In-Hand Shared Blackboard Why Should We Care? • Some fundamental question still open • Natural model for distributed computing – Single-hop wireless network – More generally, abstracts away network topology – Related to MapReduce, etc. [Hegeman and Pemmaraju’14] Example: NIH Multi-Party Disjointness • Trivial upper bound: – Also easy to get log + • Simultaneous CC: Ω [Braverman,Ellen,O.,Pitassi,Vaikuntanathan’13] – In rounds? – Looks like for = , Ω 1+1/2 [current work with Ran Raz] • Unbounded rounds: Θ log Braverman] [with Mark “Not-Quite Number in Hand” • In undirected networks, each edge is known to both endpoints • Distributed graph property testing: – Players 1, … , , input graph = , – Input to player : its neighbors in – Goal: test if satisfies property • Example: subgraph detection [Drucker, Kuhn, O. ‘14] Example: Lower Bound for 5 • Claim: -round algorithm for 5 detection ⇒ solve DISJ2 in ⋅ ⋅ bits • Reduction outline: – Alice and Bob get inputs , ⊆ × – Construct input graph on 5 nodes, such that contains 5 ⇔ ∩ ≠ ∅ – Simulate the run of 5 -detection algorithm on Construction of from , 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 Construction of from , 1 1 2 2 3 3 4 4 Top-bottom: , ∈ Bottom-top: , ∈ 1 1 2 2 3 3 4 4 Construction of from , 1 1 2 2 3 3 4 4 , ∈ ∩ 1 1 2 2 3 3 4 4 Simulating the Algorithm • Alice simulates 3 nodes, Bob simulates 2 • To simulate one round, each player: – Locally computes message broadcast by each node it simulates – Sends all messages to the other player – Cost: ⋅ per round • Total cost: ⇒=Ω What About 4 ? • More complicated…. Can contain 4 regardless of Solution: use extremal 4 -free graph Elements of DISJ = edges of Upper Bound on Subgraph Detection • Turán number: , = max # edges in free graph on vertices • Upper bound: solve -subgraph detection in , rounds – Example: 5 , = 2 /4, nearly tight – Open problem: is this tight for all subgraphs? Detecting Triangles • Trivial upper bound: rounds • Lower bound? – 2-party (black box) reduction cannot prove it – For each triangle, one player knows all 3 edges Triangles to 3-Party NOF Disjointness • [Ruzsa and Szemerédi ’76]: there is a tripartite graph = ( ∪ ∪ , ) where – = = , = /2 – contains T = 2 / log triangles – Each edge in belongs to exactly one triangle • Reduce from 3-party NOF Disjointness on elements, each representing one triangle in Triangles to 3-Party NOF Disjointness • Input: sets of triangles , , ⊆ • Let () be the unique triangle edge belongs to • Construct ′ ⊆ , including: – ∈ × iff ∈ – ∈ × iff ∈ X – ∈ × iff ∈ • Note: endpoints of each edge agree on its inclusion! Triangles to 3-Party NOF Disjointness • Input: sets of triangles , , ⊆ • Triangle appears in ′ ⇔ ∩ ∩ ≠ ∅ • Cost of simulation: – () bits per round ⇒ Round complexity of triangle detection ≥ (DIS J )/() for 3-party NOF 3-Party NOF Disjointness • Randomized CC: – Sherstov’13: Ω – We get nothing: #elements <1 • Deterministic CC: – Rao and Yehudayoff’14: Ω #elements ⇒Ω ⋅ detection log for deterministic triangle Conclusion #rounds total CC LOCAL SHARED BLACKBOARD CONGEST MESSAGE-PASSING Directions for Future Research • Exploiting asynchrony and faults to get stronger communication lower bounds Example 1: Dynamic Networks • Abstract model for dynamic networks: – In each round we get a different graph • [Kuhn, Lynch, O. ‘10]: – Assume each is connected – Any function can be deterministically computed in 2 rounds using log -bit messages – Lower bounds? Example 1: Dynamic Networks • For exchanging all inputs: – Determistic, “routing-based” algorithms: Ω [Haeupler, Kuhn’12] – Randomized?? – Non-routing based?? 2 log Example 2: Byzantine Consensus • processes, synchronous message-passing • Each process receives a bit • Goal: – Everyone outputs the same bit – If everyone received , the output is 3 • Byzantine faults: up to − processes may behave arbitrarily Example 2: Byzantine Consensus • [King, Saia ‘10]: can solve with (3/2 ) total bits • No general lower bound better than Ω