Skip to main content

Central coordinator election; consensus

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).

How does a new coordinator elect in executing central coordinator algorithm? How to come to consensus in DS? Explain.

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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 6 questions →