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})$.