Leader Election: LeLann, Chang and Roberts algorithm (LCR)

This algorithm is for ring networks. Each message goes in the network from one process to another, ie no broadcasting. This means that each process knows exactly about only one other process - it's neighbor. This could be imagined as linked list.

Algorithm complexity is better than in bully algorithm, because its worst case is O(N^2), which happens only if hosts are organized into the network using by increasing (or decreasing, depends on the what extreme is used) order of their UIDs.
Algorithm is pretty simple:

1. Some process P notes a lack of the leader and initiates the election. It creates election message and send it to the next process in the ring. P sends own UID in the message, so it is a candidate.
2. Each process that receives election message forwards the message to the next peer and marks iteself as election participant.
3. When process receives the election message it compares UID in the message with own UID. If own UID is larger, it means that this host has more chances to become a leader. So it does not send the original election message with received UID, but sends own election message with own UID. Now it's a candidate.
4. When candidate receives the election message with different UID, it means that it lost the election and is not a candidate but only participant.
5. When candidate process receives the election message with own UID, it means that the message made a cirtle in the network ring, and there was no process with larger UID. This process can become a leader. Actually, the process starts acting as a leader.
6. When process becomes a leader, it has to notify others that it's a leader now. It marks itself as non-participant and sends elected message. Every next process that receivs the message marks itself as non-participant and forwards the message to next peer. When the message reaches the leader, it discards the message, so it's removed from the network.
7. Election completed.

The downside of this algorithm is in the structure of network - it's a ring. Need to make sure that if a lance in the ring is down, the ring is still connected.