Ring (Chang–Roberts) — Leader Election

Overview

What this concept solves

The Ring algorithm arranges processes into a logical ring — each one knows only its clockwise successor. Elections happen by passing a single message around the ring, and the highest ID is still the winner. There are two famous variants: Le Lann's algorithm (1977) accumulates every ID it visits, picks the max at the end, and uses O(n²) messages. Chang–Roberts (1979) is the efficient version every textbook teaches: each message carries a single ID, a process forwards only IDs greater than its own, and the algorithm finishes in 3n−1 messages in the best case.

The key Chang–Roberts rule is: if the incoming ID is greater than mine, forward it. If it's less than mine and I'm not already participating, replace it with my ID and forward. If it's less and I'm already participating, discard it. If it's equal to my ID, I am the leader — start the COORDINATOR phase. The discard rule is what kills the O(n²) of Le Lann: bid messages with a smaller ID than the current participant cannot propagate further.

Ring election was the practical choice for token-ring networks of the 1980s and still shows up wherever the physical or logical topology is already a ring — IBM Token Ring, FDDI, some peer-to-peer overlays, and as a sub-component inside larger fault-tolerant protocols. As with Bully, modern replicated systems use Raft or lease-based election instead, but Ring is the cleanest example of how a structural constraint (the ring) can replace the all-to-all messaging of Bully.

Mechanics

How it works

Chang–Roberts protocol

Every process knows its clockwise successor only — no other peers required.
When a process P suspects the leader is dead, it becomes a participant, sends ELECTION(P) (its own ID) clockwise, and starts waiting.
When process Q receives ELECTION(id): if id > Q.id, forward unchanged and become a participant.
If id < Q.id and Q is not a participant, replace with ELECTION(Q.id) and forward — become a participant.
If id < Q.id and Q is already a participant, discard the message (someone bigger than you is already in the running).
If id == Q.id, the message has travelled the full ring and Q is the highest. Q becomes leader and sends COORDINATOR(Q.id) clockwise to announce.
Every process forwards COORDINATOR exactly once, sets its leader to Q, exits participant mode, and the election is over.

Failures along the way

Successor died — each process must know its successor's successor (a small static list) and reroute around the gap.
Initiator died during election — its own bid lapses; whichever other process is awaiting the COORDINATOR will time out and start a new election.
Two simultaneous initiators — both forward their IDs; the higher one absorbs the lower (rule 3 → discard), so still exactly one winner.

Why 3n − 1 messages?

Best-case Chang–Roberts: the highest-ID node starts the election. Its bid travels n hops to come back to itself (1 ELECTION × n). Every other bid is discarded immediately by the highest node so they cost nothing. Then COORDINATOR makes one full lap (n − 1 messages, since the leader doesn't message itself). Total: n + (n − 1) = 2n − 1. Worst case (lowest-ID starter) adds another lap of "absorbed" bids and lands at 3n − 1.

Le Lann vs Chang–Roberts — and what the reference simulator does

Le Lann's variant accumulates every visited ID in the message ([3,4,5,1,2]), forwards everything, and picks the max at the end — O(n²) messages but the algorithm is one line shorter. Chang–Roberts is what production protocols implement. The prototype here teaches Chang–Roberts because the discard rule is the interesting bit; some textbooks use Le Lann to visualise the running max.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Ring (Chang–Roberts)

About this simulation

Five processes arranged in a clockwise ring. Pick a scenario — Leader dies (one node notices, sends its own ID around; only larger IDs propagate forward), Concurrent starts (two nodes initiate at the same time and the higher ID swallows the lower one), or Mid-ring failure (a non-leader dies and the ring routes around it). Free play lets you crash any node and seed your own elections; the log card below holds only the last two messages.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Walk Leader dies

Open Leader dies. P5 (the leader, ID 5) crashes. P1 notices first and sends ELECTION(1). P2 sees 1 < 2 and (not a participant) bumps it to ELECTION(2). P3 → ELECTION(3). P4 → ELECTION(4). The ring skips dead P5 and returns to P1, which is now a participant. P1 forwards 4 onward. When the ELECTION(4) makes it back to P4, P4 wins. Notice the rule pattern: a bid only grows; it never shrinks.

try 02

Walk Concurrent starts

Run Concurrent starts. P2 and P4 both notice the leader is gone and both start elections at the same time. ELECTION(4) absorbs ELECTION(2) the moment it passes any participant whose ID ≥ 4 — P2's bid is discarded by the discard rule. Only one bid ever completes the loop: the higher one. This is the property that gives Chang–Roberts its single-winner guarantee.

try 03

Walk Mid-ring failure

Run Mid-ring failure. P3 (a follower, not the leader) dies. No election is needed — the ring just routes around it. The successor pointers heal, P1 → P2 → P4 → P5 → P1, the leader stays the same, and the cluster keeps working. Failover only happens when the leader goes silent.

try 04

Free play — break it yourself

Open Free play. Crash any node and start an election from anyone you like. Try crashing P5 then P4 in quick succession — the ring keeps converging on the highest remaining ID. Try starting two elections at once from neighbouring nodes; the higher absorbs the lower. The deterministic outcome — highest alive ID wins — is the same property as Bully, just achieved with O(n) messages on a ring instead of O(n²) on a clique.

In practice

When to use it — and what you give up

When it's the right tool

Your topology is already a ring — token-ring LANs, FDDI, some peer-to-peer overlays. The election just hops along existing edges.
Bandwidth is the bottleneck — each forwarded message is tiny (one ID) and traffic is bounded by O(n).
Teaching the discard / participant rule — the cleanest example of how state per process can shrink message complexity.
Inside larger protocols — token-passing mutual exclusion and group-membership protocols often use a ring-style election as a sub-step.

When to reach for something else

Fully connected modern data centre — every node already talks to every other; the ring constraint adds latency for no benefit. Use Raft.
Frequent membership changes — the ring has to be rewired on every join/leave, and out-of-sync successor pointers cause messages to vanish.
Strict safety against partitions — Ring has no quorum. A partition into two arcs lets each arc elect its own leader.
Latency-sensitive failover — election takes ~n hops in latency, even in the best case. Lease-based or Raft are sub-RTT in the common case.

Pros

Single-ID messages — bandwidth-cheap and easy to log.
Only neighbour knowledge required — no all-to-all addressing.
Deterministic winner — the highest alive ID, every time.
Chang–Roberts is O(n) on average — far better than Bully's worst case.

Cons

Ring repair is non-trivial — a dead successor leaves the ring broken; recovering needs a stored successor-list or a separate ring-maintenance protocol.
Latency proportional to ring length — election takes O(n) hops in series, even in the best case.
No quorum — a partition into two arcs lets each arc crown its own leader. Same split-brain problem as Bully.
Fragile under high churn — joins and leaves race against in-flight election messages and can lose the bid.
No fence token — COORDINATOR carries no monotonic epoch, so a paused-then-resumed old leader can still write after a new one is elected.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

ring.ts

// Chang–Roberts ring election. Each process knows only its clockwise successor.
type ProcId = number;
type Msg =
  | { kind: "election"; id: ProcId }
  | { kind: "coord"; leader: ProcId };

class RingProcess {
  private participant = false;
  public leader: ProcId | null = null;

  constructor(
    public readonly id: ProcId,
    private next: (m: Msg) => Promise<void>, // send to clockwise successor
  ) {}

  /** Triggered when this process suspects the leader is dead. */
  async startElection() {
    if (this.participant) return;
    this.participant = true;
    await this.next({ kind: "election", id: this.id });
  }

  async onMessage(m: Msg) {
    if (m.kind === "election") {
      if (m.id > this.id) {
        this.participant = true;
        await this.next(m);                          // forward larger bid
      } else if (m.id < this.id && !this.participant) {
        this.participant = true;
        await this.next({ kind: "election", id: this.id }); // bump to my ID
      } else if (m.id < this.id && this.participant) {
        return;                                      // discard — smaller bid
      } else { // m.id === this.id  -> we are the winner
        this.participant = false;
        this.leader = this.id;
        await this.next({ kind: "coord", leader: this.id });
      }
    }

    if (m.kind === "coord") {
      this.participant = false;
      this.leader = m.leader;
      if (m.leader !== this.id) await this.next(m);  // forward one lap
    }
  }
}

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

In Chang–Roberts, what happens when a participant process receives an ELECTION message with an ID smaller than its own?

question 02 / 03

Why does Ring election have lower message complexity than Bully?

question 03 / 03

Two processes start a Ring election at the same time. How does Chang–Roberts guarantee a single winner?

0/3 answered