The Ring Algorithm

Imagine a group of people sitting in a circle, passing a note around. Each person writes their name on the note if they want to be leader, and when the note comes back to its originator, the person with the 'highest' name on the list wins. This orderly, sequential approach is the essence of the Ring Algorithm.

Proposed by Chang and Roberts in 1979, the Ring Algorithm takes a fundamentally different approach from the Bully Algorithm. Instead of broadcasting challenges to all higher-priority nodes simultaneously, the Ring Algorithm arranges nodes in a logical ring topology and passes election messages sequentially around the ring. Each node contributes its candidacy, and after a complete circuit, the winner is determined.

This sequential approach trades latency for simplicity and reduced message burst. Where Bully floods the network with O(n²) messages in parallel, the Ring Algorithm sends O(n) messages in sequence.

Before diving into the algorithm, we must understand the logical ring topology that underpins it. This is a crucial concept that distinguishes the Ring Algorithm from other approaches.

Physical vs Logical Topology:

The physical network connecting nodes might be any structure—fully connected, mesh, star, or even the internet. The logical ring is an overlay abstraction where nodes are arranged in a conceptual circle:

• Each node knows its successor (next node in the ring)
• Messages flow in one direction around the ring
• The ring is unidirectional: node A sends to B, B sends to C, C sends to A
• Any node can initiate communication around the ring

Constructing the logical ring:

The logical ring is typically constructed by ordering nodes by their identifiers and connecting them cyclically:

1. Sort all node identifiers: [1, 3, 5, 7, 9]
2. Connect sequentially: 1 → 3 → 5 → 7 → 9 → 1
3. Each node stores only its successor's address

Example ring with 5 nodes:

        Node 1
       ↗      ↘
     Node 9    Node 3
       ↑          ↓
     Node 7 ← Node 5

Messages always flow clockwise (in this illustration). Node 3's successor is Node 5; Node 9's successor is Node 1 (wrapping around).

Why use a ring topology?

The ring provides several algorithmic benefits:

1. Bounded message paths: Messages travel at most n hops (once around the ring)
2. Simple routing: Each node needs to know only its successor, not all nodes
3. Natural termination: An election completes when the message returns to its origin
4. Space efficiency: O(1) routing information per node vs O(n) for full knowledge

However, rings also have drawbacks: a single node failure breaks the ring, and sequential message passing increases latency compared to parallel communication.

The Ring Algorithm uses two types of messages:

1. ELECTION — Carries a list of candidates (initially just the initiator)
2. COORDINATOR — Announces the elected leader (sent after election completes)

Election initiation:

When a node P detects that the leader has failed (via heartbeat timeout), it initiates an election:

1. P marks itself as participating in an election
2. P creates an ELECTION message containing its own identifier: [P]
3. P sends this message to its successor in the ring

ELECTION message handling:

When a node Q receives an ELECTION message:

1. Check if Q is already in the candidate list:

   • If YES: The message has completed a full circuit. Q determines the winner (highest ID in the list) and initiates the COORDINATOR phase.
   • If NO: Continue to step 2.

2. Add Q to the candidate list:

   • Q appends its own identifier to the list: [..., Q]
   • Q marks itself as participating

3. Forward the message:

   • Q sends the updated ELECTION message to its successor

COORDINATOR message handling:

Once election completes (message returns to originator):

1. The winner is the node with the highest identifier in the candidate list
2. The detecting node sends a COORDINATOR message around the ring announcing the winner
3. Each node receives COORDINATOR, notes the new leader, and forwards the message
4. When COORDINATOR returns to its originator, election is complete

Let's trace through a complete election example. Consider a ring of 5 nodes with identifiers 2, 4, 6, 8, 10 arranged as: 2 → 4 → 6 → 8 → 10 → 2.

Initial state:

• Node 10 is the current leader
• Ring order: 2 → 4 → 6 → 8 → 10 → (back to 2)
• Node 10 crashes

Key observations:

1. Sequential processing: Unlike Bully's parallel broadcast, Ring sends one message at a time around the ring. This is slower but more orderly.

2. Candidate accumulation: The ELECTION message grows as it travels, accumulating all participating nodes' identifiers.

3. Natural termination: The election ends when the message returns to its originator—simple and elegant.

4. Failure handling required: When Node 10 (crashed) couldn't receive the message, the ring was broken. Step 4b shows failure handling—Node 8 must detect the failure and skip to the next live node.

5. Two complete circuits: ELECTION goes around once, then COORDINATOR goes around once. Total: 2n messages for a successful election (in the basic algorithm).

The Ring Algorithm's complexity characteristics differ significantly from the Bully Algorithm. Let's analyze both message and time complexity.

Message complexity:

Best case (single initiator, no failures):

• ELECTION phase: n messages (one full circuit)
• COORDINATOR phase: n messages (one full circuit)
• Total: 2n = O(n) messages

This is a dramatic improvement over Bully's O(n²) worst case.

Worst case (all nodes initiate simultaneously):

• Each of n nodes starts its own ELECTION message
• Each ELECTION travels n hops: n² messages
• If we suppress redundant COORDINATOR phases: add n more
• Total: O(n²) messages

However, this worst case is less likely than Bully's because:

1. Only one node typically detects failure first (they timeout at different times)
2. Nodes that receive an ELECTION message can refrain from starting their own
3. Message suppression can eliminate redundant circuits

Time complexity:

The Ring Algorithm's time complexity is its significant weakness:

• Each message hop incurs network delay d
• Complete circuit: n × d
• Two circuits (ELECTION + COORDINATOR): 2n × d
• Total election time: O(n × d)

If n = 10 and d = 10ms, the election takes approximately 200ms. For n = 100 and d = 10ms, it's 2 seconds. Compare this to Bully, where (in the best case) election completes in a single timeout period regardless of cluster size.

This latency characteristic makes Ring unsuitable for systems requiring fast failover.

Node failures in the Ring Algorithm are particularly problematic because they break the ring structure. A single failed node stops message circulation unless the algorithm handles it. Let's examine failure scenarios and solutions.

Solution 1: Successor lists

Each node maintains a list of its next k successors rather than just one. If the immediate successor fails:

1. Node detects failure (timeout on acknowledgment)
2. Node sends to second successor
3. If second fails, try third, and so on
4. Eventually find a live successor or determine ring is too broken

Example with k=3:

• Node 4's successors: [6, 8, 10]
• Node 6 fails → send to 8
• Node 8 also fails → send to 10

This handles up to k-1 consecutive failures.

Solution 2: Ring repair

When a failure is detected, repair the ring before continuing:

1. Node A detects successor B has failed
2. A queries known nodes: 'Who is B's successor?'
3. A connects to B's successor C, bypassing B
4. Ring is repaired: A → C

This is more complex but maintains a clean ring structure.

Solution 3: Timeout and restart

The simplest (but slowest) approach:

1. If forwarding fails, wait for timeout
2. Rebuild ring from scratch (re-query group membership)
3. Restart election on new ring

This handles all failure scenarios but may take significant time.

When multiple nodes detect the leader failure simultaneously, they may all initiate elections. Unlike Bully's cascading takeover, Ring can have multiple ELECTION messages circulating the ring at once. This creates complexity that must be handled correctly.

Scenario: Three nodes start elections simultaneously

Nodes 2, 6, and 8 all detect failure and initiate elections:

• Message A from Node 2: [2]
• Message B from Node 6: [6]
• Message C from Node 8: [8]

All three messages travel around the ring. Without coordination:

• Message A arrives at Node 2 with candidates [2, 4, 6, 8, 10]
• Message B arrives at Node 6 with candidates [6, 8, 10, 2, 4]
• Message C arrives at Node 8 with candidates [8, 10, 2, 4, 6]

All three have the same candidates (different order), and all three compute the same winner (10, if 10 hadn't crashed). But now three COORDINATOR messages are sent!

The Chang-Roberts optimization:

The original Chang-Roberts algorithm includes an optimization for concurrent elections:

1. When a node receives an ELECTION message with candidates:

   • If the node's ID is greater than all candidates, add self and forward
   • If the node's ID is less than the max candidate, don't add self (already a better candidate)
   • If the node sees its own ID and it's the max, it has won

2. This way, lower-priority candidates drop out as the message travels. By the time the message returns, only the winner's ID matters.

3. Concurrent elections naturally merge: the message carrying the highest ID 'wins' and absorbs other elections.

Having now studied both the Bully and Ring algorithms, we can make an informed comparison. Each algorithm has distinct characteristics that make it suitable for different scenarios.