Skip to main content

Need of consensus; Bully algorithm

Short answer

Consensus is required for agreeing on commit/abort, leader election, and replica consistency, with properties of termination, agreement, and validity. The Bully algorithm elects the highest-id process as coordinator: a process noticing failure sends ELECTION to higher ids; if no reply, it declares itself coordinator and sends COORDINATOR to all. For example, with ids 0–7, if 7 fails, 4 initiates and 6 eventually wins.

Why is consensus needed in DS? Explain Bully algorithm with suitable example.

Need for consensus

Consensus means that a group of processes, each proposing a value, agree on one common value, even if some fail. It is needed whenever processes must act together:

  • Deciding to commit or abort a distributed transaction.
  • Electing a leader/coordinator or deciding who holds a resource.
  • Keeping replicated state or logs identical (state machine replication, e.g. Paxos, Raft).
  • Agreeing on the order of messages (total order multicast), membership of a group, or time-critical decisions (e.g. whether to launch). Required properties: termination (every correct process decides), agreement (same value for all), validity/integrity (the value was proposed by some process).

Bully algorithm (leader election)

Each process has a unique id, knows all other ids, and the highest alive id wins.

  1. A process P detecting that the coordinator has failed sends ELECTION to all processes with higher ids.
  2. If none replies within timeout, P becomes coordinator and sends COORDINATOR to all.
  3. If a higher process replies OK, P stops its election. The higher one then holds its own election.
  4. The process with the highest id ends up with no answer, and announces itself.
  5. A recovered process starts an election; if highest, it "bullies" its way to coordinator.

Example: processes 0 to 7, coordinator 7 crashes. P4 detects it and sends ELECTION to 5, 6, 7. 5 and 6 reply OK. P5 sends to 6, 7; P6 sends to 7. P6 receives no answer from 7, so it sends COORDINATOR(6) to everyone. All agree that 6 is the new coordinator, thus reaching consensus on the leader.

Worst case O(N²) messages (lowest process starts); best case N−2.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 6 questions →