--- title: "Central coordinator election; consensus" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:election-central-consensus" source: https://www.bctengineer.com/q/semester_7/distributed_system/election-central-consensus site: BCT Engineering --- # Central coordinator election; consensus Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2076 Chaitra, 5+5 marks - Video: [Distributed Consensus: Definition & Properties of Consensus, Steps & Fault-Tolerance in Consen. ALG.](https://www.youtube.com/watch?v=wMrLPtyU_dE) — Dr Nitin Naik - Aston University, UK - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/election-central-consensus - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question How does a new coordinator elect in executing central coordinator algorithm? How to come to consensus in DS? Explain. ## Short answer In the central coordinator algorithm, a new coordinator is elected using Bully: the process detecting the failure sends ELECTION to higher ids, and the highest alive takes over after receiving no response, then sends COORDINATOR. Consensus is achieved by running f+1 synchronous rounds; each process multicasts its set of values, merges received values, and after the final round decides on the same value (e.g., the minimum). ## Answer #### Electing a new coordinator in the central coordinator algorithm In the centralised mutual exclusion algorithm, one process grants permission to enter the critical section. When it is found to be down (a request is not answered within a timeout), a new coordinator is elected by an election algorithm. Using the **bully algorithm**: 1. The process P that notices the failure sends ELECTION to all processes with a higher id. 2. A live higher process replies OK; P gives up. The higher process starts its own election in the same way. 3. If no one answers, P wins and sends COORDINATOR to all others. 4. All processes now send their requests to the new coordinator. Since the new coordinator has no queue or state, the processes holding a pending request must resend it; the new coordinator rebuilds the queue and grants the CS to the first request. A recovering process also starts an election. Alternatively in the **ring algorithm**: ELECTION(list of ids) circulates around the logical ring; the initiator picks the highest id and circulates COORDINATOR. #### Consensus in a distributed system Consensus is for processes to agree on one value, even in presence of failures. Requirements: termination, agreement, validity. Steps (synchronous system with up to f crash failures; Dolev-Strong style): 1. Each process Pi starts with a proposed value and a set Values = {its proposal}. 2. The algorithm runs **f+1 rounds**. In each round, each process multicasts the values in its set that it has not yet sent, to all others (reliable multicast). 3. On receiving, a process adds new values to its set. 4. After round f+1, each process decides on a value by a fixed rule, e.g. the minimum of its set (or majority). At least one round has no crash, so all correct processes end with the same set, and decide the same value. For asynchronous systems with crashes, exact consensus is impossible (FLP result), so algorithms like **Paxos** or **Raft** use leader election and majority quorums; for Byzantine failures, at least 3f+1 processes are required to tolerate f faulty ones. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a failed coordinator detected in the centralized mutual exclusion algorithm? A. A request is not answered within a timeout B. The token is missing C. A logical clock overflows D. All processes vote Answer: A. No reply within timeout signals a down coordinator, starting an election. (Key point: Trigger of election) 2. After election, why must processes with pending requests resend them? A. The old coordinator keeps the queue B. The new coordinator has no queue or state C. Requests expire immediately D. The ring token was lost Answer: B. The new coordinator rebuilds its queue from resent requests. (Key point: New coordinator state) 3. In the synchronous crash-failure consensus algorithm with at most f crashes, how many rounds are run? A. f B. 2f C. f+1 D. 3f+1 Answer: C. With f+1 rounds, at least one round has no crash, so all correct processes get the same set. (Key point: Rounds for consensus) 4. Which statement is correct about harder settings? A. Asynchronous consensus is trivial B. Byzantine faults need only f+1 processes C. Raft works only in synchronous systems D. Asynchronous consensus with crashes is impossible exactly (FLP), so Paxos/Raft are used; Byzantine needs 3f+1 processes Answer: D. FLP shows impossibility; practical algorithms use leaders and majority quorums. (Key point: FLP and Byzantine) ## Related in Distributed System - [One election technique; consensus steps](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-technique-consensus) — Distributed System, chapter 6 - [Need of consensus; Bully algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-bully) — 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 - [Bully algorithm vs ring algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-bully-ring) — Distributed System, chapter 6 ## Related in other subjects - [Upwind versus central scheme for convection](https://www.bctengineer.com/question.md?key=semester_7%2Fapplied_computational_fluid_dynamics%3Aupwind-central-convection-numerical) — Applied Computational Fluid Dynamics, chapter 3