--- title: "Consensus; highly available service" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:consensus-high-availability" source: https://www.bctengineer.com/q/semester_7/distributed_system/consensus-high-availability site: BCT Engineering --- # Consensus; highly available service Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2071 Shrawan, 3+5 marks - Video: [DS42: Highly Available Service | Transaction with Replicated data in Distributed System](https://www.youtube.com/watch?v=HYb9OOXQJPY) — University Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/consensus-high-availability - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question How to come to consensus in DS? Discuss with an approach, how do you make the distributed system service highly available? ## Short answer Consensus is reached via a synchronous f+1 round protocol: each process starts with its proposal in a set, multicasts unsent values each round, merges received values, and after the final round all decide the same value (e.g., minimum). High availability is achieved through replication: multiple servers with a front-end, primary-backup failover, and heartbeat detection; with n replicas each having failure probability p, availability becomes 1 − p^n (e.g., 99.9875% for p=0.05, n=3). ## Answer #### Reaching consensus Consensus means that all correct processes agree on the same value, though some may fail. Properties: **termination** (every correct process decides), **agreement** (same decision), **validity** (decided value was proposed). Approach (synchronous system, up to f crash failures): 1. Every process Pi holds a proposed value in its set Vi. 2. For f+1 rounds, each process multicasts values in its set that it has not sent before. 3. Each process merges the values it receives into Vi. 4. After round f+1, each process decides by the same function (e.g. minimum value or majority). In at least one of the f+1 rounds no process crashes, and in that round all correct processes learn the same values, so they end up with the same set and agree. For asynchronous systems with crash failures, Paxos/Raft reach agreement by electing a leader and obtaining acceptance from a majority quorum; for Byzantine faults 3f+1 processes are needed. #### Making a service highly available A service is highly available if clients get a response with high probability even when some servers fail. The approach is **replication**: 1. Keep copies of the data and service on several servers, preferably on different machines, networks and sites. 2. A **front end** (proxy) sends client requests to the replicas, and may send to several, taking the first reply. 3. **Primary-backup** or **active replication** keeps replicas consistent; with the primary down, a backup is promoted by an election/consensus (e.g. bully algorithm) without service interruption. 4. Use of heartbeat failure detection, automatic failover, load balancing, and (lazy) update propagation, as in the gossip architecture, where any replica can respond. 5. Availability with n replicas each with failure probability p is 1 − pⁿ; e.g. with p = 0.05 and 3 replicas: 1 − 0.000125 = 99.9875%. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the f-crash synchronous consensus approach, what does a process do each round? A. Multicasts values not yet sent and merges received values into its set B. Sends only to its successor C. Waits for a token D. Votes for the highest id Answer: A. After f+1 rounds, all correct sets are equal and a common function decides. (Key point: Consensus rounds) 2. What is the basic approach to make a service highly available? A. A single powerful server B. Replication on several servers, with failover to a backup C. Reducing the number of clients D. Using longer timeouts only Answer: B. Copies of the service keep it running when a server fails. (Key point: Availability technique) 3. With 3 replicas, each down with probability 0.05 independently, availability is A. 0.05^3 B. 3 x 0.95 C. 1 - 0.05^3 = 99.9875% D. 1 - 0.05 x 3 = 85% Answer: C. The service is unavailable only if all n replicas fail: p^n = 0.000125. (Key point: Availability formula) 4. When the primary fails in primary-backup, how is service kept? A. Clients wait for repair B. All backups become primary C. The oldest request is deleted D. Heartbeats detect it and a backup is promoted via election/consensus Answer: D. Failure detection plus election gives a single new primary. (Key point: Failover) ## 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 - [Need of consensus; Bully algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-bully) — Distributed System, chapter 6 - [DS as a single coherent system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Asingle-coherent-system) — Distributed System, chapter 1, asked 2× - [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 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 - [Unfair service centre simulation](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aunfair-service-centre-simulation) — Data Structure and Algorithm, chapter 2