--- title: "Need of consensus; Bully algorithm" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:consensus-bully" source: https://www.bctengineer.com/q/semester_7/distributed_system/consensus-bully site: BCT Engineering --- # Need of consensus; Bully algorithm Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2074 Chaitra, 2+6 marks - Video: [Bully Algorithm | Introduction | Distributed System | Lec-28 | Bhanu Priya](https://www.youtube.com/watch?v=z6PQGVcKXrk) — Education 4u - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/consensus-bully - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question Why is consensus needed in DS? Explain Bully algorithm with suitable example. ## 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. ## Answer #### 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which are the required properties of consensus? A. Termination, agreement and validity B. Safety, locality and ordering C. Atomicity, isolation and durability D. Integrity, timeliness and fairness Answer: A. Every correct process decides, all decide the same, and the value was proposed by some process. (Key point: Consensus properties) 2. Which is a use of consensus? A. Compressing messages B. Deciding commit or abort of a distributed transaction C. Allocating IP addresses D. Measuring clock drift Answer: B. Participants must all commit or all abort; consensus also covers leader election and replicated logs. (Key point: Need for consensus) 3. In the bully algorithm, who ends up as coordinator? A. The lowest-id process B. The process that detected the failure C. The highest-id process that is alive D. A randomly chosen process Answer: C. The highest alive process gets no OK from higher ones and announces itself. (Key point: Bully winner) 4. Processes 0-7, coordinator 7 crashes, P4 starts. Who becomes coordinator and why? A. P4, since it detected the crash B. P5, since it replies first C. P0, since it has the lowest id D. P6, because it gets no answer from 7 and sends COORDINATOR(6) Answer: D. 6 is the highest live id; 5 and 6 reply OK to 4, then 6 receives no response from 7. (Key point: Bully example) ## Related in Distributed System - [Bully algorithm vs ring algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-bully-ring) — Distributed System, chapter 6 - [Need of multicast and consensus](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amulticast-consensus-need) — Distributed System, chapter 6 - [Central coordinator election; consensus](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-central-consensus) — Distributed System, chapter 6 - [Election algorithm need and example](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-scenario) — Distributed System, chapter 6, asked 2× - [Consensus; highly available service](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-high-availability) — Distributed System, chapter 6 - [Cristian's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acristian-algorithm) — Distributed System, chapter 5, asked 3× ## Related in other subjects - [Need for replacement algorithm in cache](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-why) — Computer Organization and Architecture, chapter 6 - [Need for non-uniform quantization; one algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Anonuniform-quantization-algorithm) — Communication Systems, chapter 4 - [Why the Fourier transform is needed](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Awhy-fourier-transform-needed) — Data Communication, chapter 3, asked 2× - [Banker's algorithm, 5 processes, 4 resources](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Abanker-five-process-four-resource) — Operating System, chapter 7