Chang–Roberts Algorithm

A unidirectional-ring leader-election protocol in which ordered identifiers circulate selectively until the maximum identifier returns to its owner.

Version

v3 · 2026-09-19 · History

Domain-specific #

1455

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Distributed Computing, Leader Election → Computer Science & Software Engineering

Aliases

Chang and Roberts Algorithm, Le Lann–Chang–Roberts Algorithm, LCR Algorithm

Core Idea

The Chang–Roberts algorithm elects one distinguished process in a directed ring whose processes have unique, totally ordered identifiers. An election message carries a candidate identifier in the ring's communication direction. A process forwards an identifier greater than its own, suppresses a smaller candidate when that candidate cannot win, and recognizes itself as leader when its own identifier completes the circuit. The maximum identifier is the only candidate capable of surviving a full traversal. A subsequent announcement communicates that result to the other processes.

How would you explain it like I'm…

Biggest Number Wins the Circle

Some kids sit in a circle, each with a different number, and they can only pass notes to the kid on their left. Everyone writes their number on a note and passes it. If a note's number is bigger than yours, you pass it on; if it's smaller, you throw it away. If your own note comes all the way back around, you have the biggest number, you're the leader, and you tell everyone.

Ring Leader by Biggest ID

The Chang–Roberts algorithm is a way for computers arranged in a one-way circle to pick one leader. Each computer has its own unique ID number, and all the numbers can be compared. Each computer sends its ID around the circle. When a computer gets an ID bigger than its own, it passes it along; when it gets a smaller one that can't win, it drops it. Only the biggest ID can make it all the way around, so the computer that sees its own ID come back knows it's the leader. Then it sends a message around to tell everyone else.

Ring Election by Selective Forwarding

The Chang–Roberts algorithm is a distributed protocol for electing a leader among processes arranged in a directed (one-way) ring, where each process has a unique identifier and identifiers can be totally ordered. Each process sends an election message with a candidate ID in the ring's direction. When a process receives an ID larger than its own, it forwards it; when it receives a smaller one, it suppresses it, since that candidate can't win. The maximum ID is the only one that survives a full trip around the ring, so the process that receives its own ID back declares itself leader and then sends an announcement so everyone learns the result. The key improvement is selective forwarding, which cuts down on messages. It is also called LCR (Le Lann–Chang–Roberts) when an earlier ring algorithm that forwarded all identifiers is credited too.

 

The Chang–Roberts algorithm elects a single distinguished process in a unidirectional ring whose processes have unique, totally ordered identifiers. Each process initiates an election message carrying a candidate identifier in the direction of communication. A process forwards any received identifier greater than its own, suppresses a smaller one because that candidate cannot win, and recognizes itself as leader when its own identifier completes the circuit. Since only the maximum identifier can survive a full traversal, exactly one leader is chosen, and a subsequent announcement message disseminates the result. The protocol's identity is this package of a unidirectional ring, comparable unique identifiers, selective circulation, local suppression, return-to-origin recognition, and dissemination—not merely 'choosing a leader.' Chang and Roberts introduced the selective message-extinction improvement for decentralized extrema finding in circular configurations, and later analysis established its average-case message complexity and compared unidirectional and bidirectional variants. It is sometimes called Le Lann–Chang–Roberts (LCR), crediting an earlier algorithm that circulated all identifiers, so the selective-forwarding protocol should be defined explicitly.

Scope of Application

The native setting is distributed computing over logical or physical rings. The protocol is useful as a canonical example for reasoning about leader election, comparison-based distributed algorithms, asynchronous message passing, and the separation of safety from liveness.

The ring can be logical: the participating processes need only agree on a successor relation that forms one directed cycle. Processes need not know the ring size in the standard presentation; they learn the outcome from message circulation rather than counting hops. They do need unique comparable identifiers and a common direction of forwarding.

Clarity

Two presentations must be distinguished. In a simultaneous-start textbook form, each process sends its own UID and forwards only a UID larger than every relevant local candidate. In an initiation-sensitive form, a nonparticipant receiving a smaller UID may replace it with its own and become a participant; a participant receiving a smaller UID suppresses it. Both realize the same selective-survival invariant when their initialization rules are stated consistently.

Manages Complexity

Selective extinction reduces redundant circulation. In the naïve ring method, every one of \(n\) identifiers can travel through \(n\) links, producing quadratic communication even in ordinary arrangements. Chang–Roberts lets a locally superior candidate eliminate inferior candidates before they complete the circuit.

The worst case remains \(O(n^2)\) message transmissions because an adverse cyclic ordering can allow many candidates to travel far before meeting a superior UID.

Abstract Reasoning

Let \(M\) be the greatest UID. Once an election message carrying \(M\) is sent, every other process compares it with a smaller UID and forwards it. Reliable eventual delivery therefore carries \(M\) through all \(n\) links and back to its owner. This establishes liveness under the stable-ring assumptions.

Knowledge Transfer

Literal transfer occurs across ring implementations that preserve the directed-cycle, ordered-UID, comparison, suppression, and return roles. The same proof applies whether the ring is represented by network links, a logical overlay, or a simulator.

The broader transferable lesson is monotone elimination: candidates carry evidence, local comparisons discard dominated candidates, and a full traversal certifies an extremum. That skeleton connects to tournament and selection procedures, but without ring circulation and distributed ownership it is analogy, not another instance of Chang–Roberts.

Relationships to Other Abstractions

Current abstraction Chang–Roberts Algorithm Domain-specific

Parents (1) — outgoing typed relations

• Chang–Roberts Algorithm is a kind of Algorithm Prime

  prime:algorithm is the broader abstraction this entry instantiates: Chang–Roberts is a finite rule system mapping admissible distributed executions to a selected leader.

Hierarchy path (1) — routes to 1 parentless root

• Chang–Roberts Algorithm → is a kind of Algorithm → presupposes, conditional Function (Mapping)

Neighborhood in Abstraction Space

Chang–Roberts Algorithm sits in a sparse region of the domain-specific corpus (97^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Ballot-Order Effect — 0.79
• Countback — 0.78
• Dot-Voting — 0.77
• Lockstep (computing) — 0.76
• Decoy list — 0.76

Computed from structural-signature embeddings · 2026-10-25