One election technique; consensus steps

Election technique: Ring algorithm

Used to choose a new coordinator. Processes are arranged in a logical ring, and each knows its successor (and the next ones in case of crashes).

1. A process P detecting that the coordinator has failed creates an ELECTION message with its own id and sends it to its successor. If the successor is down, it skips to the next live one.
2. Each process that receives the message adds its own id to the list and forwards it to its successor.
3. When the message returns to P (it sees its own id), the list contains all live processes. P picks the process with the highest id.
4. P sends a COORDINATOR message with the winner's id around the ring; all processes record the new coordinator. The message circulates once more and stops when it reaches P. If two processes start together, both messages result in the same winner, so there is no conflict.

Messages: about 2N per election (N for election, N for announcement).

Achieving consensus

The goal is that all correct processes agree on the same value (agreement), every correct process decides (termination), and the decided value was proposed by some process (validity).

Steps (f crash faults, synchronous system):

1. Each process starts with its proposal in a set.
2. Run f+1 rounds. In each round, each process sends the new values to all others by multicast.
3. Receivers merge the received values into their sets.
4. After f+1 rounds, each process decides, e.g., the minimum value in its set. Since at most f processes crash, at least one round has no crash, so every correct process gets the same set.

In practice, asynchronous systems use Paxos/Raft: a leader proposes a value, a majority of acceptors accept it, and the value is then committed. Byzantine faults need 3f+1 processes.