# Distributed Consensus — 36-Item Grid (Control) ## Stage 1 — Fundamentals ### 1.1 Agreement, Validity and Termination **Definition:** These are the three classic safety and liveness properties that define consensus itself. Agreement means that no two correct processes ever decide different values, so the system speaks with one voice even though it is built from many machines. Validity means that the value decided must have been proposed by some process, which prevents a trivial or adversarial algorithm from inventing an answer nobody suggested. Termination means that every correct process eventually decides, which turns consensus from a static safety condition into a usable decision procedure. Together they separate a genuine consensus protocol from both a mere broadcast mechanism and a mere voting rule. **Execution flow:** 1. Each process starts with an input value that it is willing to propose to the group. 2. Processes exchange proposals and intermediate votes according to the rules of the particular protocol in use. 3. A process applies the protocol's decision rule once the required quorum or threshold condition is met. 4. The process records the decided value as final and never revises it in later rounds. 5. Other processes learn the decision either directly from the decider or through subsequent protocol messages, and they converge on the same value because the decision rule was designed to make divergent decisions impossible. **Edge cases:** Termination cannot be guaranteed in a fully asynchronous system with even one crash failure, which is the content of the FLP impossibility result, so real protocols add timing assumptions, randomness, or failure detectors. Validity has several strengths: weak validity only constrains decisions when all inputs are identical, while strong or external validity requires the decided value to satisfy an application-level predicate, as in blockchain systems where a block must be well-formed. Agreement must also be stated carefully when processes can be Byzantine, because then agreement is required only among the honest participants, not the faulty ones. ### 1.2 State Machine Replication **Definition:** State machine replication, usually abbreviated SMR, is the architectural pattern that turns consensus on individual values into consensus on an ordered sequence of commands. Each replica runs an identical deterministic state machine, all replicas receive the same commands in the same order, and therefore all replicas pass through the same sequence of states and produce the same outputs. Consensus is the ordering engine inside SMR: instead of agreeing on a single value once, the replicas repeatedly agree on the next command to append to a shared log. This is the foundation on which replicated databases, coordination services such as ZooKeeper and etcd, and most permissioned blockchains are built. **Execution flow:** 1. A client submits a command to one or more replicas, often to a designated leader. 2. The leader assigns the command the next position in the replicated log and proposes that assignment to the other replicas. 3. Replicas run a consensus round for that log position and commit the command once a quorum accepts it. 4. Each replica applies committed commands to its local state machine strictly in log order. 5. The replica that received the client request returns the output produced by applying the command, and the client treats the operation as complete. **Edge cases:** Determinism is essential: a command that reads the local clock, generates a random number, or iterates over an unordered data structure can make replicas diverge even though they applied the same log. Read-only operations can bypass the log with lease-based or quorum reads, but only if the protocol proves the read reflects all committed writes. Snapshotting and log compaction are needed because the log grows without bound, and a replica that falls far behind must be brought up to date by transferring a snapshot rather than replaying the entire history. ### 1.3 Quorums and Intersection **Definition:** A quorum is a subset of processes large enough that its response can be treated as representative of the whole system, and the central design trick is quorum intersection: any two quorums overlap in at least one process. In a majority system with N processes, a quorum is any set of more than N/2 processes, and two majorities necessarily share a member, so information accepted by one quorum cannot be invisible to the next. That single shared witness is what prevents two different values from both being accepted in different rounds. For Byzantine systems the arithmetic is stricter, because the intersection must contain an honest process, which leads to quorums of size 2f+1 in a system of 3f+1 processes tolerating f Byzantine faults. **Execution flow:** 1. The protocol fixes a quorum size based on the number of processes and the fault model it tolerates. 2. A proposer sends its proposal to all processes and collects acknowledgements until it holds a full quorum of responses. 3. Each responding process records the proposal in durable local state before acknowledging, so the record survives its own crash. 4. A later proposer contacts its own quorum, which must intersect the earlier quorum, and therefore learns about the earlier proposal from at least one common member. 5. The later proposer is then constrained by the protocol rules to preserve the earlier value rather than overwrite it, which is how safety propagates across rounds. **Edge cases:** Flexible quorum systems allow read and write quorums of different sizes as long as they intersect each other appropriately, trading read cost against write cost. Weighted voting assigns more votes to more reliable or better-provisioned replicas, so a quorum is a majority of weight rather than of machines. Quorum intersection alone does not give liveness: if too many processes crash, no quorum can be assembled at all, and the system stalls safely rather than deciding incorrectly. ### 1.4 Rounds, Ballots and Epochs **Definition:** Most consensus protocols organise time into numbered rounds, also called ballots, terms, epochs, or views, each with a designated coordinator. The round number acts as a logical clock for the protocol: messages are tagged with the round in which they were sent, processes ignore stale messages from older rounds, and a value accepted in a lower round constrains what may be proposed in higher rounds. Round numbers must be totally ordered and, in most designs, uniquely assigned so that two coordinators never believe they own the same round. Paxos generates ballot numbers from a scheme that interleaves process identifiers, Raft increments a term on each election timeout, and PBFT increments a view number on each view change. **Execution flow:** 1. A process that suspects the current coordinator has failed, or that wants to lead, selects a round number higher than any it has seen. 2. It broadcasts a message announcing the new round and asking processes to promise not to accept proposals from lower rounds. 3. Processes that have not already promised a higher round record the promise and reply with any value they previously accepted, together with the round in which they accepted it. 4. Once the coordinator collects a quorum of replies, it must propose the value associated with the highest reported round, if any, or may propose its own value if none was reported. 5. The round proceeds to the accept phase, and if it fails, the whole procedure repeats with a still higher round number. **Edge cases:** Round contention, where several processes repeatedly try to seize leadership at once, can livelock the protocol even though safety is never violated; randomised backoff and lease mechanisms exist largely to prevent this duelling-leader pattern. Round numbers stored in stable storage must survive crashes, otherwise a recovered process might reuse an old round and break the promise discipline. Very long-lived systems must also consider round-number exhaustion and wrap-around, which is handled by using wide integers or by pairing a persistent epoch counter with a resettable local counter. ### 1.5 Safety versus Liveness **Definition:** Safety and liveness are the two families into which almost every correctness property of a distributed protocol falls. Safety properties say that nothing bad ever happens: no two honest processes decide differently, no committed entry is ever removed from the log, no client is told an operation succeeded if it did not. Liveness properties say that something good eventually happens: every correct process eventually decides, every submitted command is eventually committed, the system recovers after a failure. Consensus protocols are deliberately designed to preserve safety unconditionally, under all timing conditions, and to provide liveness only under favourable conditions such as eventual synchrony or a stable leader, because the FLP result shows that both cannot be guaranteed together in a purely asynchronous system with failures. **Execution flow:** 1. The designer states the safety invariant precisely, usually as a property of the set of values that can be decided in any execution. 2. The protocol's message rules are constructed so that every state transition preserves that invariant, regardless of message delays or process crashes. 3. Liveness mechanisms are then layered on top: timeouts, leader election, retransmission, and round advancement, none of which are allowed to alter the safety rules. 4. During operation, if conditions are bad, the liveness mechanisms simply fail to make progress while the safety invariant continues to hold. 5. When conditions improve — a stable leader emerges and messages arrive within the timeout — the same protocol resumes deciding without any special recovery of the safety state. **Edge cases:** The CAP theorem is an application of this trade-off to network partitions: during a partition a system must choose between continuing to answer, risking divergence, or refusing to answer, preserving consistency. Operators often misread a safe stall as a bug and intervene by forcing decisions or rolling back logs, which converts a liveness failure into a safety failure. Formal verification effort is usually spent overwhelmingly on safety, because liveness proofs depend on timing and fairness assumptions that are harder to state and easier to invalidate in deployment. ### 1.6 The FLP Impossibility Result **Definition:** The FLP result, proved by Fischer, Lynch and Paterson in 1985, states that no deterministic consensus protocol can guarantee agreement, validity and termination in a fully asynchronous system if even a single process can crash. The proof shows that from any bivalent configuration — a state from which the system could still decide either 0 or 1 — an adversarial scheduler can always delay one critical message and steer the execution to another bivalent configuration, forever postponing a decision. The result does not say consensus is impossible in practice; it says that at least one assumption must be relaxed, and every practical protocol is best understood by which assumption it relaxes. **Execution flow:** 1. Assume a deterministic protocol that claims to solve consensus asynchronously with one possible crash. 2. Show there exists an initial configuration that is bivalent, because if all initial configurations were univalent, neighbouring configurations differing in one process's input would force a contradiction when that process is assumed crashed. 3. Show that from any bivalent configuration and any pending event, the scheduler can reach another bivalent configuration by delaying the event and exploring the executions in which it is applied last. 4. Compose these steps into an infinite fair execution in which every correct process takes infinitely many steps but no decision is ever reached. 5. Conclude that termination is not guaranteed, and therefore any real protocol must add synchrony assumptions, randomness, failure detectors, or a probabilistic termination guarantee. **Edge cases:** Randomised protocols such as Ben-Or's escape FLP by guaranteeing termination with probability one rather than with certainty. Partial synchrony models, in which message delays are bounded after some unknown global stabilisation time, restore deterministic termination and underpin Paxos, Raft and PBFT deployments. Failure-detector approaches, notably the weakest failure detector results of Chandra and Toueg, characterise exactly how much extra information about crashes is needed to solve consensus, which makes FLP a design map rather than a dead end. ## Stage 2 — Fault & Network Models ### 2.1 Crash Faults and Crash Recovery **Definition:** A crash fault is the simplest failure mode: a process stops executing and sends no further messages. In the crash-stop model it never returns, while in the crash-recovery model it may restart, but it loses all volatile memory and can recover only what it wrote to stable storage before crashing. Protocols tolerating crash faults, such as Paxos and Raft, need only majorities, because a crashed process never actively contradicts the protocol — it is merely silent. The engineering discipline of the model is the write-ahead rule: any fact a process has acknowledged to others must already be durable, otherwise a crash and restart could make it retract a promise the rest of the system has relied upon. **Execution flow:** 1. A process receives a request to accept a proposal or cast a vote. 2. Before replying, it writes the relevant state — current term, voted-for candidate, or accepted value and log entry — to stable storage and flushes it. 3. Only after the write is durable does it send its acknowledgement or vote. 4. If the process crashes, it stops responding, and the remaining processes continue if they still form a quorum. 5. If the process recovers, it reads its durable state, rejoins with exactly the commitments it made before crashing, and catches up on any log entries it missed. **Edge cases:** A crash during the flush itself creates ambiguity about whether the state was recorded, so protocols must treat a partially written record as either fully present or fully absent, typically with checksums and atomic rename patterns. Correlated crashes, such as a rack power failure, can remove a whole quorum at once even though each individual crash is benign. Crash-recovery also interacts badly with identity: a recovered process must rejoin with the same identity, because if it returned as a new process the quorum arithmetic would be wrong. ### 2.2 Byzantine Faults **Definition:** A Byzantine fault is arbitrary behaviour: a faulty process may lie, send contradictory messages to different peers, forge votes it is entitled to cast, omit messages selectively, or collude with other faulty processes, all in whatever way most damages the protocol. The name comes from the Byzantine Generals Problem posed by Lamport, Shostak and Pease, in which loyal generals must agree on a plan despite traitors sending conflicting orders. Because a Byzantine process can actively manufacture apparent support for two different values, crash-fault majorities are insufficient: with N processes and f Byzantine faults, consensus requires N at least 3f+1 and quorums of 2f+1, so that any two quorums intersect in at least one honest process and an honest majority sits inside every quorum. **Execution flow:** 1. The system is configured with an explicit bound f on the number of Byzantine processes and a total membership of at least 3f+1. 2. Processes sign their protocol messages so that statements can be attributed and cannot be forged by others. 3. A proposer broadcasts a proposal, and processes echo or vote for it only if it is well-formed and consistent with what they have seen. 4. A value is treated as prepared or committed only when a process collects 2f+1 matching signed votes, forming a quorum certificate. 5. Any later round must present and respect prior quorum certificates, so a conflicting value cannot assemble an honest-supported certificate of its own. **Edge cases:** Authentication changes the bounds for the special problem of broadcast, where signed messages allow tolerating any number of traitors for a single sender's value, but general Byzantine consensus still needs the 3f+1 bound. The model assumes faults are independent, yet real compromises are often correlated through shared software, shared keys, or a shared cloud provider, which can silently exceed f. Economic systems such as proof-of-stake blockchains replace the count f with a fraction of total stake, so the assumption becomes that less than one third of stake is adversarial, and key compromise of a large staking operator becomes a systemic event. ### 2.3 Partial Synchrony and Timing Assumptions **Definition:** Partial synchrony is the timing model that sits between the fully asynchronous model, where message delays are unbounded, and the synchronous model, where a known bound on delay holds from the start. In the formulation of Dwork, Lynch and Stockmeyer, either there is an unknown bound on message delay that holds from the beginning, or there is a known bound that only begins to hold after an unknown global stabilisation time. Before stabilisation the network can behave arbitrarily badly, and the protocol must remain safe; after stabilisation, timeouts become meaningful and the protocol must make progress. This is the honest model of a real data-centre network, which is fast almost all the time but can suffer congestion, garbage-collection pauses and routing incidents that temporarily destroy timing. **Execution flow:** 1. Processes run the protocol with timeout values that are initially conservative. 2. While the network is unstable, rounds time out and are retried with higher round numbers, but no safety rule is ever relaxed. 3. Leaders or coordinators that fail to make progress are replaced through the round-advance mechanism. 4. When the network stabilises, a round eventually runs with a live coordinator and timely messages, and a decision is reached. 5. Many implementations increase timeouts on each failed round, in the style of exponential backoff, so that the configured timeout eventually exceeds the true post-stabilisation delay even though that delay was never known in advance. **Edge cases:** A process that is merely slow, for example because of a long garbage-collection pause, is indistinguishable from a crashed process in this model, and it may wake up believing it is still leader after the system has moved on, which is why fencing through round numbers matters. Clock synchronisation is not assumed, only message-delay behaviour, so protocols must never use wall-clock timestamps as a safety input. If stabilisation never comes, the protocol owes safety but not progress, and operators must fix the network rather than the algorithm. ### 2.4 Network Partitions **Definition:** A network partition is a failure of communication rather than of processes: the membership splits into two or more groups such that messages within a group are delivered but messages between groups are lost or delayed indefinitely. Every process may be alive and correct, yet the system as a whole cannot coordinate across the split. Quorum-based protocols respond predictably: at most one side of a partition can contain a quorum, so at most one side can continue deciding, and the other side must block. This is the operational meaning of the CAP theorem's choice between consistency and availability during a partition. **Execution flow:** 1. A network fault, such as a failed link between data centres or a misconfigured firewall rule, severs communication between two groups of replicas. 2. Each group attempts to run consensus rounds; the group holding a quorum of the total membership succeeds, and the group without one times out. 3. Clients connected to the majority side continue to have their operations committed. 4. Clients connected to the minority side receive errors or timeouts rather than confirmations, because their replicas cannot commit anything. 5. When the partition heals, minority-side replicas discover the higher round numbers and log entries of the majority side, discard any uncommitted divergent state, and catch up by log replication or snapshot transfer. **Edge cases:** Split brain is the catastrophic version of a partition, where both sides wrongly believe they hold a quorum, usually because membership was reconfigured inconsistently or because an external failover tool promoted a second leader; fencing tokens and careful membership changes exist to prevent it. Asymmetric partitions, where A can send to B but B cannot reply, are harder to detect than clean cuts and often manifest as repeated leader elections. Partition testing, by deliberately severing links in staging with tools that inject network faults, is the only reliable way to learn whether a given deployment actually blocks on the minority side. ### 2.5 Failure Detectors **Definition:** A failure detector is an oracle-like module at each process that outputs suspicions about which other processes have crashed. It is unreliable by design: it may suspect a slow but living process, and it may take time to suspect a genuinely crashed one. Chandra and Toueg classified detectors by completeness, whether crashed processes are eventually suspected, and accuracy, whether correct processes are ever suspected, and showed that the eventually weak failure detector — eventually, some correct process is never suspected — is the weakest detector with which consensus can be solved in an asynchronous system with a majority of correct processes. In practice, timeout-based heartbeat monitors are the failure detectors inside every leader-election mechanism, whether or not they are named as such. **Execution flow:** 1. Each process periodically sends heartbeat messages to its peers or to a monitoring component. 2. A local detector records the time since the last heartbeat from each peer. 3. When that interval exceeds a configured timeout, the detector adds the peer to its suspected set and notifies the consensus layer. 4. The consensus layer reacts to suspicion by starting an election or advancing a round, not by treating the suspected process as definitively dead. 5. If heartbeats resume, the detector removes the process from the suspected set, and adaptive implementations lengthen the timeout to reduce future false suspicions. **Edge cases:** False suspicions do not endanger safety in a well-designed protocol, because suspicion only triggers round changes and elections that are themselves fenced by round numbers, but they do damage liveness by causing leader churn. Detectors based purely on timeouts conflate process crashes with network failures and with long local pauses, which is why accrual detectors, such as the phi accrual detector used in Cassandra, output a continuously increasing suspicion level instead of a binary verdict. In wide-area deployments the timeout must reflect the tail latency of the link, not the median, or the system will spend its life electing. ### 2.6 Adversary Models and Cryptographic Assumptions **Definition:** The adversary model states precisely what an attacker is assumed to be able to do: how many processes it can control, whether it can schedule message delivery, whether it can break cryptographic primitives, and whether it is static, choosing its victims before the protocol starts, or adaptive, corrupting processes during execution based on what it observes. Byzantine consensus protocols are typically proved against a computationally bounded adversary that controls up to f processes, can delay messages within the timing model, but cannot forge signatures or find hash collisions. These assumptions are part of the protocol's specification, not decoration: if the deployed system gives the adversary more power than the model allows, the proof says nothing about the deployment. **Execution flow:** 1. The protocol designer fixes the corruption threshold, the timing model, and the cryptographic primitives to be used, and states them as explicit assumptions. 2. Processes are provisioned with key material, usually through a distributed key generation or a trusted setup, so that no single party can forge a quorum certificate. 3. During execution, every safety-critical message is signed, and quorum certificates are verified before they are acted upon. 4. Threshold signatures are often used so that a quorum certificate is a single compact object rather than 2f+1 separate signatures, reducing verification and bandwidth cost. 5. If the adversary exceeds its assumed bound, the protocol's guarantees are void, and detection shifts from the protocol layer to monitoring, forensics, and governance procedures that can remove or slash the offending participants. **Edge cases:** Adaptive corruption is a real concern in long-lived systems because an attacker who learns which process is the next leader can target it with a denial-of-service attack, which motivates leader-election schemes that hide the leader's identity until it reveals itself, such as single secret leader election. Cryptographic assumptions age: a signature scheme considered safe at deployment may weaken, so protocols need algorithm agility and a key-rotation story. Randomness used by the protocol, for leader election or for randomised consensus, must be unpredictable to the adversary, which rules out naive schemes such as hashing public data that the adversary can grind. ## Stage 3 — Classic Protocols ### 3.1 Paxos **Definition:** Paxos, described by Leslie Lamport, is the foundational crash-fault consensus algorithm, in which proposers, acceptors and learners cooperate to choose a single value, and multi-Paxos extends it to choose a sequence of values for state machine replication. Its core discipline is the promise: an acceptor that promises to a ballot will not accept lower ballots, and it reports the highest-ballot value it has already accepted, forcing a proposer to carry that value forward. That rule is the whole safety argument in miniature — a value that might have been chosen can never be silently replaced. Paxos is famously hard to implement correctly because the specification is permissive about roles and message patterns, so most production systems are heavily structured variants of it. **Execution flow:** 1. A proposer selects a ballot number higher than any it has used and sends Prepare messages to a majority of acceptors. 2. An acceptor that has not promised a higher ballot replies with a Promise, including the highest-ballot proposal it has accepted, if any, and commits not to accept lower ballots. 3. If the proposer receives promises from a majority, it must choose the value from the highest-ballot accepted proposal reported; only if none was reported may it use its own value. 4. The proposer sends Accept messages carrying that value and ballot to the acceptors. 5. Acceptors that have not made a higher promise record the acceptance and reply; once a majority has accepted the same value and ballot, the value is chosen and learners can be notified. **Edge cases:** Dueling proposers can repeatedly preempt each other with higher ballots and prevent any decision, so multi-Paxos deployments stabilise a single leader that runs phase one once and then only phase two per instance. Durable state — the highest promise and the highest accepted proposal — must be persisted before replying, or a crash-recovery cycle can violate safety. Log holes can occur in multi-Paxos when a leader changes mid-stream, and a new leader must fill or explicitly no-op those slots before later entries can be applied safely. ### 3.2 Raft **Definition:** Raft is a crash-fault consensus algorithm designed by Ongaro and Ousterhout explicitly for understandability, decomposing the problem into leader election, log replication and safety, plus membership change and log compaction as first-class mechanisms. At any time one server is leader for a term, followers are passive, and a candidate is a follower attempting to become leader. The leader receives all client commands, appends them to its log, replicates them with AppendEntries messages, and commits an entry once it is stored on a majority. Raft's central restriction, that a candidate can only win an election if its log is at least as up to date as a majority's, together with the rule that a leader only commits entries from its own term by counting replicas, gives a safety argument that is much easier to follow than Paxos's. **Execution flow:** 1. Followers wait for heartbeats; when an election timeout expires without contact from a leader, a follower becomes a candidate, increments its term, votes for itself and requests votes. 2. A voter grants its vote if it has not voted in that term and the candidate's log is at least as up to date as its own, comparing last log term and then last index. 3. A candidate receiving votes from a majority becomes leader and immediately sends empty AppendEntries heartbeats to assert authority. 4. The leader appends client commands locally, sends AppendEntries carrying the entries plus the index and term of the preceding entry, and followers reject the request if that preceding entry does not match their log, forcing the leader to back up and retry. 5. When an entry is stored on a majority, the leader advances its commit index, applies the entry, replies to the client, and informs followers of the new commit index in subsequent messages. **Edge cases:** The commit rule is subtle: a leader must not conclude that an entry from a previous term is committed merely because it is stored on a majority, because a future leader could still overwrite it; it becomes committed only indirectly once an entry from the current term is committed. Pre-vote extensions prevent a partitioned server from repeatedly raising its term and disrupting a healthy leader when it rejoins. Joint consensus or single-server membership changes are required because changing membership in one step can create two disjoint majorities and two simultaneous leaders. ### 3.3 Viewstamped Replication **Definition:** Viewstamped Replication, developed by Oki and Liskov in 1988 and revisited in a modern form in 2012, is one of the earliest state machine replication protocols and a direct ancestor of both Paxos-style and PBFT-style designs. Replicas are arranged in a configuration, one is the primary of the current view, and clients send requests to the primary, which assigns each request a sequential operation number and drives it through the backups. When the primary is suspected, replicas perform a view change, selecting the replica with the most complete log in the new view and transferring the state needed to continue without losing any committed operation. Its vocabulary — view, primary, op-number, commit-number — recurs throughout the later literature. **Execution flow:** 1. The client sends its request to the primary of the current view. 2. The primary assigns the next operation number, appends the request to its log, and sends a Prepare message with the view number, operation number and request to the backups. 3. Each backup appends the request in order, and replies with a PrepareOK once it has logged the operation. 4. When the primary has acknowledgements from a majority, the operation is committed; the primary executes it in operation-number order, replies to the client, and piggybacks the commit number on later messages so backups can execute and reply as well. 5. If backups stop hearing from the primary, they start a view change, exchange their logs, install the new primary with the longest log, and resume from the highest committed operation. **Edge cases:** A view change must be careful to preserve operations that were committed but not yet known to all replicas, which is why the new primary is chosen from a quorum and adopts the longest log among them. Client tables, recording the last request from each client and its reply, are needed to give exactly-once semantics when a client retries after a view change. The revisited version of the protocol adds reconfiguration and state transfer for lagging replicas, both of which were underspecified in the original and are where real implementations tend to fail. ### 3.4 Two-Phase and Three-Phase Commit **Definition:** Two-phase commit, or 2PC, is the classic atomic commitment protocol for distributed transactions, in which a coordinator asks all participants whether they can commit a transaction and then broadcasts a single commit or abort decision. It guarantees atomicity — all participants commit or all abort — but it is not a consensus protocol in the fault-tolerant sense, because the coordinator is a single point of failure and the protocol blocks: if the coordinator crashes after participants have voted yes, participants must wait, holding locks, until it recovers. Three-phase commit adds a pre-commit phase and timeouts so that participants can reach a decision without the coordinator under certain failure assumptions, at the cost of an extra round and of correctness that depends on the network not partitioning. **Execution flow:** 1. The coordinator begins the transaction and sends a Prepare or Vote-Request message to all participants. 2. Each participant checks whether it can commit locally, writes the transaction and an undo or redo record to its log if it votes yes, and replies Yes or No. 3. If all votes are Yes, the coordinator writes a Commit decision and broadcasts it; if any vote is No or a timeout expires, it writes Abort and broadcasts that instead. 4. Participants receiving Commit finalise the transaction and release their locks; those receiving Abort roll back using their logs and release their locks. 5. Each participant acknowledges the decision, and the coordinator completes the transaction once all acknowledgements are in. **Edge cases:** The blocking window in 2PC is its defining weakness: participants that voted Yes cannot unilaterally commit or abort, because the coordinator's decision is unknown to them, so a coordinator failure can freeze resources indefinitely. 3PC's extra phase fails under network partitions, where different groups can time out into different decisions, which is why it is rarely used in wide-area systems. Modern systems therefore replace the single coordinator with a replicated one — running the commit decision itself through Paxos or Raft, as in Spanner-style designs and Paxos Commit — which removes the blocking problem while keeping the atomic-commitment interface. ### 3.5 Zab and Leader-Based Atomic Broadcast **Definition:** Zab, the Zookeeper Atomic Broadcast protocol, is the ordering protocol behind Apache ZooKeeper, designed specifically to support a primary-backup replicated service with strong consistency for coordination data. Zab provides atomic broadcast: all processes deliver the same messages in the same order, with the additional guarantee, important for primary election use cases, that a new leader's initial state reflects all transactions committed by previous leaders, and that transactions proposed by a leader are delivered in the order the leader proposed them, preserving causal order across leader changes. Zab runs in phases — election, discovery, synchronisation and broadcast — and its separation of discovery and synchronisation is what makes its leader-change logic distinctive compared with Raft's, which folds those concerns into the election restriction. **Execution flow:** 1. When a leader is lost or the system starts, processes run a leader election, typically using a fast leader election algorithm that selects the process with the most up-to-date history among a quorum. 2. In the discovery phase, the prospective leader collects the accepted histories from a quorum of followers and determines the most recent committed transaction identifier. 3. In the synchronisation phase, the leader brings each follower up to date, truncating divergent uncommitted transactions and sending any committed transactions the follower lacks, and followers acknowledge once synchronised. 4. In the broadcast phase, the leader proposes transactions with monotonically increasing identifiers, followers log and acknowledge them, and the leader commits a transaction once a quorum has acknowledged it, then broadcasts the commit. 5. If the leader fails at any point, the remaining processes abandon the current epoch, return to election, and the epoch increment ensures transactions from the old leader cannot be confused with those of the new one. **Edge cases:** Zab's correctness depends on followers persisting transactions before acknowledging, and on the epoch mechanism preventing a recovered old leader from continuing to issue proposals. Throughput is limited by the leader and by disk flush latency, since every transaction is logged by a quorum before commit. ZooKeeper's use of Zab also illustrates a deliberate scope limit: it is optimised for small coordination data and read-heavy workloads with observers that replicate without voting, not for large data replication, and using it as a general database is a well-known misuse. ### 3.6 Virtual Synchrony and Group Communication **Definition:** Virtual synchrony is a programming model for group communication, pioneered by Birman and the Isis system, in which processes are organised into groups with explicit membership, and messages are delivered in an order that is consistent with membership changes: all processes that survive from one membership view to the next deliver the same set of messages in the old view before installing the new one. This gives developers the illusion that membership changes and message delivery happen synchronously, even though the underlying execution is asynchronous, which makes it much easier to write replicated services that must react coherently to failures. Total-order broadcast within a view, view-synchronous delivery across views, and state transfer to joining members are its three main ingredients. **Execution flow:** 1. A group is formed with an initial membership view, and each member is given the current state or a snapshot from which to derive it. 2. Members multicast messages to the group, and the ordering layer assigns them a delivery order agreed by the members of the current view. 3. When a member fails or wishes to join, the membership layer proposes a new view, and the delivery layer flushes: all messages sent in the old view are delivered to the surviving members before the new view is installed. 4. A joining member receives a state transfer from an existing member so that it starts the new view with the same state as the others. 5. Execution continues in the new view, with the guarantee that any two members that both pass through a sequence of views have delivered the same messages in each of them. **Edge cases:** Virtual synchrony guarantees are about delivery order relative to views, not about durability, so a group can agree on a message that is then lost if all members crash before persisting it, unless the implementation adds logging. Scaling is limited because ordering and view changes involve the whole group, which is why these systems are typically used for small, tightly coupled replica groups rather than internet-scale membership. The model also became the conceptual basis for the view-change mechanisms in PBFT and other Byzantine protocols, where the same flush discipline is needed but with Byzantine rather than crash assumptions. ## Stage 4 — Modern BFT & Blockchain Consensus ### 4.1 PBFT **Definition:** Practical Byzantine Fault Tolerance, published by Castro and Liskov in 1999, was the first Byzantine state machine replication protocol efficient enough to be practical, and it remains the reference design for permissioned Byzantine consensus. PBFT runs with 3f+1 replicas, a primary for each view, and three phases of all-to-all communication — pre-prepare, prepare and commit — which together ensure that if a request is committed in a view, no conflicting request can be committed in any later view. Its normal-case message complexity is quadratic, because every replica broadcasts in two of the phases, and its view-change protocol, which carries prepared certificates into the new view, is the most intricate part of the design. **Execution flow:** 1. A client sends a signed request to the primary, which assigns it the next sequence number in the current view and broadcasts a Pre-Prepare message. 2. Each backup that accepts the Pre-Prepare — checking the signature, view, sequence number and that it has not accepted a different request for that number — broadcasts a Prepare message. 3. A replica that collects the Pre-Prepare plus 2f matching Prepares has a prepared certificate, proving that a quorum agrees on the request's position in this view. 4. Each replica with a prepared certificate broadcasts a Commit message, and a replica that collects 2f+1 matching Commits knows the request is committed locally. 5. The replica executes requests in sequence-number order, sends a signed reply to the client, and the client accepts the result once it receives f+1 matching replies from different replicas. **Edge cases:** A faulty primary can censor requests or delay them indefinitely without violating safety, so clients use timers and rebroadcast to all replicas, and replicas start a view change if a request they know about is not executed in time. Checkpoints and the stable-checkpoint mechanism are essential to bound log growth and to let view changes avoid carrying the entire history, with a checkpoint proved stable by 2f+1 matching checkpoint messages. PBFT's quadratic communication makes it impractical beyond a few dozen replicas, which motivated the linear-authenticator and collector-based designs that followed. ### 4.2 HotStuff and Linear BFT **Definition:** HotStuff is a Byzantine consensus protocol, originating in the Libra/Diem blockchain effort, whose main contribution is to reduce the communication complexity of the common case from quadratic to linear by having replicas send their votes only to the leader, who aggregates them into a threshold-signed quorum certificate. It also unifies the normal case and the view change into a single three-chain commit rule: a block becomes committed when it is the head of a chain of three consecutive quorum certificates, which makes the protocol a clean pipelined blockchain of votes rather than a sequence of distinct instances. That simplicity, plus responsive progress at actual network speed rather than at a timeout bound, is why HotStuff and its descendants, such as Jolteon, Ditto and HotStuff-2, have become the default template for modern BFT. **Execution flow:** 1. The leader of the current view proposes a block extending the highest quorum certificate it knows, and broadcasts the proposal to all replicas. 2. Each replica checks that the proposal extends the certified chain and respects the locked certificate rule, then signs a vote and sends it only to the leader. 3. The leader aggregates 2f+1 votes into a threshold-signed quorum certificate and includes it in its next proposal, simultaneously certifying the previous block. 4. As the chain grows, a block followed by two further certified blocks satisfies the three-chain rule and is committed, together with all its ancestors. 5. Pacemaker logic advances views when a view times out, synchronising replicas onto a new leader with the highest known certificate so the chain can continue. **Edge cases:** The leader is a throughput bottleneck and a single point of liveness failure for its view, so view duration and leader rotation policy matter as much as the core protocol. Pipelining means the latency to commit is measured in chain length rather than rounds, and implementations must handle proposals arriving for blocks whose parents are not yet locally available. Threshold signature setup, especially distributed key generation, is an operational prerequisite that is easy to underestimate, and its failure modes are outside the protocol's own proofs. ### 4.3 Tendermint **Definition:** Tendermint is a Byzantine consensus protocol designed for blockchain systems and now widely used in the Cosmos ecosystem, combining a round-based proposer rotation with a two-step voting process of prevotes and precommits and an explicit locking mechanism. For each height, replicas proceed through rounds; a designated proposer suggests a block, replicas prevote for it if it is valid and consistent with their lock, and if a block gathers more than two thirds of prevotes it becomes locked and replicas precommit it, with more than two thirds of precommits committing the block. Tendermint emphasises accountability: because votes are signed and recorded on-chain, if safety is ever violated the validators responsible for conflicting votes can be identified from the evidence. **Execution flow:** 1. Validators enter a new height, and the proposer for the current round, selected by a weighted round-robin based on voting power, broadcasts a proposal block. 2. Each validator checks the proposal's validity and its locking state; if it is unlocked, or locked on this block, it broadcasts a prevote for the block, otherwise it prevotes nil. 3. A validator that observes more than two thirds of prevotes for a block locks on that block and broadcasts a precommit for it; if the prevotes favour nil, it unlocks and precommits nil. 4. A validator that collects more than two thirds of precommits for a block commits it, applies it to the application state, and moves to the next height. 5. If a round expires without a commit, validators move to the next round, where a new proposer may re-propose the locked block so that the locked value is not lost. **Edge cases:** Tendermint provides finality, so there are no reorganisations in normal operation, but if more than one third of voting power is Byzantine and safety fails, the chain can fork and recovery is a governance and social process rather than an automatic protocol step. Liveness requires more than two thirds of voting power to be online and communicating, so a large validator outage halts the chain rather than degrading it. Because voting power is stake-weighted, validator set changes must be handled carefully across heights, and light clients rely on the signed header chain and validator set transitions to verify state without running the protocol. ### 4.4 Nakamoto Consensus and Proof of Work **Definition:** Nakamoto consensus, introduced by Bitcoin, achieves agreement on a chain of blocks in an open, permissionless network without fixed membership, by making block production a proof-of-work lottery and adopting the chain with the most accumulated work as the canonical history. Agreement is probabilistic and eventual: a transaction buried under enough subsequent blocks is reversed with probability that decreases exponentially in the number of confirmations, but there is no point at which a block is formally final. Sybil resistance comes from the cost of computation rather than from identity, so the security assumption is that a majority of hash power is honest, and the incentive design — block rewards and fees paid to the miner of an accepted block — is part of the consensus mechanism rather than an add-on. **Execution flow:** 1. Nodes relay transactions to the network, and each mining node assembles a candidate block from its mempool, including the hash of the current chain tip. 2. The miner searches for a nonce such that the block header hash falls below the current difficulty target, varying the nonce and other header fields. 3. When a valid proof of work is found, the miner broadcasts the block, and other nodes verify the proof, the transactions and the parent reference. 4. Nodes adopt the block if it extends the chain with the most accumulated work they know; if two blocks compete, nodes keep both branches and work on the first they received. 5. The tie resolves when one branch is extended further, at which point nodes reorganise onto the heavier branch and return the losing branch's transactions to the mempool; difficulty is periodically retargeted to hold the average block interval constant as hash power changes. **Edge cases:** Selfish mining shows that the honest-majority threshold is not the whole story: a miner that strategically withholds blocks can earn disproportionate revenue with substantially less than half the hash power, depending on network propagation. Confirmation latency and low throughput are intrinsic, because the block interval must be long relative to propagation time to keep the accidental fork rate low. Energy consumption and mining centralisation in pools are systemic concerns, and the finality being only probabilistic makes the protocol awkward for applications that need a definite point at which a payment is settled. ### 4.5 Proof of Stake and Finality Gadgets **Definition:** Proof-of-stake consensus replaces computational work with economic stake as the Sybil-resistance and leader-election resource: validators lock a deposit, are selected to propose and attest in proportion to their stake, and can be penalised by slashing, the destruction of part of their deposit, if they sign conflicting messages. Ethereum's design pairs a fork-choice rule, LMD-GHOST, which grows the chain using the latest attestation weights, with a finality gadget, Casper FFG, in which validators vote on checkpoints and a checkpoint supported by at least two thirds of total stake becomes justified, and then finalised when the next checkpoint is justified on top of it. This two-layer structure separates chain growth, which is responsive and fork-tolerant, from finalisation, which gives an explicit point after which reversion would require at least one third of stake to be provably destroyed. **Execution flow:** 1. Validators deposit stake and are assigned duties by a pseudorandom selection process for slots and committees in each epoch. 2. In each slot, the selected proposer publishes a block, and committee members attest to the head of the chain and to the current finality checkpoint pair. 3. Attestations are aggregated and included in later blocks, and the fork-choice rule weighs the accumulated attestations supporting each branch to choose the canonical head. 4. When votes for a checkpoint reach two thirds of total staked balance, the checkpoint is justified; when a checkpoint's child is justified, the parent becomes finalised. 5. If a validator signs two conflicting attestations or proposals covered by the slashing conditions, anyone can submit the evidence, the validator's stake is partly burned, and it is ejected from the validator set. **Edge cases:** Weak subjectivity is a distinctive consequence: a node that has been offline for a long period cannot safely determine the canonical finalised chain from genesis alone, because long-range attacks can construct an alternative history with old, withdrawn keys, so it needs a recent trusted checkpoint. Nothing-at-stake behaviour, voting for multiple branches at no cost, is controlled by slashing conditions and by fork-choice rules that only count the latest message from each validator. Inactivity leaks handle the liveness failure where more than one third of validators go offline and finality stalls, by gradually draining the balance of non-attesting validators until the active set again exceeds two thirds. ### 4.6 DAG-Based and Asynchronous BFT **Definition:** A family of modern protocols replaces the single linear chain of leader proposals with a directed acyclic graph of certified blocks or vertices, so that many validators propose concurrently and the ordering is extracted from the graph structure afterwards. Systems such as Narwhal and Bullshark, Aleph, and DAG-Rider separate data dissemination from ordering: a mempool layer reliably broadcasts and certifies blocks, guaranteeing availability, and a consensus layer interprets the resulting DAG, committing whole waves or anchors and ordering all the blocks in their causal history deterministically. Fully asynchronous protocols in this family, such as HoneyBadgerBFT and the DAG-Rider lineage, avoid timing assumptions altogether by using reliable broadcast and common-coin randomness, trading higher latency for robustness against adversarial scheduling and network attacks that target timeouts. **Execution flow:** 1. In each round, every validator creates a block containing transactions, references to blocks from the previous round, and its signature, and reliably broadcasts it. 2. Validators that receive a block verify it, store it, and issue a signed acknowledgement or certificate share, so that a certified block is guaranteed to be available to all honest validators. 3. Once a validator has collected the required number of certified blocks for a round — typically 2f+1 — it advances to the next round and references those blocks, growing the DAG. 4. Periodically, an anchor or leader block for a wave is selected, either by a predetermined schedule or retrospectively by a common coin, and validators determine whether the anchor is committed by counting the votes for it in the following rounds. 5. When an anchor commits, all blocks in its causal history that have not yet been ordered are deterministically ordered by a topological rule and delivered to the application, and the process continues for the next wave. **Edge cases:** Throughput gains come from parallel dissemination, but the DAG can grow large, so garbage collection must be coordinated so that no validator prunes blocks another still needs for ordering. Asynchronous protocols have expected constant-round but high-constant-factor behaviour, and their latency under an adversarial scheduler can be much worse than a leader-based protocol on a healthy network, which is why several production systems run an optimistic synchronous path with an asynchronous fallback. Retrospective leader selection prevents an adversary from knowing which block to suppress, but it also means a wave can fail to commit its anchor and must be skipped, which complicates latency accounting. ## Stage 5 — Scaling & Performance ### 5.1 Pipelining and Batching **Definition:** Pipelining and batching are the two most basic throughput techniques in consensus implementations. Batching amortises the fixed cost of a consensus round — message handling, signature operations, quorum communication — over many client requests by grouping them into a single proposal, so the protocol agrees on a batch rather than on each request individually. Pipelining overlaps the phases of successive consensus instances, so that while one batch is in its commit phase, the next is already in its prepare phase and a third is being formed, keeping the network and the replicas busy instead of waiting for each instance to finish. In blockchain-style protocols such as HotStuff, pipelining is built into the design, because each proposal simultaneously votes on its parent, whereas in classical multi-Paxos and PBFT implementations it is added by running many instances concurrently with a sliding window. **Execution flow:** 1. Requests arriving at the leader are accumulated into a batch until either a maximum batch size is reached or a short batching timer expires. 2. The leader assigns the batch the next sequence number and starts the consensus phases for it without waiting for earlier batches to complete, subject to a window limit on outstanding instances. 3. Replicas process the phases of several instances concurrently, using sequence numbers to keep the state of each instance separate. 4. As instances complete, their batches are executed in strict sequence-number order, so a batch that finishes early waits for its predecessors before being applied. 5. Replies are sent to clients once their batch has executed, and the window slides forward to admit new batches. **Edge cases:** Large batches improve throughput but worsen latency for the first request in a batch and increase the cost of a failed round, because more work is discarded or retried, so batch size is a tuning trade-off rather than a free win. A window that is too large creates head-of-line blocking in the execution stage and can exhaust memory with buffered, out-of-order completions. Under low load, batching timers dominate latency, which is why production systems make the timer adaptive or bypass batching entirely when the queue is short. ### 5.2 Signature Aggregation and Threshold Signatures **Definition:** Signature costs are often the real bottleneck in Byzantine consensus, because a naive implementation verifies 2f+1 individual signatures for every quorum, at every replica, in every phase. Signature aggregation and threshold signatures attack that cost directly. With aggregation, many signatures on the same message are combined into one short object that can be verified in a single operation, as with BLS signatures. With a threshold signature scheme, the replicas hold shares of a single group private key, any 2f+1 shares can be combined into one group signature, and no smaller set can produce one, so a quorum certificate becomes a single signature that anyone can verify against the group public key. This is what makes linear-authenticator protocols such as HotStuff practical, and it also shrinks certificate size for light clients and for on-chain verification. **Execution flow:** 1. During setup, the group key is generated, ideally by a distributed key generation protocol so that no single party ever knows the full private key, and each replica receives its share. 2. When a replica votes, it produces a partial signature on the proposal or block hash using its share and sends it to the aggregator, usually the leader. 3. The aggregator collects partial signatures until it holds the threshold number, then combines them into a single threshold signature. 4. The combined signature is attached to the proposal or quorum certificate and broadcast as the proof that a quorum voted. 5. Any replica or external verifier checks the single signature against the group public key and treats the quorum as established if it verifies. **Edge cases:** Distributed key generation is operationally complex and must be repeated or reshared when membership changes, which is a major cost in dynamic validator sets. Aggregation schemes based on pairings have different performance and security assumptions from Schnorr-based schemes, and some aggregation methods are vulnerable to rogue-key attacks unless proofs of possession are required at registration. Threshold signatures also hide which replicas voted, which conflicts with accountability designs that need to identify misbehaving validators from their individual signed votes. ### 5.3 Sharding and Parallel Chains **Definition:** Sharding scales consensus by partitioning the state and the validator set into multiple groups, called shards, each of which runs its own consensus instance over its own portion of the state, so that total throughput grows with the number of shards instead of being bounded by what one replica group can process. The hard problems move rather than disappear: a transaction touching state in two shards needs an atomic cross-shard protocol, validators must be assigned to shards unpredictably so that an adversary cannot concentrate its power in one shard, and the security of each shard is weaker than the security of the whole set because a shard is a smaller sample. Designs range from fully independent parallel chains with cross-chain messaging, through sharded state machine replication inside one data centre, to blockchain systems such as Ethereum's rollup-centric roadmap, where execution is pushed to layer-two systems and the base chain provides ordering and data availability. **Execution flow:** 1. The state space is divided by a partitioning function, usually a hash of the account or key, and each partition is assigned to a shard. 2. Validators are assigned to shards by a randomness-driven sampling procedure and are periodically reshuffled. 3. A client submits a transaction to the shard that owns the relevant state, and that shard orders and executes it through its own consensus instance. 4. For a cross-shard transaction, the source shard locks or debits its side and emits a receipt or proof, the destination shard verifies the proof and credits its side, and an atomicity mechanism ensures both sides complete or neither does. 5. Shards periodically publish commitments, such as state roots or checkpoint blocks, to a coordinating chain or beacon layer, which provides a global reference point for cross-shard verification and for light clients. **Edge cases:** Cross-shard transactions can dominate the design if the workload does not partition cleanly, and hot keys, such as a popular account or a global counter, can overload a single shard regardless of how many shards exist. The single-shard takeover problem means sampling must be large enough that the probability of an adversary controlling a quorum inside any shard is negligible, which sets a floor on shard size and therefore on how much scaling is available. Data availability for shards that publish only commitments must be handled separately, with techniques such as data availability sampling, or a shard can commit to data that nobody can reconstruct. ### 5.4 Leader Bottlenecks and Leaderless Designs **Definition:** In leader-based protocols the leader does disproportionate work: it receives all requests, forms all proposals, and in many designs collects and distributes all votes, so the leader's bandwidth and CPU bound the throughput of the whole system even though the other replicas are underused. Leaderless and multi-leader designs try to remove that asymmetry. Some protocols let every replica propose concurrently and then order the proposals, as in DAG-based systems and in multi-leader Paxos variants such as EPaxos, which exploits commutativity to commit commands without a single ordering point when they do not conflict. Others rotate or share the proposal load across rounds, or separate dissemination from ordering so that the expensive data movement is spread over all replicas while a lightweight ordering layer decides the sequence. **Execution flow:** 1. The system first identifies where the bottleneck actually is, by measuring the leader's network egress, signature operations, and request-handling CPU against the followers'. 2. If dissemination dominates, transaction data is spread through a dissemination layer in which all replicas broadcast batches and exchange certificates of availability. 3. Proposals then carry only references or hashes of the already-disseminated batches, so the leader's messages are small and its bandwidth no longer scales with transaction volume. 4. Ordering is performed on those references by the consensus layer, whether by a rotating leader, by multiple concurrent proposers, or by an anchor rule over a DAG. 5. Replicas retrieve any referenced batch they are missing, execute the ordered references, and produce the same state as every other replica. **Edge cases:** Removing the leader removes a convenient place to impose order and to deduplicate client requests, so leaderless systems need explicit mechanisms for both, and conflicting concurrent proposals can create extra resolution work. Multi-leader protocols that rely on commutativity perform very well when commands touch disjoint state and degrade towards leader-based behaviour, or worse, when the workload is contended. Operational simplicity also counts against leaderless designs: a single leader is easy to monitor, rate-limit and blame, whereas a symmetric protocol can fail in ways that are harder to attribute. ### 5.5 Benchmarking, Throughput and Latency **Definition:** Benchmarking a consensus system means measuring throughput, usually in transactions or operations per second at saturation, and latency, usually the time from client submission to a committed reply, reported as a distribution rather than a single average. The two are linked: as offered load approaches the system's capacity, latency rises sharply, so a meaningful benchmark reports latency at specified load levels and identifies the saturation point. Consensus benchmarks are notoriously easy to distort, because results depend on batch size, signature scheme, payload size, network topology, disk flush policy, the number of clients, and whether the measurement includes execution and client-side verification or only the ordering layer. Honest evaluation therefore states the whole configuration and separates the cost of consensus from the cost of the application on top of it. **Execution flow:** 1. Define the workload: operation mix, payload size, contention level, number of clients, and whether clients are co-located with replicas or remote. 2. Fix the system configuration: replica count, fault threshold, batch parameters, signature scheme, and durability settings, and record them with the results. 3. Warm the system up until caches, connections and logs are in steady state, then increase offered load in steps. 4. At each load level, measure completed throughput and the latency distribution, including median and high percentiles, over a sustained interval. 5. Identify the saturation point where throughput stops rising and latency grows without bound, and report the highest load at which the latency objective is still met. **Edge cases:** Closed-loop load generators, which only issue a new request when a previous one completes, hide overload by throttling themselves, so open-loop generation is needed to find true saturation. Tail latency in consensus is usually caused by view changes, garbage collection, disk flushes, or a slow replica delaying a quorum, and a benchmark that never injects a fault will not reveal any of it. Comparing protocols measured on different hardware or with different durability guarantees is meaningless, and the common trick of disabling fsync or signatures for a headline number should be treated as measuring a different system. ### 5.6 Speculation, Optimistic Execution and Fast Paths **Definition:** Many consensus implementations add an optimistic path that assumes the common case — a stable leader, no conflicts, no failures — and does work early, before the protocol has formally committed it, in order to cut latency. In PBFT-style systems, replicas may execute a request speculatively after the prepare phase and roll back if a view change invalidates it, as in the Zyzzyva protocol, which achieves very low latency when all replicas agree and no faults occur, at the cost of a more complex recovery path when the assumption fails. In leader-based log replication, followers may apply entries optimistically, and clients may be given fast-path read results based on leases or on a quorum of read replies. The general pattern is a bet: the optimistic result is almost always right, and the protocol must be able to detect the rare case where it is wrong and repair it without ever having exposed an incorrect committed result. **Execution flow:** 1. A replica reaches an intermediate protocol state that makes an outcome highly likely, such as holding a prepared certificate or receiving a leader's proposal in the expected order. 2. It executes the request speculatively and may return a tentative reply, clearly dependent on final commitment. 3. The protocol continues to its normal commit point, and the speculative execution is confirmed if the committed value matches. 4. If the committed value differs, or a view change discards the speculative state, the replica rolls back to the last committed state, using an undo log or a snapshot, and re-executes in the correct order. 5. Clients that received speculative replies are either required to collect enough matching replies to trust the result, as in Zyzzyva's 3f+1 matching replies rule, or are informed that the reply was tentative. **Edge cases:** Rollback must be complete, including any external side effects, which is why speculation is only safe for operations whose effects can be contained inside the replicated state until commit; sending an email or actuating a device cannot be undone. Speculative protocols have historically been a rich source of subtle bugs, because the fast path is tested constantly while the recovery path runs only during failures. There is also a security dimension: an adversary that can repeatedly force the slow path can degrade the system to worse than the non-speculative baseline, so the fallback must be efficient in its own right. ## Stage 6 — Verification & Operations ### 6.1 Formal Specification and Model Checking **Definition:** Formal specification means writing the protocol's intended behaviour in a precise mathematical language, such as TLA+, PlusCal, Ivy, or Coq, so that its properties can be checked mechanically rather than argued informally. Model checking then explores the state space of a finite instance of the specification, searching exhaustively for a state that violates a stated invariant, such as two replicas deciding differently or a committed log entry being lost. This approach has become standard practice for serious consensus work: Raft's design was accompanied by a TLA+ specification, and large cloud providers routinely model-check the protocols behind their storage systems, because the failures that matter are usually interleavings that no human reviewer and no test suite would think to construct. **Execution flow:** 1. The designer writes a specification of the protocol's state variables and the transitions corresponding to each message handler and failure event. 2. The safety invariants and, where feasible, liveness properties are stated as formulas over that state. 3. A model checker is run on small configurations, such as three or four replicas with a bounded number of rounds and values, and it either proves the invariant holds over the reachable states or returns a counterexample trace. 4. Any counterexample is examined to determine whether it is a genuine protocol bug or an artefact of an over-permissive model, and the specification or the protocol is corrected accordingly. 5. The specification is kept alongside the implementation as documentation and is re-checked whenever the protocol is modified. **Edge cases:** State explosion limits model checking to small instances, so a clean result for four replicas is strong evidence but not a proof for all sizes; that gap is addressed by inductive invariant proofs, which are much more labour-intensive. The specification can diverge from the code, and a verified model of a protocol that the implementation does not actually follow gives false confidence, which motivates refinement-based and code-level verification in critical systems. Liveness checking is harder than safety checking because it requires fairness assumptions, and many projects verify safety formally while testing liveness empirically. ### 6.2 Testing, Fault Injection and Chaos Engineering **Definition:** Testing a consensus system is fundamentally about testing behaviour under faults, because the protocol's interesting code paths only execute when leaders fail, messages are dropped, or nodes are partitioned. Fault injection deliberately introduces those conditions — killing processes, delaying or dropping packets, corrupting disks, skewing clocks — in a controlled environment, and chaos engineering extends the practice to production-like and sometimes production systems on the theory that faults should be discovered on the operator's schedule rather than the fault's. Deterministic simulation testing, used prominently by FoundationDB and TigerBeetle, takes a different route: the entire system runs in a single-threaded simulated environment with a seeded random scheduler and network, so that millions of fault scenarios can be explored and any failure can be replayed exactly from its seed. **Execution flow:** 1. Build a test harness that can start a cluster, drive client load, and observe the committed state from outside the cluster. 2. Define the fault scenarios to inject: leader kill during load, minority and majority partitions, slow replicas, disk latency spikes, clock skew, and repeated rolling restarts. 3. Run each scenario while continuously checking invariants from the client's perspective, such as linearizability of reads and writes and the absence of acknowledged writes being lost. 4. When a check fails, capture the logs, the fault schedule, and the random seed so the failure is reproducible, and minimise the scenario if possible. 5. Fix the underlying defect, add the scenario to the regression suite, and re-run the full fault matrix before release. **Edge cases:** Fault injection in production carries real risk and requires blast-radius controls, automatic aborts, and a clear understanding of which failures the system is actually designed to survive. Random testing finds shallow bugs quickly and deep bugs rarely, so the fault distribution and the invariant checker matter more than the raw number of runs. A checker that is too weak is the most common failure of the whole approach: clusters can pass thousands of chaos runs while silently violating a property nobody asserted. ### 6.3 Membership Changes and Reconfiguration **Definition:** Reconfiguration is the problem of changing the set of processes that run consensus — adding replicas, removing failed ones, replacing hardware, or changing the quorum size — while the system continues to operate and without ever creating a situation in which two different configurations can both make decisions independently. It is one of the most dangerous operations in a consensus system, because safety rests on quorum intersection, and two configurations whose quorums do not intersect across the change can decide conflicting values. The standard solutions are joint consensus, in which decisions during the transition require quorums from both the old and the new configuration, and single-server changes, in which membership changes by one member at a time so that any two consecutive configurations overlap sufficiently, as used by Raft. **Execution flow:** 1. An operator or an automated controller proposes a new configuration, which is itself entered as a special entry in the replicated log. 2. On committing that entry under the transitional rule — joint quorums of old and new configurations, or a single-server step — the new configuration becomes active for subsequent decisions. 3. New replicas joining the system first receive a snapshot of the state and then the log entries after the snapshot, and only begin voting once they are caught up. 4. Removed replicas are told to step down, or are fenced by the configuration change, so that they cannot continue to act as leaders or voters. 5. The system records the new configuration durably at every replica, and subsequent reconfigurations proceed from it. **Edge cases:** Reconfiguration during a partition or during a leader failure is where most real-world split-brain incidents originate, and conservative implementations refuse membership changes unless the current configuration is healthy. Removing a replica that is actually the only holder of some committed state is prevented by the commit rule, but removing several replicas in quick succession can still outrun the safety argument if the steps are batched informally by an operator. Automatic reconfiguration driven by a failure detector can also oscillate, repeatedly adding and removing a flapping replica, so hysteresis and operator approval for large changes are common safeguards. ### 6.4 Observability, Metrics and Debugging **Definition:** Observability for a consensus system means being able to determine, from metrics, logs and traces, what the protocol is doing internally: who the leader is, how far each replica's log extends, how long each protocol phase takes, how often view changes or elections occur, and whether the commit index is advancing. Consensus failures are otherwise nearly undiagnosable, because the external symptom — requests timing out — is the same for a dead leader, a network partition, a disk bottleneck, and a protocol bug. Well-designed systems expose a small set of high-signal metrics, such as election frequency, commit latency, quorum latency, log replication lag per follower, and the rate of rejected AppendEntries or vote requests, and they log every leadership and configuration transition with its term or view number. **Execution flow:** 1. Instrument the protocol at its phase boundaries: proposal, quorum achieved, commit, apply, and reply, recording a timestamp and the relevant term, view, and index for each. 2. Export counters and histograms for elections, view changes, votes granted and denied, log mismatches, and snapshot transfers, labelled by replica. 3. Build dashboards and alerts around the signals that precede outages, such as rising election rates, a commit index that has not advanced, or one follower consistently lagging. 4. When an incident occurs, use the term and index information to reconstruct the sequence of leadership changes and identify the first point where replicas diverged or stalled. 5. Feed the findings back into testing, by turning the incident's conditions into a fault-injection scenario. **Edge cases:** Excessive per-message logging can itself become the bottleneck and can change the timing behaviour being measured, so production systems log transitions and errors rather than every protocol message. Metrics that average across replicas hide exactly the outlier replica that is causing quorum delays, so per-replica and percentile views are essential. Debugging a safety violation after the fact requires durable evidence — signed votes, log contents, and configuration history — which is why accountable and forensic designs preserve vote records rather than discarding them at commit. ### 6.5 Upgrades, Persistence and Recovery Operations **Definition:** Operating a consensus system over years requires upgrading its software, maintaining its persistent state, and recovering from disasters, all without violating the protocol's assumptions. Persistence is part of the protocol, not an implementation detail: the current term, the vote cast, the log, and the commit index must be stored with specific flush semantics, because a replica that forgets a vote it already cast can break safety after a restart. Upgrades are delicate because a rolling upgrade temporarily runs a mixed-version cluster, so protocol changes must be backward compatible at the message level or gated behind a configuration or feature flag that activates only when all replicas support them. Recovery operations, such as restoring from backup or rebuilding a replica, must respect the same rules, because a restored replica with stale state rejoining as a voter is a classic source of data loss. **Execution flow:** 1. Before an upgrade, verify that the cluster is healthy, fully replicated, and has a recent snapshot or backup whose integrity has been tested. 2. Upgrade replicas one at a time, starting with followers, waiting after each one for it to rejoin, catch up, and resume voting before proceeding. 3. Upgrade the leader last, or trigger a controlled leader transfer to an already-upgraded follower, so that leadership is never held by a replica that is about to stop. 4. Activate any new protocol behaviour only after all replicas report the new version, using a version gate recorded in the replicated configuration. 5. For recovery, provision a replacement replica with an empty or snapshot-based state, let it catch up as a non-voting learner, and promote it to voter through a normal reconfiguration once it is current. **Edge cases:** Restoring a whole cluster from backup is a safety-critical decision: if any client received a commit acknowledgement for data that is not in the backup, restoring it silently loses committed data, so the operation must be treated as a declared data-loss event, not a routine repair. Downgrades are often impossible once the on-disk format has changed, which means an upgrade plan without a tested rollback is incomplete. Disk corruption that passes undetected can make a replica vote from false state, so checksums on log entries and periodic state verification between replicas are worth their cost. ### 6.6 Accountability, Forensics and Governance **Definition:** Accountability extends consensus beyond deciding correctly among live participants: it asks whether, when something goes wrong, the system can produce cryptographic evidence of who misbehaved. In accountable Byzantine systems, conflicting signed votes, double proposals, or inconsistent quorum certificates can be assembled into a proof that identifies a set of replicas that must include the culprits, which is the basis for slashing in proof-of-stake systems and for forensic protocols that determine culpability after a safety violation. Governance is the surrounding human and institutional layer: who may change the validator set, set parameters such as timeouts and batch sizes, approve upgrades, and decide what to do when the protocol's assumptions are exceeded and automatic recovery is impossible. **Execution flow:** 1. During normal operation, replicas retain signed protocol messages, or compact hashes of them, so that the evidence needed to attribute a fault is not discarded. 2. When a safety violation or a serious liveness failure is detected, an investigator collects the relevant signed messages from multiple replicas. 3. The forensic procedure checks the messages against the protocol rules and identifies the replicas whose signatures appear on mutually inconsistent statements. 4. The identified evidence is published or submitted to the governing body, which applies the predetermined consequence, such as slashing stake, removing the validator, or filing an incident report. 5. If the violation exceeds what the protocol can attribute or repair, governance coordinates an explicit recovery, such as a coordinated restart from an agreed checkpoint, and records the decision and its rationale. **Edge cases:** Accountability has limits: if the number of Byzantine replicas exceeds the assumed threshold, forensic procedures may be unable to distinguish culprits from honest replicas that were misled, and honest replicas must not be punishable in that regime. Retaining all signed messages indefinitely is expensive, so systems must choose a retention window that matches the time within which a violation would realistically be detected and disputed. Governance itself is an attack surface, because the keys or votes that control validator membership and upgrades are worth more than any single replica, and they require their own protection, transparency, and separation of duties.