CONGEST Model

In each round, the node can send $O(\log n)$ bit message.

Things can be encoded in $O(\log n)$ bits:

Node ID
Number of edges
Number of nodes
Distance between two nodes

Gathering the graph can not be done in CONGEST model in $O(diam(G))$ time. Because it requires $\Omega(n^2)$ messages. It can be done in $O(n)$ time, but challenging.

APSP with CONGEST Model

Assuming that the edges have no weights.

Leader Electing

Each node is entitled by an ID.

The nodes exchange message by sending the minimum IDs they have received.

The node with minimum ID is the "leader".

This can be done in $O(diam(G))$ rounds.

SSSP

Suppose we have a source node now.

The source node sends messages to all its neighbors, and the neighbors forward the message by adding $1$ (as distance). After every node is reached, the messages will be propagate back.

This can be done in $2\cdot diam(G)$ rounds.

Also by this, we construct a BFS tree.

WAVE Algorithm

There is a token $\tau$ from the leader, traverse on BFS tree.

From the leader, it sends the "WAVE" message (containing its ID and distance $0$) and the token $\tau$ to all its neighbors, and when the a receive the message, it forwards to the other neighbor nodes.

When a node receives the token $\tau$, after 2 rounds, it starts to send its own "WAVE" message (containing its own ID and distance $0$) and token $\tau$ to all its neighbors.

Why after $2$ rounds?

Because there will be conflicts the node starts to send "WAVE" message in after $1$ round.

Let $t_u$ and $t_v$ be the earliest round when $u,v$ has token $\tau$.

$\tau$ moves from $u$ to $v$ between rounds $t_u$ and $t_v$. Round number increases by $2$ each time $\tau$ moves by one edge. $$ t_v-t_u\geq2\cdot dis(u,v) $$ This holds for any pair of $u,v$, so no waves can interfere.

Complexity

Computing the initial BFS tree $T$ takes $O(diam(G))$ rounds

Walk $W$ visits each edge of $T$ twice, $T$ has $n − 1$ edges so the token moves $2n − 2$ times.

It moves every second round so $O(n)$ rounds to complete the walk.

Thus, every execution of wave starts within O(n) rounds and takes an additional $O(diam(G))$ rounds to finish.

So overall WAVE algorithm takes $O(n+diam(G))=O(n)$ rounds.

APSP Lower bound

On CONGEST model the lower bound is tight: $\Omega(\frac{n}{\log n})$.

Proof sketch:

Show that a lower bound for computing the diameter implies the same lower bound for APSP.
Prove the lower bound for computing the diameter.

Reduction

Given a solution for APSP, we can compute the diameter in $O(diam(G))$ rounds.

Each node store the maximum length of all its shortest paths in $G$.
Construct a BFS tree in $O(diam(G))$ rounds
Leaves send their maximum distance to parent
Non-leaves compute the maximum distance among their own and the ones of its children, send to parent.
Broadcast the value of the diameter.

If computing the diameter requires $\Omega(n/\log n)$ rounds, APSP must require $\Omega(n/\log n)$ rounds in all graphs with diameter $o(n/\log n)$.

Computing the Diameter

Proof of $\Omega(n/\log n)$ lower bound requires known results from $2$-party communication complexity on Set Disjointness.

Computing the diameter can be reduced to set disjointness problem.

Construction of graph is complicated. If diameter is $\geq5$, the sets are not disjoint. If diameter $=4$, the sets are disjoint.