Yo-Yo Leader-Election Algorithm¶
A distributed leader-election protocol repeatedly propagates minimum identifiers forward through an oriented graph and returns yes/no decisions backward to eliminate candidates and prune the graph.
Core Idea¶
The Yo-Yo leader-election algorithm is a distributed minimum-finding protocol for a connected undirected network whose processes have distinct totally ordered identifiers. It logically orients active edges to obtain a directed acyclic graph, treats its sources as current candidates, propagates candidate identifiers forward in a “Yo-” phase, and sends yes/no decisions backward in a “-Yo” phase. Negative decisions reverse selected orientations so losing sources cease to be candidates; pruning removes edges or nodes that can no longer affect the minimum. Repetition leaves the process with globally minimum identifier as the unique leader.
Scope of Application¶
The protocol belongs to distributed graph algorithms and leader election. It applies to generic connected undirected topologies rather than only rings or complete graphs, provided the reliable bidirectional-channel and unique-identifier assumptions hold. Its purpose is to select a distinguished node without preassigning one, typically the minimum-ID node under the chosen total order.
It is especially useful pedagogically and analytically because the algorithm separates preprocessing, forward comparison, backward decision, and reduction. Santoro presents it in a general distributed-algorithm framework, while his dedicated slides expose the evolving DAG and elimination argument.
Clarity¶
Naming the Yo-Yo protocol separates the election specification from the algorithm satisfying it. “Choose one leader” says what terminal states are valid. “Elect the minimum identifier through alternating minimum flow and returned pruning decisions” says how this protocol progresses. It also distinguishes a physical undirected channel from a logical orientation: reversing an active edge changes the algorithmic direction, not the hardware's bidirectionality.
Manages Complexity¶
The algorithm avoids collecting the whole graph at a coordinator. Each node performs local comparisons and forwards a current minimum; the global order emerges through repeated local messages. Orientation summarizes which candidates can still influence which sinks, and pruning reduces subsequent work by deleting redundant routes or degree-one structures that no longer contribute a comparison.
Abstract Reasoning¶
Correctness separates safety and progress. For safety, the globally minimum identifier cannot be rejected by a smaller competing value, because none exists. Along routes carrying that minimum, local minimum selection preserves it; returned confirmations protect a route supporting it. For progress, a nonterminal round changes orientations so at least one current source becomes internal or a sink, reducing the candidate set. With finitely many nodes, repetition terminates.
Knowledge Transfer¶
The Yo-Yo design transfers literally among connected undirected network topologies satisfying the model. A path, tree, mesh, or irregular graph changes local degree and phase evolution but preserves sources, forward minima, backward feedback, reversals, and minimum survival. The invariant-guided proof transfers with those roles.
More broadly, the protocol illustrates candidate elimination, echo feedback, and monotone reduction. Those parent ideas can inspire distributed searches or pruning algorithms, but a system is not Yo-Yo merely because information travels out and back. Transfer of the name requires the minimum-ID election objective and alternating oriented-graph mechanism.
Relationships to Other Abstractions¶
Current abstraction Yo-Yo Leader-Election Algorithm Domain-specific
Parents (1) — more general patterns this builds on
-
Yo-Yo Leader-Election Algorithm is a kind of Algorithm Prime
The proposed strict parent is
prime:algorithm: Yo-Yo is a finite, specified procedure mapping an identified connected network to a leader designation, with correctness and termination obligations.
Hierarchy paths (2) — routes to 2 parentless roots
- Yo-Yo Leader-Election Algorithm → Algorithm → Function (Mapping)
Neighborhood in Abstraction Space¶
Yo-Yo Leader-Election Algorithm sits in a sparse region of the domain-specific corpus (74th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Discrete Structures & Graph Algorithms (17 abstractions)
Nearest neighbors
- Hadwiger number — 0.84
- Split-Brain Problem — 0.84
- Cross-reference Relation — 0.83
- Navigation loop — 0.83
- Luby transform code — 0.83
Computed from structural-signature embeddings · 2026-09-08