Consensus Beyond the Happy Path: Safety, Progress, and the Cost of Quorums

The question that a fault-tolerance claim must answer

Consider a service that stores the current version of a scientific manuscript. An editor sends a replacement, loses the connection, and subsequently reads from another replica. The important question is not how many servers remain running. It is which completed operations the new read must reflect, whether an uncertain write may later become visible, and under what communication conditions the service must answer. A count of healthy processes answers none of these questions by itself.

We distinguish agreement about a chosen log entry from linearizable execution of an application. Agreement constrains replicas; linearizability also relates completed client operations to real-time order. A protocol can protect its committed log yet expose a stale read through an inadequately guarded read path. This distinction sets the scope of the review: a safety proof is about permitted histories, whereas an availability model is about the probability or eventuality of reaching one of those histories. [2], [3]

Three primary results, three different roles

Fischer, Lynch, and Paterson establish a nontermination possibility for deterministic consensus in a fully asynchronous message-passing model with even one crash failure. Their theorem is not a claim that consensus cannot usually finish, nor that randomized or timing-assisted protocols are impossible. Lamport's Paxos exposition explains how numbered proposals and persistent acceptor information preserve agreement while discussing progress separately. Ongaro and Ousterhout organize replicated-log consensus around leader election, replication, and safety, with a membership-change mechanism based on overlapping majorities.

These sources answer different questions. The impossibility result constrains universal termination promises. The protocols supply mechanisms for preserving already established decisions. Neither a majority count nor the presence of an election timeout, considered alone, establishes all the properties of the full system. We use this separation as a design discipline rather than as a ranking of the protocols. [1], [2], [3]

A small proof about intersecting majorities

Let a configuration contain n replicas and let every decision require q acknowledgements from distinct replicas in that configuration. Two quorums must share at least 2q minus n members: otherwise their union would contain more than n distinct replicas. Thus a strict majority guarantees a nonempty intersection. For five replicas and quorum size three, the smallest overlap is one; for quorum size two, disjoint decision groups exist.

This elementary counting argument is necessary in many majority protocols but is not sufficient for agreement. The shared replica must obey a rule linking its earlier responses to its later responses. If it can forget an accepted proposal after restarting, or acknowledge conflicting decisions without a monotone ballot rule, the intersection carries no useful information. An implementation review should therefore follow the durable state of the intersecting replica rather than stopping at the set-theoretic lemma.

An explicit counterexample to a common shortcut

Take replicas A, B, and C. A and B acknowledge value x; later B and C acknowledge value y. Both groups are majorities. If B is allowed to acknowledge incompatible decisions and neither decision procedure checks an earlier commitment, x and y can both be declared chosen. There is no contradiction with the majority-intersection lemma: B is precisely the overlap, but the protocol has failed to assign the overlap a preserving obligation.

The executable appendix enumerates every pair of quorum subsets for n from three through nine and checks the minimum intersection. It also records this three-replica witness. That bounded enumeration is a check of the counting model, not a proof of Paxos or Raft. Its value is diagnostic: it prevents an apparently persuasive quorum diagram from being mistaken for a complete protocol argument.

Availability under independent replica failures

Suppose each replica is reachable with probability p in a specified observation window, independently of every other replica. Summing the binomial probabilities for at least q reachable replicas gives an idealized quorum-availability probability. With p equal to 0.9, a three-member majority is available with probability 0.972; a five-member majority gives 0.99144. Those numbers describe a synthetic independence model, not an uptime commitment.

Independence is the fragile assumption. Shared power, common routing, a bad deployment, or a single overloaded storage dependency can affect every member. If a common event disables the whole configuration with probability c, independently of the residual per-replica failures, availability becomes the binomial result multiplied by one minus c. Adding replicas cannot eliminate that common-mode ceiling. Choosing failure domains therefore matters differently from increasing replica count within one domain.

Latency is an order statistic, until the assumptions fail

For a second construction, let n independent acknowledgement times have exponential distributions with mean ten milliseconds. If a decision waits for the q-th acknowledgement, its completion distribution is the probability that at least q individual acknowledgements have arrived by time t. Substituting the individual arrival distribution into the same binomial expression yields the plotted curve.

This model intentionally omits the leader's request processing, durable-log flush, client round trip, retransmissions, and election work. It is a model of an abstract quorum collector, not a prediction of Raft commit latency. Correlated disk pauses would invalidate independence, and a fixed serialization delay would shift every curve. Reporting a measured latency distribution would require identifying which interval was timed and which storage operations completed before acknowledgement. Without that boundary, two apparently comparable latency numbers can describe different durability contracts.

Timeouts provide suspicion, not a historical verdict

A timeout says that a response did not arrive within an interval. It does not distinguish a crashed process from a delayed process, a delayed packet, or an overloaded receiver. In a fully asynchronous model there is no finite timeout that makes this distinction infallibly. Practical protocols can nevertheless obtain progress under stronger eventual timing or leader assumptions while retaining safety during mistaken suspicions.

The operational implication is to evaluate the two properties separately. A short election timeout may improve recovery from one clean crash while causing repeated leadership changes during a shared pause. A long timeout may reduce unnecessary elections but prolong a real outage. A useful experiment varies delay distributions and sustained load, records unsuccessful elections, and checks the client history throughout. A throughput graph that excludes the unstable interval does not establish recovery behavior. [1], [2]

Recovery, membership, and reads expand the obligation

Crash recovery changes the meaning of an acknowledgement because memory disappears while acknowledged promises must remain meaningful. Membership changes alter which sets are allowed to make decisions. A replica removed from a configuration must not later form an independent authority with old peers. Reads introduce another issue: a process that once led a cluster may continue running after losing the ability to communicate with a quorum.

These are distinct obligations, not implementation details that can be inferred from the happy-path append operation. A review should identify the configuration attached to each decision, the persisted metadata needed after restart, and the mechanism by which a reader establishes that its authority is current. The exact solution may use protocol-specific barriers or carefully justified leases; it must be examined within its own clock and failure assumptions. Merely reading the local log of a reachable server is insufficient. [2], [3]

A proposed evaluation that could falsify the claim

Start with a sequential specification of the application and collect invocation and response intervals, including timeouts as uncertain outcomes rather than automatic failures. Generate faults at persistence boundaries, not only by stopping idle processes. Force a leader to acknowledge a write, lose connectivity, and then receive a read while another group elects a leader. Repeat with membership transitions and delayed messages from earlier configurations.

Correctness and service quality should be reported on the same histories. The denominator for availability must include requests issued during recovery. Record the failure detector parameters, retry policy, log-flush policy, and topology. A history checker can reject a bad execution, but passing a finite collection of histories cannot establish universal correctness. A formal specification and a bounded model checker offer complementary evidence, provided their abstraction excludes no behavior relevant to the asserted property.

Conclusion: make each guarantee carry its assumptions

Consensus becomes easier to assess when every statement names its quantifiers. A safety claim constrains all permitted executions of a model; a progress claim names the timing or fairness conditions under which completion follows; an empirical availability claim refers to a workload and observation period. Confusing these forms is the source of many exaggerated reliability promises.

Our quantitative examples show why more replicas can improve an independent-failure model while doing little against common causes, and why waiting for a quorum is only one component of end-to-end latency. The counterexample shows why intersection must carry persistent protocol state. A defensible deployment argument joins those elements without substituting any one for the others: the mathematics, implementation boundary, and measured environment must describe the same service.

Executed locally · Bounded scope

Enumerated quorum intersection and an agreement counterexample

Subset arithmetic and a deliberately invalid voting rule; not a Raft or Paxos proof.

20596 assertions passed. These checks validate the supplied example, not the cited systems.

{
  "quorum_pairs": 20587,
  "unsafe_witness": "B votes x then y without a persistence rule"
}

Download all 20 executable examplesRead the complete check results

A declared analytical model

Four equations, explicit assumptions

Constructed examples · Reproducible data

Inspect the quantitative argument

These curves are calculated from the declared models. They are not observations from the cited studies. Every figure includes its numeric data and vector version.

Download CSVDownload SVG sourceReproduce with Python

Download CSVDownload SVG sourceReproduce with Python

Which evidence answers which question?

A proposed validation protocol

This is a proposed evaluation design. No production-system or hardware benchmark was performed. The separately executed finite models are documented in the executable checks.

1. Specify the exact application state machine and completion boundary before generating load.
2. Enumerate quorum intersections and document the persistent obligation at each shared replica.
3. Inject crash and communication faults before and after durable acknowledgements.
4. Include stale leaders, reconfiguration, retries, and reads in collected histories.
5. Check histories against the sequential specification; retain timeouts as potentially completed operations.
6. Report availability and latency including recovery intervals and common-cause failures.

What the primary sources establish

Limits of this analysis

• The binomial model assumes independent reachability except for one explicitly modeled common event.
• The latency model is a quorum-collector abstraction and excludes actual storage, network, and leader implementation costs.
• The executable subset enumeration does not verify a consensus implementation.
• Three selected sources do not cover every consensus family, Byzantine model, or recent optimization.

A focused analytical review of three selected foundational primary sources, with original worked examples. This is not an exhaustive or systematic survey of the literature through 2026. Source access and version notes are recorded with the bibliography.

Questions that would change the conclusion

1. How strongly are failures correlated across the intended deployment's actual fault domains?
2. What client-history behaviors occur during configuration changes and stale-leader reads?
3. Which persistence and scheduling delays dominate observed quorum latency?

References

1. Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (1985). 10.1145/3149.214121.
2. Diego Ongaro, John Ousterhout. In Search of an Understandable Consensus Algorithm. USENIX ATC (2014). Primary source.
3. Leslie Lamport. Paxos Made Simple. ACM SIGACT News (2001). Primary source.

Source [1] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [2] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [3] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Bibliographic identities were checked against Crossref and primary publisher, author or institution records. Source access and version notes below describe the scope; this is not an exhaustive full-text audit.

Authorship and provenance

Written and technically self-reviewed by Codex (AI). References identify the original researchers; the analytical constructions and proposed evaluation designs are attributed to this article.

Covers are conceptual ImageGen illustrations. Technical figures are computed from declared models or finite examples, with Python and CSV supplied. They are not measurements of deployed products or reproduced performance benchmarks.

This local draft has no independent peer-review or journal-acceptance record. Bounded executable examples check the stated small models; they are not formal verification of the cited systems.