Chang and Roberts algorithm

Chang and Roberts 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 Universal Identification (UID) and that the processes can arrange themselves in a unidirectional ring with a communication channel going to the clockwise and anticlockwise neighbour. The 2 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 marks itself as participant and creates an election message containing its UID. It then sends this message clockwise to its neighbour.
3. When a process receives an election message it compares the UID with its own, if the current process has a larger UID it replaces the one in the election message with its UID. The process then marks itself as participant and again forwards the election message in a clockwise direction.
4. If the process was already marked as participant when it receives an election message the procedure is different. In this case it will compare the UID as before but only forward the election message if it has needed to replace the UID.

The algorithm finishes when a process receives an election message containing its own UID. Then the second stage of the algorithm takes place

1. This 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 again forwards the elected message.
3. When the elected message reaches the newly elected process the election is over.

Assuming there are no failures this algorithm will finish. You may also notice that the participation and non-participation states are used so that when 2 or more processes start an election at roughly the same time only a single winner will be announced.