CoreConcept & Pseudocode Entry

Ring Leader Election (Chang-Roberts)

Elects the highest-ID leader among processes arranged in a unidirectional logical ring by forwarding only the maximum candidate ID around the ring.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Systems
Difficulty: Beginner
Family: Leader Election & Coordination
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 2
Code example: Not ready
Visualization: Ready
Aliases: Chang-Roberts Algorithm, Token Ring Leader Election, Logical Ring Coordinator Election

Overview

In the Ring Leader Election algorithm (Lann 1977, optimized by Chang & Roberts 1979), N processes are organized in a logical unidirectional ring where each node knows its successor. A node initiating an election sends ELECTION(myId) to its next live neighbor. Each receiving node compares the incoming ID with its own: in Chang-Roberts, it forwards the message only if incomingId > myId (or replaces it with myId if myId > incomingId and not yet participating). When a node receives its own ID back after a full circuit, it is elected leader and circulates a COORDINATOR announcement.

Core Concepts

unidirectional logical ringChang-Roberts ID suppressionfull-circuit terminationsuccessor skip on failure

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N) messages

Average

O(N log N) messages (Chang-Roberts)

Worst

O(N^2) messages

Space

O(1) per node (Chang-Roberts)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Ring Leader Election (Chang-Roberts) across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(N log N) messages (Chang-Roberts)

6.64 ms

60 FPS Frame-Safe (<16ms)~2.33M ops

Est. Worst-Case TimeO(N^2) messages

0.2 min

Offline Batch / Timeout Risk~5.00B ops

Est. Working MemoryO(1) per node (Chang-Roberts)

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

Use Ring Leader Election (Chang-Roberts) when processes are arranged in a logical ring topology or when you want bounded per-link message forwarding instead of all-to-all broadcasts.

When Not to Use

Avoid when ring links suffer high latency (since election latency is O(N) sequential hops) or when network partitions can sever the ring into disconnected arcs.

What It Does

Elects a unique leader in a unidirectional logical ring without requiring all-to-all broadcast connectivity
Suppresses smaller candidate IDs in Chang-Roberts so only O(N log N) messages are sent on average

Use Cases

Leader and token recovery in logical ring networks and DHT rings
Coordinator election when nodes only maintain point-to-point links to their ring successors
Distributed mutual exclusion token regeneration

Inputs

Logical ring of N processes with unique IDs and successor pointers

Outputs

Single elected coordinator with the maximum ID around the ring

Key Formulas (1)

Chang-Roberts Expected Messages

E_[M] = N · H_N + N approx N ln N + O(N)

E[M] = N * H_N + N approx N ln N + O(N)

Average message count when all N randomly ordered ring nodes initiate simultaneously, where H_N is the N-th harmonic number.

Pseudocode

1.On initiating election at node P: set P.participant = true and send ELECTION(P.id) to next live successor
2.On receiving ELECTION(candId) at node Q:
3. If candId > Q.id: set Q.participant = true and forward ELECTION(candId) to successor
4. Else if candId < Q.id and not Q.participant: set Q.participant = true and send ELECTION(Q.id) to successor (else drop message)
5. Else if candId == Q.id: Q is elected leader; set Q.participant = false and send COORDINATOR(Q.id) around the ring

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

On initiating election at node P: set P.participant = true and send ELECTION(P.id) to next live successor
On receiving ELECTION(candId) at node Q:
If candId > Q.id: set Q.participant = true and forward ELECTION(candId) to successor
Else if candId < Q.id and not Q.participant: set Q.participant = true and send ELECTION(Q.id) to successor (else drop message)
Else if candId == Q.id: Q is elected leader; set Q.participant = false and send COORDINATOR(Q.id) around the ring

Canonical Example

Input: Ring [3 -> 1 -> 7 -> 4 -> 3]; Nodes 3 and 1 initiate elections simultaneously
Output: Node 7 suppresses 3 and 1, forwards ELECTION(7) through 4 -> 3 -> 1 -> 7, and becomes leader
Explanation: Lower IDs (1 and 3) are swallowed when they reach higher-ID nodes, while 7 completes a full circuit of the ring.

Implementation Notes

Mark a boolean participant flag on each node so a node already in an election does not re-emit its own lower ID.

Common Pitfalls

Forwarding every candidate list unconditionally (Lann's O(N^2) variant) instead of dropping smaller IDs via Chang-Roberts comparison.
Stalling the ring when an immediate successor has crashed; each node must probe the next live successor in the ring list.

Interactive Mechanism Walkthrough & State Debugger

Iterative Convergence & State Trajectory

iteration kk = 0

state estimate x_k2.36828

residual |f(x_k)|3.92e-1

convergenceDescending gradient

Step 1 of 5: On initiating election at node P: set P.participant = true and send ELECTION(P.id) to next live successor

Notes

Concept entry for Ring Leader Election (Chang-Roberts): verified code implementation pending.

Sources (1)

What each reference supports for this entry.

Chang & Roberts (1979) — An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes

Paper

CACM paper proving O(N log N) average message complexity via candidate ID suppression on a ring.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Alternative toBully Algorithm

Distributed Systems · Core

Elects the highest-ID node using unidirectional ring forwarding instead of all-to-all higher-ID broadcasts.

Compare with this

Relationships

View full relationship page