KT-1 CONGEST Model: Exponential-Round Algorithm with Õ(n) Messages

  1. Build a spanning tree
    Construct a spanning tree \(T\) in \(\tilde{O}(n)\) rounds/messages.

  2. Elect a leader
    Choose a leader at the root of \(T\). Every node learns its distance from the leader.

  3. Enumerate possible graphs
    With an ID space of size \(n^c\), there are exponentially many possible graphs.
    Each permutation of node IDs defines a different candidate graph.

  4. Convergecast process
    Let \(E\) be the enumeration of these permutations.
    The algorithm runs for \(d\) iterations (where \(d\) is the tree’s depth), and each iteration has \(t\) rounds:
    • Iteration 1: Leaves send 1-bit signals to their parents indicating whether their neighborhood matches graph \(E_1\).
    • Subsequent rounds: Repeat the check for \(E_2, E_3, \dots, E_t\).
    • Iteration i > 1: Nodes at distance \(d - i + 1\) send bits upward, encoding both their neighborhoods and info received from children.
    • This way, the root gradually reconstructs the entire graph topology.

  5. Root learns the graph
    After \(d\) iterations, the root \(u_*\) has complete knowledge of the graph.

  6. Broadcast back
    The root then disseminates this knowledge down the tree in another \(d\) iterations, using only \(\tilde{O}(n)\) messages.

  7. Solve the problem
    Finally, each node locally computes the solution from the reconstructed topology.