Distributed Consensus — Paxos, Raft, PBFT, and Nakamoto Consensus

01Consensus is not another word for unanimity

• Processes in a distributed system do not observe the same event at the same instant. Messages are delayed and reordered, some participants stop while others continue, and some may send contradictory information. Once the system decides that value A occupies a particular log position, the central job of consensus is to prevent correct participants from finalising value B in that same position.
• Consensus therefore does not require every node to display the same state at the same moment or every participant to cast an affirmative vote. Some nodes may still be unaware of a decision or may be offline; intersecting quorums prevent a conflicting decision even without simultaneous knowledge.
• Paxos, Raft, PBFT, and Bitcoin all order actions among multiple parties, but they are not interchangeable algorithms. A replicated service with named servers and an open network where anyone can create pseudonyms differ at the first question: who is entitled to count as one participant?

02From one decision to a replicated log

• The classical one-shot consensus problem gives processes candidate values and asks correct processes to decide one value. The usual properties are Agreement, meaning correct participants do not decide differently; Validity, meaning the decision satisfies a stated legitimacy condition; Integrity, meaning a participant does not decide twice; and Termination, meaning correct participants eventually decide. The exact definition of Validity varies across papers.
• A service needs more than one decision. It places commands into log slots 1, 2, 3, and onward by running consensus repeatedly, then applies that common order to deterministic state machines with the same initial state. This is the foundation of state-machine replication.
• Consensus and atomic broadcast are closely related. Delivering the same messages in the same order can construct a replicated log, while consensus per slot can construct ordered broadcast. A production system still extends beyond the one-shot theorem to recovery, duplicate requests, reconfiguration, snapshots, and client replies.

03Read the assumptions before the protocol name

• The first comparison should not be transactions per second but assumptions. Are participants enrolled servers or open peers? Can a fault only stop, or can it lie and equivocate? Is message delay bounded? Is influence weighted by identity, stake, or computational work? Does a decision become irreversible at a defined certificate, or merely less likely to reverse with time?

• Words such as “distributed” or “BFT” do not answer these questions. A guarantee belongs to a pair of assumptions and conclusions, not to a protocol brand in isolation.

04Separate safety from time, then return liveness to time

• A synchronous model has known bounds on processing and message delivery. A fully asynchronous model has no such bounds, so silence cannot prove whether a peer has stopped or is merely slow. Partial synchrony lies between them: bounds exist but are initially unknown, or begin to hold only after an unknown point.
• The FLP result says that under full asynchrony, a deterministic consensus protocol cannot guarantee Termination in every admissible execution if even one process may crash. It does not say practical agreement can never occur. Real protocols add conditions such as eventual network stability, a leader that remains available for long enough, or randomness.
• Many practical designs preserve Safety — never producing two conflicting decisions — however long the network is delayed, while promising Liveness only after communication becomes sufficiently stable. A timeout is not proof of failure; it is a mechanism for trying a different leader or round.

05Quorum intersection — what a majority is really for

• A quorum is not a popularity poll. Its purpose is to force decision sets to intersect. In a crash-tolerant configuration of `2f+1` nodes, any two majorities share at least one node. That overlap carries previously accepted information into a later round and prevents another value from being chosen for the same slot.
• If the overlap could consist entirely of Byzantine nodes, it could lie. A BFT design using quorums of `2f+1` among `3f+1` replicas makes any two quorums overlap in at least `f+1` replicas, including at least one correct replica. Thresholds follow from the fault model and the property being proved.
• Bitcoin does not count registered node identities toward a quorum because anyone can create many identities. It weights competing valid histories by accumulated proof of work, attaching proposal influence to a scarce computational resource rather than a count of names. This is a different participation model, not a simple substitution for majority quorum.

06Paxos — preserving a value once a majority chooses it

• Paxos chooses one value safely among a known set of acceptors while tolerating crash faults. A proposer uses uniquely ordered ballot numbers. In Phase 1 it asks acceptors for promises not to accept lower ballots and collects the highest-ballot value each has already accepted.
• In Phase 2, the proposer must carry forward the value with the highest accepted ballot reported in Phase 1, if one exists; otherwise it may introduce a new value. A value accepted by a majority is chosen. These constraints ensure that a later proposer using a higher ballot cannot cause a different value to be chosen in the same instance.
• Basic Paxos chooses one value. Multi-Paxos applies consensus to successive log slots and reuses Phase 1 under a stable leader to advance a replicated log efficiently. `2f+1` acceptors tolerate `f` crashes, but the service stops safely if it loses a communicating majority.
• Paxos is not another name for two-phase commit. 2PC coordinates whether every participant commits a transaction and can block after coordinator failure; Paxos chooses one proposal among candidates. A transaction system may combine them, but their problem statements differ. Ordinary Paxos also does not tolerate acceptors that lie arbitrarily.

07Raft — making leader, term, and log explicit

• Raft is a crash-tolerant replicated-log protocol designed around understandability and intended to produce a result equivalent to Multi-Paxos. Servers are followers, candidates, or leaders, and execution is divided into monotonically increasing terms. A follower that misses heartbeats becomes a candidate; only a candidate receiving votes from a majority in one term becomes leader.
• The leader replicates entries using AppendEntries RPCs. Its central properties include Log Matching — logs sharing an index and term share every preceding entry — Leader Completeness — a committed entry remains in leaders of later terms — and State Machine Safety — servers never apply different commands at the same index.
• A leader advances commitment after an entry from its current term is stored on a majority. Uncommitted suffixes may be overwritten by a later leader, while election restrictions preserve committed entries. Membership changes use joint consensus so quorums of the old and new configurations overlap during transition.
• Randomised election timeouts reduce repeated split votes and aid progress, but they do not make Raft Byzantine tolerant. A malicious server intentionally sending conflicting logs is outside ordinary Raft’s fault model.

08Byzantine agreement and PBFT — including replicas that lie

• A Byzantine fault includes more than stopping: a process may equivocate by sending different values to different peers, corrupt messages, or deviate arbitrarily from the protocol. The model covers malicious compromise but also software bugs and corruption that produce arbitrary behaviour.
• The 1982 Byzantine Generals paper showed that oral messages require at least `3m+1` generals to tolerate `m` traitors. Unforgeable signatures change the conditions. Yet signatures alone do not complete consensus on an open network: the system must still determine which public keys count as replicas.
• PBFT uses `3f+1` known, authenticated replicas to replicate a deterministic state machine with up to `f` Byzantine faults. A primary pre-prepares an order, replicas prepare and commit it, and the protocol collects certificates from `2f+1` replicas. A client waits for `f+1` matching replies, ensuring that at least one came from a correct replica.
• PBFT Safety does not depend on message delay, but Liveness needs a weak synchrony assumption under which correct nodes and messages cannot be delayed forever. Its `3f+1` bound also presumes known membership and sufficiently independent replica failures. An open system must establish that premise by some additional mechanism.

09Nakamoto consensus — weighting open participation by resources

• The Bitcoin whitepaper does not use the term “Nakamoto consensus.” What later acquired that name combines peer-to-peer broadcast, independent rule validation, proof-of-work block proposals, a chain-selection rule, and incentives.
• Miners search for a block-header hash at or below a target. Success acts as probabilistic leader election proportional to hashpower. The whitepaper’s phrase “one-CPU-one-vote” contrasts computational resource with IP addresses or pseudonym counts; in an ASIC-dominated network, hashpower-weighted is the more accurate description.
• When valid blocks are found at nearly the same time, a temporary fork appears. Each full node considers only blocks it has validated and converges on the valid chain that is hardest to recreate — the one with the most accumulated proof of work. It is not simply the chain with the largest block count, and proof of work cannot make an invalid chain valid.
• Formal work describes the Bitcoin backbone through properties such as common prefix, chain quality, and chain growth, then constructs a ledger with transaction persistence and liveness. Garay, Kiayias, and Leonardos do not treat the original suggestion alone as a general Byzantine Agreement solution; they state additional protocols and assumptions about hashpower and network synchrony. Bitcoin solves a different problem under a different guarantee.

10Finality — chosen is not the same as deeply buried

• Finality asks what makes a decision no longer reversible. Once a value is chosen in a Paxos instance, another value cannot be chosen in that instance, although every learner may not know the decision immediately. Raft likewise distinguishes a committed entry from one present only in a leader’s local log.
• PBFT gives deterministic finality to an operation backed by a commit certificate within its fault threshold. Bitcoin permits competition at the tip as ordinary operation; each additional block reduces the probability of a reorganisation. Confirmations are probabilistic safety margin, not a protocol constant at which reversal becomes mathematically impossible.

• Deterministic does not mean fast, and probabilistic does not mean unsafe. A deterministic protocol can stop when it loses quorum; a probabilistic protocol can provide strong practical assurance at sufficient depth under dispersed hashpower. Applications compare halt risk with reorganisation risk.

11Who agrees on what in Bitcoin?

• Bitcoin nodes do not all exchange explicit votes and decide simultaneously. A wallet constructs and signs a transaction, then broadcasts it to peers. Full nodes independently validate transactions and blocks against consensus rules. Miners assemble valid transactions into candidate blocks and compete on proof of work.
• Mining proposes and orders candidate history and contributes to its rewrite cost. Even a block with enormous proof of work is rejected by full nodes if it creates an excessive coinbase output, contains an invalid signature, or double-spends. Hashpower is not a vote that turns invalid data into valid data.
• It helps to distinguish the consensus rules enforced by full nodes from the consensus mechanism that converges on one history among competing valid histories. Users, exchanges, merchants, and other economic actors choose which software and rules they accept. A protocol change is not automatically decided by a node count or miner poll.
• Bitcoin’s agreement concerns transaction validity and which valid block history is currently treated as the best chain. It does not make the chain an oracle for price, legal title, or the truth of arbitrary events in the physical world.

12Reading four designs with one set of questions

• There is no useful single ranking of these protocols. Paxos or Raft fits the assumptions of known servers and crash tolerance. BFT protocols address arbitrary behaviour among known replicas. Bitcoin accepts extra cost and probabilistic finality to maintain a public ledger without a central membership authority.
• The final design question is not only “What trust disappeared?” but “Which assumptions replaced it?” Quorum independence, keys and membership, leader stability, network propagation, hashpower distribution, and users validating rules all remain. Consensus does not abolish trust; it decomposes it into assumptions that can be inspected and tested.