R10. Distributed Algorithms

What this lecture covers

This recitation reviews and extends distributed algorithms material from the lectures by working through two problems in detail: leader election on a ring network (rather than the clique covered in lecture), and counting the total number of nodes in a network. For each problem, the class collaboratively develops a naive solution first, then improves it, with the instructor pushing students toward better complexity bounds and more careful termination handling.

This recitation follows the two-lecture unit on synchronous and asynchronous distributed algorithms and assumes familiarity with concepts like breadth-first spanning trees, convergecast, and message-passing between processes with only local neighbor knowledge. After watching, you should be able to derive an O(n log n)-message ring leader election algorithm using an increasing-hop-count technique, and write out, in near-pseudocode, a full spanning-tree-based algorithm that counts nodes using convergecast, including how it degrades gracefully from a BFS tree to an arbitrary spanning tree under asynchrony.

Key ideas

• Ring leader election, naive version: propagate every node's ID around the ring in one direction; after n rounds everyone has seen everyone else's ID, using O(n^2) messages total.
• Dropping non-competitive messages: a node can stop forwarding an ID it knows cannot be the maximum, but in pathological orderings (IDs arriving in increasing order) this optimization still costs O(n^2) messages in the worst case.
• Doubling-range algorithm: each surviving candidate sends its ID outward 2^i hops in round i; if it is still the local maximum over that range when the probe returns, it doubles its range next round, while non-maximal candidates go silent, giving O(n log n) total messages.
• Works synchronously or asynchronously: the doubling-range algorithm needs no shared round counter across nodes; each node just tracks its own round locally, so results still converge correctly even if nodes are out of step.
• Node counting via spanning tree: build any spanning tree of the network, then have each node report the size of its own subtree (including itself) up to its parent, so the root ends up with the total node count.
• BFS spanning tree in synchronous networks: works by having the root broadcast "you are my child" outward, with each node accepting only its first parent offer; this degrades to just "a" spanning tree (not necessarily breadth-first) when run asynchronously, because message delays can let a farther node's offer arrive before a nearer one's.
• Convergecast for termination and counting: leaves initiate "I'm done" messages (with subtree size 1) up the tree once all their search responses are in; internal nodes wait for all children's "done" messages, sum reported subtree sizes plus themselves, and forward their own total upward.

Walkthrough

Ring leader election: the naive propagation algorithm (1:05)

The recitation reframes leader election for a ring topology, where each node only has two neighbors instead of the full connectivity of a clique. Through class discussion, the instructor develops the idea that each node passes along the running maximum of the IDs it has seen, so information about the largest ID propagates one hop per round. With one-directional propagation this takes n rounds and O(n^2) total messages, since every message is effectively relayed by every node.

An optimization that doesn't change the worst case (9:20)

A student suggests dropping messages that carry an ID clearly too small to be the maximum, since a node already knows its own value beats them. This reduces average-case traffic, but the recitation constructs a pathological ordering, IDs increasing steadily as they travel, where no node can ever drop a message, showing the worst-case message count remains O(n^2).

The doubling-range algorithm (12:22)

Building on a "let weak candidates go quiet early" idea proposed in discussion, the recitation develops the actual improved algorithm: in round i, each still-active node sends its ID up to 2^(i-1) or 2^i hops in both directions (implemented via a hop-count field that gets decremented, reversed, and echoed back). A node stays active into the next round only if it hears back that it was the local maximum over that range from both directions; otherwise it goes silent. The number of active nodes roughly halves each round, giving a logarithmic number of rounds and an overall message complexity the class estimates near O(n log n), matching the general shape (though the exact constant differs slightly from the written recitation notes).

Node counting: choosing a spanning-tree strategy (25:33)

For the second problem, counting the total number of nodes, the class first considers directly propagating sets of known IDs, then converges on a cleaner strategy: build a spanning tree of the network and have each node report the size of its own subtree, including itself, up to its parent, so the root accumulates the full count without needing global information anywhere else.

Building a spanning tree, synchronously and asynchronously (31:00)

The recitation reviews the lecture's BFS spanning tree algorithm: a root sends "you are my child" messages outward, and each node accepts only the first such offer, rejecting later ones. Run on an asynchronous network, this still produces a valid spanning tree, but not necessarily a breadth-first one, since message delays can let a message that traveled farther arrive before a shorter one; getting an actual BFS tree asynchronously would require the edge-relaxation approach from the main lecture instead.

Writing out the full algorithm in pseudocode (35:04)

The instructor builds the algorithm incrementally in near-code form for a generic process U: on receiving a search message from V, adopt V as parent if none is set yet, respond with parent=true or parent=false, and forward search messages to all other neighbors. On receiving a parent response, track which neighbors accepted U as their parent in a children set. The root is handled as a special case that initiates the process by treating itself as already having a parent.

Termination and counting via convergecast (43:14)

Since no node initially knows how many nodes exist, termination cannot simply wait a fixed number of rounds. The recitation adds a searched set tracking which neighbors have responded, and once that set covers all neighbors and all children have reported done, a node sends an I'm done message up to its parent, carrying a total count of its subtree size (including itself). Leaves, which have no children, initiate this convergecast immediately; internal nodes sum their children's reported totals, add one for themselves, and forward the result upward, so the root ends up with the complete node count once the convergecast finishes.

Before you watch

• Watch "19. Synchronous Distributed Algorithms" and "20. Asynchronous Distributed Algorithms" first, since this recitation directly reuses BFS spanning trees, convergecast, and the synchronous/asynchronous distinction from those lectures.
• Be comfortable with basic pseudocode for message-passing processes, since much of this recitation is spent building an algorithm's code incrementally on the board.
• Review why unique identifiers are needed to break symmetry in leader election, covered in the earlier lecture.

Check your understanding

1. Why does dropping obviously non-maximal messages fail to improve the worst-case message complexity of naive ring leader election?
2. Walk through why the doubling-range algorithm's active node count roughly halves each round, and how that leads to a logarithmic number of rounds.
3. Why does the simple "accept the first parent offer" spanning tree algorithm still produce a valid spanning tree on an asynchronous network, even though it may not be breadth-first?
4. Explain why leaves are the ones that initiate the convergecast "I'm done" signal, rather than the root.
5. In the node-counting algorithm, why must a node wait for searched to cover all its neighbors before it can know its final list of children?