Quorum Intersection, Ballots, and Commit Evidence

By the end of this lesson, you will be able to...

• Calculate why two majorities in a five-replica crash-fault cluster must overlap.

• Trace how a later ballot learns and preserves an earlier accepted value for one slot.

• Distinguish quorum evidence from a vague claim that an entry is simply “committed.”

Idea in one sentence: Quorums keep safety because every later successful decision path must meet evidence from an earlier one, and ballots force the later path to respect that evidence.

Core Insight

Atlas has five acceptors, A through E, and must choose one value for slot 57. Two coordinators may race after a network delay. The obvious worry is that one coordinator chooses X while another chooses Y for the same slot.

The first mental model is “a majority is safe because it is lots of machines.” It is incomplete. The useful fact is mathematical: two groups large enough to decide cannot be disjoint. Their overlap can carry evidence from the first attempt to the next one.

But overlap alone is not magic. The shared acceptor must durably report what it accepted, and the newer coordinator must have a rule that uses that report. A ballot number orders attempts; it does not grant the new coordinator permission to forget the earlier value.

This lesson uses a small, single-slot, crash-fault teaching model close to Paxos. A production replicated log adds prefixes, membership rules, persistence details, and service-level acknowledgement rules. The core reasoning survives: safety is a chain of intersection, durable evidence, and an obligation to preserve it.

The Pattern We Want to Name

For N acceptors, a majority quorum contains:

q = floor(N / 2) + 1

Atlas has N = 5, so q = 3. Take any two majorities, Q1 and Q2. The smallest possible overlap is:

|Q1 ∩ Q2| >= |Q1| + |Q2| - N
           >= 3 + 3 - 5
           >= 1

For example:

Q1 = {A, B, C}
Q2 = {C, D, E}
Q1 ∩ Q2 = {C}

The calculation does not say every replica sees every decision. It says a later majority cannot avoid every participant in an earlier majority. If C recorded relevant evidence during the first attempt, then C is the witness that the later attempt must encounter.

This is the plain meaning of quorum intersection: decision groups overlap in at least one participant. It is a structural property, not a timeout setting or a promise that messages arrive quickly.

A Tiny Example: One Slot, Two Values

Assume slot 57 is empty. Coordinator P uses ballot 7 and proposes value X. The following trace uses illustrative ballot numbers and acceptor sets.

The intermediate state at step 6 is the hard part. Q is newer, but “newer” only tells acceptors which attempt is current. It does not answer which value belongs in the slot. The prepare responses answer that second question. In Paxos, a proposer that receives accepted values chooses the value associated with the highest accepted ballot it learned. In this trace that value is X.

The Initial Model: A New Ballot Can Choose Anything

It is tempting to reason this way:

ballot 8 is greater than ballot 7
therefore ballot 8 may choose Y

That rule would make ballot numbers a way to overwrite history. It fails because X already has majority evidence. If Q could ignore C and propose Y, A, B, and C could later accept Y at ballot 8; the same slot could appear to have majorities for both values. The number ordering would not rescue safety.

The stronger rule has two parts:

1. An acceptor that promises ballot 8 rejects older accept requests such as ballot 7.
2. A coordinator at ballot 8 first collects a quorum of promises and accepted records, then adopts the required prior value before asking acceptors to accept.

The first part blocks stale attempts. The second part preserves the value that prior evidence protects. Both are necessary. Intersection without a reporting rule is just a set calculation. Reporting without an adoption rule is evidence that a buggy coordinator can ignore.

Working Through the Definition

The majority formula gives two properties in the five-node model:

These properties are related but not identical. A five-node cluster split A,B versus C,D,E can progress only on the three-node side. A split where no side has three nodes cannot safely choose a new value. Waiting is a liveness cost accepted to avoid two independent decisions.

The trade-off is clear: majority quorums create the overlap that preserves safety, but they require enough reachable replicas. A smaller decision group may improve availability in some failure pattern but loses safety unless the protocol proves that its decision quorum still intersects every earlier evidence-gathering quorum that matters.

This matters for flexible quorum designs. The right question is not “must every quorum be a majority?” It is “does every phase that can create evidence intersect every phase that later needs to learn that evidence?” For a simple fixed five-node majority protocol, using three in both phases is an easy answer. Other designs need a more careful proof.

What Commit Evidence Actually Means

“Committed” can describe different boundaries in different systems. Avoid treating it as a magic label.

In this lesson's single-decree Paxos model, majority acceptance is evidence that X is chosen for the slot. A later valid prepare quorum must find enough accepted evidence to preserve the chosen value. In a replicated-log implementation, an entry may need a particular log-term, configuration, and replication rule before the protocol calls it committed. A service may wait even longer, until deterministic application produces the client result discussed in the previous lesson.

So use a precise design-review question:

What durable records exist now, which quorum rule covers them,
and which later protocol step is forced to preserve their meaning?

Weak answers reveal false evidence:

• “The leader remembers it.” A leader can crash or be replaced.
• “One follower has it.” A single copy may not intersect the next decision path.
• “The client timed out.” A timeout reports uncertainty, not a distributed decision.
• “Most replicas logged something.” The record must be durable and count under the current protocol and membership rule.

Commit evidence is therefore not a dashboard impression. It is a claim that can survive a crash, leadership change, and later successful attempt because those later steps are constrained to encounter it.

Edge Cases and Limits

The five-node calculation assumes a fixed membership and crash failures. It does not by itself handle Byzantine nodes that lie about records; those systems use stronger assumptions and often cryptographic quorum certificates. It also does not prove a client has received a response, that all replicas have applied the value, or that an external side effect occurred once.

Reconfiguration needs particular care. If an old configuration and a new configuration could decide independently without overlap, the same safety argument breaks. Safe reconfiguration protocols arrange an overlap or joint phase so evidence cannot disappear during the transition.

The signal to watch in an implementation is not merely quorum size. Inspect whether acceptor or log metadata survives restart, whether promise/term changes are durable before they affect replies, whether quorum membership is the intended configuration, and whether an election or prepare response includes the evidence a new leader needs.

Practice: Trace the Second Attempt

Check: In the trace, Q contacts C, D, and E. C reports accepted (7, X), while D reports accepted (6, Y), and E reports no accepted value. Which value should Q carry in ballot 8?

Think first, then reveal.

Answer: Q carries X, the value tied to the highest accepted ballot it learned. The rule does not choose the most common response or the coordinator's preferred value. It preserves the evidence that could already constrain the slot.

Transfer Challenge: Review a Faster Quorum Claim

A team proposes a five-node protocol with two-node write quorums and three-node recovery quorums. They say, “recovery has a majority, so writes can use any pair.”

Review the claim using the model from this lesson.

A good answer should mention:

• a two-node write quorum such as {A, B} can be disjoint from a three-node recovery quorum such as {C, D, E};
• the recovery path could therefore miss the write's evidence entirely;
• this design is unsafe unless a different protocol rule guarantees the required cross-phase intersection;
• the team must state which sets create durable decision evidence and which future sets must discover it, then prove those sets intersect.

Connections

The previous lesson showed why replicas apply only committed history. This lesson explains why a later leader cannot replace the history that the protocol has already made durable.

The next lesson turns the same issue toward reads: a controller that acts on a lease or leader read needs evidence that its authority is still current.

Resources

• [PAPER] Paxos Made Simple — Focus: Prepare responses, accepted values, and the rule for choosing a value in a later proposal.
• [PAPER] In Search of an Understandable Consensus Algorithm — Focus: Terms, elections, and the log conditions that preserve committed entries.
• [PAPER] Viewstamped Replication Revisited — Focus: View changes and the evidence needed to preserve committed operations.

Key Takeaways

• Majority safety comes from intersection: in a five-node cluster, any two three-node quorums share at least one node.
• The shared node must keep and report durable accepted evidence; the later coordinator must obey an adoption rule.
• A higher ballot blocks stale attempts but does not allow a new coordinator to choose any value it wants.
• Commit evidence is protocol-specific proof that later valid steps are forced to preserve a decision, not a timeout or a single node's memory.
• Quorum choices trade availability for the intersection needed to preserve safety, especially across membership changes.