19. Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees

What this lecture covers

This lecture shifts from single-machine algorithms to distributed algorithms, where a network of processes sitting at the vertices of a graph communicate over channels in synchronous rounds and must solve problems without any central coordinator. It introduces the synchronous distributed model, then works through three problems: leader election (breaking symmetry among identical processes), maximal independent set (Luby's randomized algorithm), and computing a breadth-first spanning tree, closing with the start of a weighted shortest-paths version using a distributed Bellman-Ford algorithm.

The lecture builds no prerequisites from earlier parts of this course beyond general algorithmic maturity and familiarity with graphs, spanning trees, and induction-based proofs; it explicitly introduces a new model, new complexity measures (rounds and messages, not local computation time), and new proof techniques (invariants and convergecast). After watching, you should understand why deterministic, identical processes cannot break symmetry, how randomness or unique identifiers fix this, how Luby's algorithm achieves fast expected termination via an edge-counting argument, and how a breadth-first spanning tree is built and its completion detected in a distributed setting.

Key ideas

• Synchronous distributed model: processes sit at graph vertices, communicate over channels in synchronous rounds, and complexity is measured in rounds and messages, not local computation cost.
• Symmetry-breaking impossibility: deterministic, indistinguishable processes on a clique can never elect a unique leader, proved by induction showing all processes stay in identical states forever.
• Unique identifiers or randomness: leader election becomes easy once processes have unique IDs (send them around, take the maximum) or choose random IDs from a large enough space to avoid collisions with high probability.
• Maximal independent set (MIS): a subset of vertices with no two neighbors both included, and no vertex that could be added without violating that property.
• Luby's algorithm: each active node picks a random value each phase; a node with the locally maximum value joins the MIS and its neighbors drop out, repeating on the shrinking graph.
• Edge-halving argument: Luby's algorithm is shown to reduce the expected number of live edges by half each phase, giving termination within about 4 log n phases with high probability.
• Breadth-first spanning tree construction: starting from a marked root, each newly marked node sends a search message to its neighbors, who mark themselves and pick a parent, producing a correct BFS tree after a number of rounds equal to the graph's diameter.
• Convergecast termination detection: leaves signal "done" up the tree once they know they have no children, and each internal node forwards "done" to its parent only after hearing from all its children, letting the root learn when construction is complete.

Walkthrough

The distributed model and its complexity measures (5:11)

The lecture defines the synchronous network model: an undirected graph with a process at each vertex and communication channels along each edge. In each round every process reads its state, decides what to send on each port, messages are delivered, and processes update state. Local computation cost is ignored; the focus is on round count and message or bit count. Ports are unlabeled beyond local names, and processes may be entirely indistinguishable.

Leader election and the impossibility for identical processes (10:18)

The lecture defines leader election, then proves that on a clique of indistinguishable, deterministic processes, no algorithm can elect a unique leader. The proof shows by induction that all processes remain in identical states after any number of rounds, since they start identically, send and receive identical messages, and update identically — so if one process ever outputs "leader," they all would, violating the requirement that exactly one does.

Breaking symmetry with identifiers or randomness (18:36)

Once processes carry unique identifiers, leader election becomes trivial: everyone broadcasts its ID, and whoever holds the maximum elects itself in one round using O(n^2) messages. The lecture then shows that random IDs chosen from a large enough space (n^2 / (2*epsilon)) are distinct with probability at least 1 - epsilon, via a union bound over pairs, giving a fast randomized alternative when true unique identifiers are unavailable.

Maximal independent set and Luby's algorithm (24:44)

The lecture defines a maximal independent set and notes applications from overlay networks to a developmental-biology algorithm mirrored by fruit fly cells. It then presents Luby's algorithm: in each phase, active nodes pick random values, exchange them with neighbors, and any node whose value is a strict local maximum joins the MIS and tells its neighbors to drop out; this repeats on the remaining active subgraph until everyone has decided.

Proving Luby's algorithm terminates quickly (36:00)

The lecture proves that, ignoring the small probability of duplicate random values, the expected number of live edges drops by at least half each phase. The argument computes, for each vertex, the probability it is "killed" by a neighbor whose value beats both its own neighbors and the vertex's other neighbors, sums this into a bound on the probability an edge dies, and manipulates the resulting double sum over vertices and their neighbors until it collapses to half the edge count. This yields termination within about 4 log n phases with probability at least 1 - 1/n.

Building a breadth-first spanning tree (49:19)

Given a distinguished root and unique identifiers, the lecture presents a simple algorithm: the root sends a search message to its neighbors; any unmarked process receiving a search message marks itself, picks one sender as its parent (nondeterministically if several arrive at once), and forwards search messages onward next round. This produces a correct BFS tree, with correctness argued through invariants (which nodes are marked by round r, and that a marked node's parent lies at distance one less) proved by induction, and completes in rounds equal to the graph's diameter using O(E) messages.

Detecting termination and extending the tree (1:04:32)

Because no process knows the graph's shape, the root cannot simply assume the tree is finished. The lecture introduces convergecast: once a node knows all its children (from search responses) and has received "done" messages from each of them, it forwards "done" to its own parent; when the root has heard from all its children, it knows the tree is complete and can broadcast that fact downward. This takes at most diameter-many additional rounds and O(n) messages, and the same tree structure supports efficient one-to-many broadcast and many-to-one data aggregation.

Toward weighted shortest paths with distributed Bellman-Ford (1:11:39)

The lecture closes by extending the problem to weighted graphs, where each process tracks its current best distance and parent, sends its distance to neighbors each round, and relaxes its estimate whenever a neighbor's distance plus the connecting edge weight improves on what it currently has. An animation shows distance estimates being corrected over several rounds as better, longer paths are discovered, previewing the correctness and complexity analysis to be completed in the next lecture on asynchronous algorithms.

Before you watch

• Be comfortable with induction-style correctness proofs and probability tools such as the union bound, since both are used repeatedly.
• Review spanning trees, breadth-first search, and the sequential Bellman-Ford algorithm, since the distributed algorithms in this lecture directly parallel them.
• No prior lecture in this course is required; this is the first of a short standalone unit on distributed algorithms.

Check your understanding

1. Why can no deterministic algorithm elect a unique leader among identical processes on a clique, regardless of how the algorithm is designed?
2. How does choosing random identifiers from a sufficiently large space let processes emulate unique identifiers with high probability?
3. In Luby's MIS algorithm, why must a node's random value beat both its own neighbors' values and its neighbor's other neighbors' values for the "kill" argument to use disjoint events?
4. Explain how convergecast lets the root of a breadth-first spanning tree learn that the entire tree has been constructed, without ever collecting the whole tree in one place.
5. How does the distributed Bellman-Ford relaxation step differ from simply running the sequential Bellman-Ford algorithm at one node?