Chang and Roberts algorithm

Chang and Roberts^[1] is a ring-based election algorithm used to find a process with the largest identification. It is a useful method of election in decentralised distributed computing.

The algorithm

The algorithm assumes that each process has a Unique Identification (UID) and that the processes can arrange themselves 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. 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 election message 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.

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.

Assuming there are no failures this algorithm will finish. The algorithm works for any number of processes N, and does not require any process to know how many processes are in the ring.

Properties

The algorithm respects safety: a process will receive an elected message with its own UID only if his UID is greater than others', and only when all processes agree on the same UID. The algorithm also respects liveness. "Participant" and "not participant" states are used so that when multiple processes start an election at roughly the same time, only a single winner will be announced.

When there's a single process starting the election, the algorithm requires 3N-1 sequentially messages, in the worst case. Worst case is when the process starting the election is the immediate following to the one with greatest UID: it takes N-1 messages for the election message to reach it, then N messages for it to get back its own UID, then other N messages to send everyone in the ring the elected message.

This algorithm is not very fault tolerant. Fault tolerance can be increased If every process knows the whole topology, by introducing ACK messages and skipping faulty nodes on sending messages.

See also

• Leader election
• Bully algorithm

References

1. ^ Ernest Chang; Rosemary Roberts (1979), "An improved algorithm for decentralized extrema-finding in circular configurations of processes", Communications of the ACM (ACM) 22 (5): 281–283, doi:10.1145/359104.359108, http://portal.acm.org/citation.cfm?id=359108&dl=GUIDE&coll=GUIDE&CFID=66938712&CFTOKEN=59343102