--- title: "One election technique; consensus steps" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:election-technique-consensus" source: https://www.bctengineer.com/q/semester_7/distributed_system/election-technique-consensus site: BCT Engineering --- # One election technique; consensus steps Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2070 Asar, 5+3 marks - Video: [How do computers elect leaders? | Consensus and Leader Election Explained](https://www.youtube.com/watch?v=7qRVMKXo4M4) — A Dev' Story - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/election-technique-consensus - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question Explain any one election technique in Distributed System. Discuss with steps how consensus can be achieved in Distributed System. ## Short answer The Ring election algorithm: a process detecting failure sends an ELECTION message with its id around the logical ring; each successor appends its id, and the initiator picks the highest id from the returned list and circulates a COORDINATOR message. For consensus in a synchronous system with up to f crash faults, a f+1 round protocol is used: processes multicast their proposal sets, merge received values, and after round f+1 all decide identically, e.g., the minimum value. ## Answer #### 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the ring election algorithm, what does each receiving process do with the ELECTION message? A. Appends its own id and forwards it to its successor B. Replaces the list with its id C. Sends it to higher ids D. Discards it Answer: A. The list collects all live ids until it returns to the initiator. (Key point: Ring election step) 2. How is the coordinator chosen when the message returns to the initiator? A. The initiator always wins B. The highest id in the list is picked and announced by a COORDINATOR message C. The first id in the list wins D. The majority vote wins Answer: B. The initiator sees its own id, so the list holds all live processes. (Key point: Choosing winner) 3. How many messages does a ring election use? A. N^2 B. N-2 C. About 2N (N election plus N announcement) D. 3 sqrt(N) Answer: C. The election goes around once and the coordinator announcement goes around once. (Key point: Ring message cost) 4. Why does f+1 round consensus work? A. Every round has a crash B. Only a majority is needed C. A leader chooses the value D. At most f crash, so at least one round has no crash and all correct processes get the same set Answer: D. A crash-free round equalises the sets, so the decision rule gives the same result. (Key point: Why f+1 rounds) ## Related in Distributed System - [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× - [Need of consensus; Bully algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-bully) — Distributed System, chapter 6 - [Consensus; highly available service](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-high-availability) — 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 - [Autonomous vs distributed system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aautonomous-vs-distributed) — Distributed System, chapter 1 ## Related in other subjects - [Distributed system in big data example](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Adistributed-system-example) — Big Data Technologies, chapter 1 - [Short note: Distributed system implementation](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Ashort-note-distributed-implementation-issues) — Object Oriented Analysis and Design, chapter 4 - [Distributed system and Hadoop](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Adistributed-system-hadoop-voluminous-data) — Information System, chapter 8 - [Describe one classification system, limits](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Adescribe-classification-system-limits) — Soil Mechanics, chapter 3