Chang and Roberts algorithm

The Chang and Roberts algorithm is a ring-based coordinator election algorithm for distributed computing, published by Ernest Chang and Rosemary Roberts in 1979. It assumes that every process has a unique identification number and that the processes are arranged in a unidirectional ring in which each one sends to its clockwise neighbour. A process that notices there is no leader starts an election by sending a message carrying its own identifier around the ring, and every process that sends or forwards an election message marks itself as a participant. A process forwards a larger identifier unchanged, replaces a smaller identifier with its own if it is not yet a participant, and discards the message if it is already a participant with an identifier at least as large. When a process receives its own identifier back it becomes the leader and sends an elected message around the ring to announce the result. The algorithm works for any number of processes without any process knowing how many there are, and the participant state ensures that when several elections start at once only a single winner is announced.