Course contentsShow
← Computer Science
Lesson 2679 of 2,87259. Consensus and ReplicationFree lesson

Quorums and Majority Requirements

Understanding why Paxos requires majority quorums and how this ensures safety despite failures.

Understanding Quorums and Majority Requirements in Paxos

You'll learn why Paxos needs a majority of acceptors to agree—and how this simple rule guarantees correctness even when nodes crash.

The Core Idea

In Paxos, both phases require responses from a quorum—a majority of acceptors. Why majority? Because any two majorities must overlap by at least one acceptor. This overlap is the secret to Paxos's safety.

Imagine 5 acceptors. A majority is 3. If one proposer gets promises from acceptors A, B, and C, and another proposer later gets promises from C, D, and E, they share acceptor C. This shared acceptor carries information forward, preventing conflicting decisions.

Why Majority Prevents Conflicts

When a proposer enters Phase 1 with a higher proposal number, it must collect promises from a majority. At least one acceptor in this new majority must have been in any previous successful majority. This guarantees the new proposer learns about any value that might have been chosen.

Without this overlap, two disjoint groups could accept different values for the same decision, violating safety. The majority requirement ensures information propagation: past decisions can't be lost or ignored.

Tolerating Failures

With N acceptors, you can tolerate up to ⌊(N-1)/2⌋ failures and still make progress. With 5 acceptors (majority = 3), you tolerate 2 failures. With 7 (majority = 4), you tolerate 3 failures.

The trade-off: requiring more nodes for quorums increases resilience but also increases the chance that some node in the quorum is slow or unreachable, potentially delaying consensus.

Key Takeaway:
Paxos requires majority quorums because any two majorities must overlap, guaranteeing that no conflicting values can be chosen and that all past decisions are visible to future proposals.