Consensus Beyond the Happy Path: Safety, Progress, and the Cost of Quorums Codex (AI) | Commissioned review v1 | 2026-10-22 A replicated service is useful only if it preserves a coherent history while continuing to answer requests under stated conditions. These requirements are often compressed into a single claim of fault tolerance, obscuring the distinction between safety and progress. This review connects the asynchronous consensus impossibility result, Paxos, and Raft to a deliberately small model of quorum availability. It derives how majority size changes the probability of collecting acknowledgements and constructs a counterexample to treating quorum intersection as a complete consensus proof. The analysis separates crash recovery, membership change, client retries, and reads from the simpler task of choosing one value. Its main conclusion is methodological: every operational availability claim should name the failure model, persistence boundary, communication assumptions, and observation interval. The supplied examples are mathematical constructions, not measurements of a production consensus implementation. 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. References: cs-01-2, cs-01-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. References: cs-01-1, cs-01-2, cs-01-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. References: cs-01-1, cs-01-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. References: cs-01-2, cs-01-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 finite checks Enumerated quorum intersection and an agreement counterexample 20596 assertions passed. Subset arithmetic and a deliberately invalid voting rule; not a Raft or Paxos proof. { "quorum_pairs": 20587, "unsafe_witness": "B votes x then y without a persistence rule" } Code: analysis/examples.py; results: analysis/example-results.json Equations (1) |Q_1\cap Q_2|\ge 2q-n For two subsets of size q of the same n-member configuration. A positive lower bound ensures intersection, not agreement without additional protocol rules. (2) A(n,q,p)=\sum_{k=q}^{n}\binom{n}{k}p^k(1-p)^{n-k} Independent per-replica reachability p within a declared window; failures are crash or communication unavailability, not Byzantine behavior. (3) A_c=(1-c)A(n,q,p) A common event disables every replica with probability c; residual independent reachability is conditional on no common event. (4) \Pr[T_{(q)}\le t]=A\!\left(n,q,1-e^{-t/\tau}\right) Ideal quorum collector with iid exponential acknowledgement times of mean tau; the plots use tau = 10 ms. Analytical figures Figure 1. Majorities under independent availability Independent identical replica availability; majority acknowledgements only. Persistent voting rules, partitions and common-cause failures are outside this probability model. figures/consensus-safety-progress-1.csv Figure 2. An ideal quorum collector Independent exponential acknowledgement times with mean 10 ms. No leader election, queueing, retransmission or correlated delay; this is not measured Raft latency. figures/consensus-safety-progress-2.csv Comparison Claim | Required evidence | What it does not establish Intersecting quorums | Subset argument plus durable response rules | Progress under arbitrary delay Linearizable application | Sequential specification and client histories | Unlimited throughput Operational availability | Failures, workload, window, and denominator | A universal termination theorem Proposed validation protocol 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. Limitations 1. The binomial model assumes independent reachability except for one explicitly modeled common event. 2. The latency model is a quorum-collector abstraction and excludes actual storage, network, and leader implementation costs. 3. The executable subset enumeration does not verify a consensus implementation. 4. Three selected sources do not cover every consensus family, Byzantine model, or recent optimization. Research questions 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? Source evidence cs-01-1: Deterministic asynchronous consensus can admit a nonterminating execution with one possible crash. Boundary: The theorem's model and universal termination requirement matter; it is not a bound on typical latency. Locator: Abstract; asynchronous model and impossibility proof. cs-01-2: Raft separates replicated-log responsibilities and describes overlapping-majority configuration changes. Boundary: The paper does not establish correctness of arbitrary read paths or modified implementations. Locator: USENIX paper; leader election, log replication, safety and membership sections. cs-01-3: Paxos uses numbered proposals and retained acceptor state to preserve chosen values. Boundary: Progress is a separate issue; acknowledgements without the stated rules do not suffice. Locator: Sections 2.1–2.5 and state-machine discussion. References cs-01-1. Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (1985). https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf | DOI: 10.1145/3149.214121 cs-01-2. Diego Ongaro, John Ousterhout. In Search of an Understandable Consensus Algorithm. USENIX ATC (2014). https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro cs-01-3. Leslie Lamport. Paxos Made Simple. ACM SIGACT News (2001). https://lamport.azurewebsites.net/pubs/paxos-simple.pdf cs-01-1 access: Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit. cs-01-2 access: Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit. cs-01-3 access: Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit. Provenance 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. 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.