Quorum Intersection, Ballots, and Commit Evidence

The core idea: Quorum intersection makes safety portable across leadership changes because later attempts must encounter evidence from earlier attempts, with a trade-off between availability, quorum size, and the discipline required to preserve commit evidence.

Core Insight

Imagine a five-node cluster where two clients race to write different values for the same log slot. One client reaches nodes A, B, and C. The other reaches C, D, and E. Node C is the overlap. That overlap is not an implementation detail; it is the safety hinge.

Consensus protocols use quorums so that successful decision attempts cannot be completely independent. Any later quorum must meet at least one participant that may have seen the earlier attempt, and the protocol must make that participant report the evidence it has recorded.

The misconception is that a quorum is just "more than half, so it feels safe." The deeper reason is intersection. Ballots, terms, epochs, and views then order competing attempts so newer coordinators learn from older accepted history instead of blindly overwriting it.

Why Intersection Matters

In a crash-fault consensus system with 2f + 1 replicas, a majority quorum lets the system survive up to f failed replicas. With five replicas, a majority is three. Any two majorities intersect:

Q1 = A B C
Q2 = C D E
overlap = C

If a value may have been accepted by a quorum, the next leader or proposer must consult another quorum before deciding what is safe to do. Because the quorums intersect, at least one participant can reveal the earlier accepted value, ballot, term, or log prefix.

This is why prepare phases, election restrictions, and log-matching rules exist. They are not ceremony. They are ways of asking the cluster: "what evidence already exists that I must preserve?"

The trade-off is concrete. Larger quorums make it easier to preserve safety evidence, but they reduce availability because more replicas must respond. Flexible quorum protocols can change quorum sizes, but only if the quorums that matter for safety still intersect in the required places.

Evidence Moves Through the Overlap

The overlapping participant is useful only if it carries durable evidence. A node that accepted a value, acknowledged a log entry, or voted in a term must retain enough metadata to explain what happened after a crash or leadership change.

Suppose node C accepted value X in ballot 7. A later coordinator in ballot 8 contacts C, D, and E. If the protocol requires C to report its accepted value, ballot, and slot, the new coordinator cannot pretend the slot is empty. It must carry X forward, or preserve a compatible log prefix, depending on the protocol.

Intersection without evidence is weak. Evidence without a rule that future leaders must obey it is also weak. Consensus safety needs both.

Ballots Turn Races Into Ordered Attempts

Quorum intersection alone is not enough. Nodes also need to know which attempt supersedes which. Paxos calls these ballots. Raft uses terms. The names differ, but the job is similar:

old attempt: ballot 7
new attempt: ballot 8

A node promises not to accept older attempts after it has joined a newer one. That promise lets a new leader gather evidence and move forward without letting stale proposers create conflicting committed history.

The important rule is that newer does not mean "free to choose anything." Newer means "allowed to proceed after learning what must be preserved." If an earlier value has enough evidence behind it, the later attempt may have to carry that value forward.

This is the safety logic behind many details learners otherwise memorize:

• Paxos proposers adopt the highest-numbered accepted value they discover.
• Raft candidates need sufficiently up-to-date logs to win leadership.
• Reconfiguration protocols require overlap so the old and new worlds cannot both decide incompatible histories.

Worked Example: Competing Values for One Slot

Use the five-node cluster again and focus on one log slot.

1. Ballot 7 proposes value X.
2. Nodes A, B, and C accept X.
3. Before every node hears the outcome, coordinator D starts ballot 8.
4. D contacts C, D, and E.

Because C is in both quorums, D learns that X was accepted in ballot 7. D may now have the newer ballot, but it does not have permission to choose unrelated value Y for the same slot. The safe move is to propose X, or in a replicated log protocol, to preserve the compatible prefix implied by that evidence.

If the second quorum did not intersect the first, D could miss the evidence. If D ignored C's evidence, the intersection would exist in the math but not in the behavior.

Commit Evidence Is a Claim You Can Defend

Operationally, a committed entry is not just an entry that appears in logs. It is an entry backed by evidence strong enough that future valid protocol steps must preserve it.

That evidence can take different shapes:

• acknowledgments from a majority,
• an accepted value with ballot metadata,
• a replicated entry identified by log index and leader term,
• quorum certificates in Byzantine protocols,
• durable metadata showing which configuration and quorum rule decided the entry.

The useful question during design review is:

If this node crashes now, what evidence proves the decision survives?

That question catches weak designs. A single leader's memory is not commit evidence. A write on one follower is not commit evidence. A timeout is not commit evidence. The system needs a rule that future leaders, recoveries, and configuration changes are forced to respect.

Common Misreadings

Quorum intersection does not mean every node sees every decision. It means any later successful decision path must cross enough prior evidence to preserve safety.

Ballots and terms do not make newer leaders omnipotent. They make attempts comparable, then constrain newer attempts to respect older evidence.

A majority acknowledgment is only meaningful if the acknowledgments follow the protocol's persistence and membership rules. A volatile or mis-scoped acknowledgment is not strong commit evidence.

Connections

The previous lesson's state machine replication contract depends on this machinery. Replicas can apply the same command at the same log position only if future leaders preserve the already-committed history.

The next lesson on linearizable reads, leader leases, and fencing builds on the same concern from the read side. A leader must know that its authority and committed state are still current before answering a read that claims to observe the latest value.

Resources

• [PAPER] Paxos Made Simple
  • Focus: Track how prepare and accept phases preserve previously accepted values.
• [PAPER] In Search of an Understandable Consensus Algorithm
  • Focus: Compare Raft terms, elections, and log matching with the quorum evidence frame.
• [PAPER] Viewstamped Replication Revisited
  • Focus: Look for how views and quorums preserve committed operations.

Key Takeaways

• Quorum intersection makes later coordination attempts encounter evidence from earlier ones.
• Ballots, terms, epochs, and views order competing attempts without letting newer leaders ignore history.
• A committed decision is safe only when future valid protocol steps are forced to discover and preserve it.