The Chang and Roberts algorithm is a ring-based coordinator election algorithm, employed in distributed computing.

We assume that:

• Asynchronous network
• No failure occurs
• Each process has a unique identification (UID)

Algorithm Description

Processes are arranged in a unidirectional ring with a communication channel going from each process to the clockwise neighbour. The two part algorithm can be described as follows:

1. Part One
   1. Initially each process in the ring is marked as non-participant
   2. A process that notices a lack of leader starts an election. It creates an  containing its UID. It then sends this message clockwise to its neighbour.
   3. Every time a process sends or forwards an election message, the process also marks itself as a participant.
   4. When a process receives an election message it compares the UID in the message with its own UID.
      1. If the UID in the election message is larger, the process unconditionally forwards the election message in a clockwise direction.
      2. If the UID in the election message is smaller, and the process is not yet a participant, the process replaces the UID in the message with its own UID, sends the updated election message in a clockwise direction.
      3. If the UID in the election message is smaller, and the process is already a participant (i.e., the process has already sent out an election message with a UID at least as large as its own UID), the process discards the election message.
      4. If the UID in the incoming election message is the same as the UID of the process, that process starts acting as the leader.
2. Part Two - When a process starts acting as the leader, it begins the second stage of the algorithm.
   1. The leader process marks itself as  non-participant and sends an  elected message to its neighbour announcing its election and UID.
   2. When a process receives an elected message, it marks itself as non-participant, records the elected UID, and forwards the elected message unchanged.
   3. When the  elected message reaches the newly elected leader, the leader discards that message, and the election is over.

Illusion of Ring Based Election

Properties and Performance

• E1: Safety
  • Met as all identifiers are considered
  • Even if elections start simultaneously the smaller identifier cannot pass the larger identifier
• E2: Liveness
  • Met due to reliable communication
• Bandwidth utilisation
  • Best-case behaviour
    • $2N$ messages in total and sequentially
      • $N$ for the message with largest UID being passed sequentially through the ring and reaching the process which sent it
      • Another $N$ for elected messages
  • Worst-case behaviour
    • $3N – 1$ messages in total and sequentially
      • At most $2N – 1$ messages for electing the left-hand neighbour
      • Another $N$ elected messages