Oshman

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 Ω 

similar documents