Distributed System (BSc CSIT, CSC462): the questions likely to come

Election Algorithms

An election algorithm chooses a single process to act as coordinator (e.g., the central lock manager, sequencer or master). Any process may start an election; when it finishes every non-crashed process must agree on the new coordinator, usually the one with the highest process id (or priority). Elections are needed after the current coordinator crashes.

1. Bully Algorithm (Garcia-Molina)

Assumes each process knows the ids of all others and can message them; uses timeouts to detect crashes.

When a process P notices the coordinator has failed (or it just recovered):

1. P sends an ELECTION message to all processes with higher ids.
2. If no higher process answers within the timeout, P wins and sends a COORDINATOR message to all lower processes announcing itself.
3. If a higher process answers with OK, P drops out; the higher process now holds its own election.
4. Eventually the highest-id live process becomes coordinator and announces it.

Example: processes 1..7, with 7 the old coordinator. 7 crashes; 4 notices and sends ELECTION to 5,6,7. 5 and 6 reply OK and hold their own elections. 6 sends ELECTION to 7 (no reply) and finds itself highest, so 6 announces itself coordinator to all. The highest survivor 'bullies' the rest — hence the name.

• Worst-case messages: $O(N^2)$.

2. Ring Algorithm

Processes form a logical ring; each knows its successor. No token is used.

1. A process that detects coordinator failure builds an ELECTION message containing its own id and sends it to its successor (skipping dead nodes).
2. Each process appends its id and forwards the message around the ring.
3. When the message returns to the initiator (it sees its own id in the list), the highest id in the list is the new coordinator.
4. The initiator circulates a COORDINATOR message naming the winner so all processes update.

Example: ring 1→2→3→4→5→6→7→1, coordinator 7 crashes. Process 2 starts an election with {2}; it becomes {2,3,4,5,6} as it travels (7 skipped) and returns to 2. Max = 6, so 6 is the new coordinator, announced via a second pass.

• Messages: about $2N$ ($N$ for the election list + $N$ for the announcement).

Comparison

Both guarantee that all live processes agree on the same coordinator after the election completes.