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

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 has decided that value A occupies a given log position, the central job of consensus is to keep correct participants from finalizing value B in that same position.

Consensus therefore does not require every node to show the same state at the same moment, nor every participant to vote yes. Some nodes may not know about a decision yet, and some may be offline; because quorums intersect, a conflicting decision is ruled out even when no one has simultaneous knowledge.

Paxos, Raft, PBFT, and Bitcoin all put actions in order among multiple parties, but they are not interchangeable. A replicated service with named servers and an open network where anyone can mint pseudonyms part company at the very first question: who is entitled to count as one participant?

The classical one-shot consensus problem hands processes candidate values and asks the correct ones to settle on a single value. The usual properties are Agreement, meaning correct participants do not decide differently; Validity, meaning the decision meets a stated legitimacy condition; Integrity, meaning no participant decides twice; and Termination, meaning correct participants eventually decide. What Validity means exactly varies from paper to paper.

A real service needs more than one decision. It runs consensus repeatedly to place commands into log slots 1, 2, 3, and onward, then applies that shared order to deterministic state machines that started from the same state. This is what state-machine replication rests on.

Consensus and atomic broadcast are close relatives. Delivering the same messages in the same order gives you a replicated log, and running consensus per slot gives you ordered broadcast. A production system reaches well past the one-shot theorem, into recovery, duplicate requests, reconfiguration, snapshots, and client replies.

The first thing to compare is not transactions per second but assumptions. Are the participants enrolled servers or open peers? Can a fault only stop a process, or can it lie and equivocate? Is message delay bounded? Is influence weighted by identity, by stake, or by computational work? Does a decision become irreversible at a defined certificate, or only less likely to reverse as time passes?

Words such as “distributed” or “BFT” answer none of these questions. A guarantee belongs to a pairing of assumptions and conclusions, not to a protocol name on its own.

A synchronous model has known bounds on processing and message delivery. A fully asynchronous model has no such bounds, so silence cannot tell you whether a peer has stopped or is merely slow. Partial synchrony sits between them: bounds exist but are unknown at first, or start to hold only after some point nobody can name in advance.

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 that agreement is impossible in practice. Real protocols add conditions: the network eventually settles down, a leader stays available long enough, or the protocol draws on randomness.

Many practical designs hold on to Safety, never producing two conflicting decisions, no matter how long the network is delayed, and promise Liveness only once communication becomes stable enough. A timeout is not proof of failure; it is the mechanism for trying a different leader or round.

A quorum is not a popularity poll. Its job is to force decision sets to overlap. In a crash-tolerant configuration of `2f+1` nodes, any two majorities share at least one node. That shared node carries any previously accepted value forward into a later round, which is what stops a different value from being chosen for the same slot.

If the overlap could consist entirely of Byzantine nodes, it could lie. A BFT design that uses quorums of `2f+1` among `3f+1` replicas makes any two quorums overlap in at least `f+1` replicas, so at least one of them is correct. The 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 as many identities as they like. It weighs competing valid histories by accumulated proof of work, which ties influence over proposals to a scarce computational resource instead of a count of names. That is a different participation model, not a drop-in replacement for a majority quorum.

Paxos safely chooses one value among a known set of acceptors while tolerating crash faults. A proposer uses ballot numbers that are unique and ordered. In Phase 1 it asks acceptors to promise not to accept lower ballots, and collects the highest-ballot value each of them has already accepted.

In Phase 2, the proposer has to carry forward the value with the highest accepted ballot reported in Phase 1, if there is one; otherwise it may introduce a new value. A value accepted by a majority is chosen. These constraints are what make it impossible for a later proposer, using a higher ballot, to get a different value chosen in the same instance.

Basic Paxos chooses a single value. Multi-Paxos applies consensus to successive log slots and reuses Phase 1 under a stable leader, which is what lets a replicated log advance efficiently. `2f+1` acceptors tolerate `f` crashes, but if the service loses a majority it can communicate with, it stops, safely.

Paxos is not another name for two-phase commit. 2PC coordinates whether every participant commits a transaction, and it can block if the coordinator fails; Paxos chooses one proposal among candidates. A transaction system may use both, but they state different problems. Ordinary Paxos also does not tolerate acceptors that lie arbitrarily.

Raft is a crash-tolerant replicated-log protocol built to be understandable, and meant to deliver a result equivalent to Multi-Paxos. A server is a follower, a candidate, or a leader, and execution is divided into terms that only increase. A follower that misses heartbeats becomes a candidate; a candidate becomes leader only by collecting votes from a majority within one term.

The leader replicates entries with AppendEntries RPCs. Its central properties include Log Matching (logs that share an index and term share every preceding entry), Leader Completeness (a committed entry stays present in the leaders of later terms), and State Machine Safety (no two servers apply different commands at the same index).

A leader advances commitment once an entry from its own term is stored on a majority. A later leader may overwrite uncommitted suffixes, while the restrictions on elections keep committed entries in place. Membership changes go through joint consensus, so quorums of the old and new configurations overlap during the transition.

Randomized election timeouts cut down on repeated split votes and help progress along, but they do not make Raft Byzantine tolerant. A malicious server that deliberately sends conflicting logs falls outside ordinary Raft’s fault model.

A Byzantine fault covers more than stopping: a process may equivocate by sending different values to different peers, corrupt messages, or depart from the protocol in any way at all. The model covers malicious compromise, and also software bugs and corruption that produce arbitrary behavior.

The 1982 Byzantine Generals paper showed that oral messages require at least `3m+1` generals to tolerate `m` traitors. Unforgeable signatures change those conditions. But signatures alone do not finish the job on an open network: the system still has to 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, which guarantees 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 their messages cannot be delayed forever. Its `3f+1` bound also assumes known membership and replica failures independent enough of one another. An open system has to establish that premise some other way.

The Bitcoin whitepaper never uses the term “Nakamoto consensus.” What later picked up that name combines peer-to-peer broadcast, independent validation of the rules, proof-of-work block proposals, a chain-selection rule, and incentives.

Miners search for a block-header hash at or below a target. Finding one amounts to a probabilistic leader election, weighted by hashpower. The whitepaper’s phrase “one-CPU-one-vote” sets a computational resource against IP addresses or a count of pseudonyms; in a network dominated by ASICs, weighting by hashpower is the more accurate description.

When valid blocks are found at nearly the same time, a temporary fork appears. Each full node considers only the blocks it has validated itself, and converges on the valid chain that is hardest to recreate: the one with the most accumulated proof of work. That is not the same as the chain with the most blocks, and no amount of proof of work makes an invalid chain valid.

Formal work describes the Bitcoin backbone through properties such as common prefix, chain quality, and chain growth, then builds a ledger with transaction persistence and liveness on top of them. Garay, Kiayias, and Leonardos do not treat the original suggestion by itself as a general solution to Byzantine Agreement; they set out additional protocols and assumptions about hashpower and network synchrony. Bitcoin solves a different problem under a different guarantee.

Finality is the question of what makes a decision no longer reversible. Once a value is chosen in a Paxos instance, no other value can be chosen in that instance, even though not every learner knows the decision right away. Raft likewise separates a committed entry from one that exists only in a leader’s local log.

PBFT gives deterministic finality to an operation backed by a commit certificate, within its fault threshold. Bitcoin treats competition at the tip as normal operation; each additional block lowers the probability of a reorganization. Confirmations are a probabilistic safety margin, not a constant written into the protocol at which reversal becomes mathematically impossible.

Deterministic does not mean fast, and probabilistic does not mean unsafe. A deterministic protocol can halt when it loses its quorum; a probabilistic one can give strong practical assurance at sufficient depth as long as hashpower stays dispersed. Applications weigh the risk of halting against the risk of reorganization.

Bitcoin nodes do not all exchange explicit votes and decide at the same moment. A wallet builds and signs a transaction, then broadcasts it to peers. Full nodes check transactions and blocks against the consensus rules for themselves. Miners assemble valid transactions into candidate blocks and compete on proof of work.

Mining proposes candidate history, puts it in order, and adds to the cost of rewriting it. Full nodes reject a block no matter how much proof of work it carries 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 keep two things apart: the consensus rules that full nodes enforce, and the consensus mechanism that converges on one history among competing valid ones. Users, exchanges, merchants, and other economic actors choose which software and which rules they accept. A protocol change is not settled automatically by a node count or a miner poll.

What Bitcoin agrees on is which transactions are valid and which valid block history is currently treated as the best chain. It does not turn the chain into an oracle for price, legal title, or the truth of arbitrary events in the physical world.

There is no single useful ranking of these protocols. Paxos or Raft fits the assumptions of known servers and crash tolerance. BFT protocols deal with arbitrary behavior among known replicas. Bitcoin accepts extra cost and probabilistic finality in order to keep a public ledger running 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, the distribution of hashpower, and users who validate the rules are all still there. Consensus does not abolish trust; it breaks it into assumptions you can inspect and test.