Chang and Roberts algorithm

Chang and Roberts is a ring-based election algorithm used to find the 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 process can arrange themselfs in a unidirectional ring.

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 recieves 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.