Distributed Consensus: Agreeing on One Truth Without a Boss

When a P2P network moves beyond distributing data to sharing a ledger or state, it needs a way for everyone to agree on the same content: a distributed consensus algorithm. Here we cover the four representative schemes: PoW, PoS, PBFT, and HotStuff.

Why is distributed consensus hard?

With a central server, the “correct data” is whatever the server says. In a gathering of equal peers, you must assume delayed and lost messages, crashing nodes, and even nodes that lie. This difficulty has been formalized in several famous results.

• The Byzantine Generals Problem: generals camped apart must coordinate “attack together or retreat” using only messengers. Messengers may be lost, and traitorous generals may send contradictory orders to different camps. This thought experiment captures the difficulty of agreement when participants may be malicious, not just faulty. Failures with contradictory behavior are called Byzantine faults.
• The CAP theorem: a distributed system cannot simultaneously provide Consistency, Availability, and Partition tolerance. Since network partitions are unavoidable, real designs choose which of consistency or availability to sacrifice when a partition strikes.
• FLP impossibility: the 1985 theorem that in an asynchronous network (no bound on message delivery time), no deterministic algorithm can guarantee agreement if even one node may crash. Practical systems evade the wall with timeouts, randomness, or economic incentives.

A consensus algorithm, then, is a body of engineering that achieves “agreement good enough in practice” under realistic assumptions within these theoretical limits. Two major families exist: Nakamoto-style (PoW/PoS) for open, permissionless participation, and BFT-style (PBFT/HotStuff) for permissioned settings with known participants.

Organizing by fault model: crash tolerance vs. Byzantine tolerance

The fastest route to understanding consensus algorithms is to classify them by the failures they assume (the fault model). A crash fault is a node that simply goes silent; it never lies. Inside a datacenter, where all participants are under one organization’s control, this assumption suffices, and Paxos and Raft reign. A Byzantine fault is arbitrary misbehavior, not just stopping but lying and contradicting itself, and it must be assumed when participants cannot be trusted: PBFT and HotStuff for known memberships, and PoW/PoS when participation is open.

The required node counts differ fundamentally too: tolerating f crash faults takes only 2f+1 nodes (a majority quorum), while Byzantine tolerance needs 3f+1 to outvote the liars. Below we cover the Proof family, then the crash-tolerant family, then the Byzantine-tolerant family.

Organizing by participation model: consensus for trusted nodes vs. untrusted nodes

The classification so far turned on the fault model: whether you assume only crash faults or must also assume lying, Byzantine faults. A second, independent axis, the participation model, explains why the six schemes take the shapes they do: whether membership is known and fixed, or anyone may freely join and leave.

Consensus for trusted nodes (known membership × crash tolerance only): inside a company’s own datacenter or a Kubernetes cluster, nodes are built and monitored by the same organization. They may crash silently from hardware failure or a network partition, but assuming they never deliberately send false messages is reasonable. Paxos and Raft fit this “trustworthy but imperfect” model best: tolerating f crashes needs only 2f+1 nodes, and communication stays light with no cryptographic voting overhead.

Consensus for known-but-untrusted nodes (known membership × Byzantine tolerance): in a consortium chain or an interbank settlement network, participants’ organizations and identities are known through registration and vetting, but you cannot rule out an operator being bribed or a system being compromised. Here you must assume nodes whose identity is known but whose behavior cannot be trusted: this is the domain of PBFT, HotStuff, and Tendermint, which derives its validator set from stake. Byzantine tolerance requires 3f+1 nodes and the heavier machinery of signatures and multi-round voting, but a bounded, known membership is what makes that cost practical.

Consensus for nodes whose identity is unknown (open participation × Byzantine tolerance): on a public blockchain, nobody can know who is running how many nodes. Since identity cannot back trust, honesty of the majority must instead be backed by an external cost that punishes misuse: compute (PoW) or staked assets (PoS). The price of open participation is machinery absent from known-membership settings, such as probabilistic finality and slashing.

The remaining combination, open participation × crash tolerance only, barely exists in practice: assuming every participant is honest while letting anyone join freely is far too exposed. If you will not pay the cost of verifying identity, you cannot guarantee honest behavior either, which is why open-network consensus, without exception, must assume Byzantine faults.

This framing sharpens where PoS actually sits. All PoS contributes is a permissionless-layer trick: issuing the right to participate via stake instead of identity. Once staking fixes the validator set, agreement inside that set often falls back into the known-membership, Byzantine-tolerant domain (the territory of PBFT and HotStuff). The next section works through concrete examples.

The Proof family: consensus for open networks (PoW / PoS)

PoW (Proof of Work): backing truth with computation

Proof of Work, used by Bitcoin, decides who gets to append the next block through a computational race. Miners search by brute force for a throwaway number (nonce) that makes the block’s hash meet a target condition, such as starting with a run of zeros. The first miner to find one proposes the block and collects the reward.

The crucial property: finding the answer is hard, but verifying it takes an instant. Other nodes compute one hash and immediately confirm that enormous work went into the block. When the chain forks, the rule is simply “the chain with the most cumulative work is the truth.” This is Nakamoto consensus, the first scheme to achieve practical agreement in an open network where anyone may join or leave.

• 51% attacks: an attacker controlling a majority of hash power can reverse transactions (double-spend) or censor them. Conversely, the cost of amassing majority hash power is the security budget. Smaller chains have actually suffered 51% attacks.
• Probabilistic finality: a block only becomes harder to reverse as more blocks pile on top; there is no moment of mathematical finality. Bitcoin’s custom of waiting for six confirmations exists for this reason.
• The energy problem: because security scales with computation, massive electricity consumption is inherent. Criticism of this footprint helped drive the shift to PoS described next.

PoS (Proof of Stake): backing truth with deposited assets

Proof of Stake replaces the computational race with a deposit of currency (a stake) as the ticket to participate. Validators lock up a set amount to register, and the protocol selects block proposers weighted by stake. Other validators vote on proposed blocks (attestations), and blocks are confirmed as the required approvals accumulate.

The deterrent is slashing: when a violation is detected (such as signing two contradictory blocks), part or all of the offender’s stake is confiscated. Where PoW says “attacks cost electricity,” PoS says “attack and your own assets burn”: security through economic penalty.

• The Nothing at Stake problem: the classic critique of early PoS designs. If voting costs nothing, the rational move during a fork is to bet on every branch, and consensus may never converge. Slashing is precisely the fix: contradictory votes themselves are punished.
• Ethereum’s transition (The Merge): in September 2022, Ethereum switched from PoW to PoS without stopping, cutting energy use by more than 99.9%. Validators staking 32 ETH now propose and attest blocks, with explicit finality reached under defined conditions.
• Open issues: concentration of power among large holders, de facto centralization via staking pools, and defenses against long-range attacks (weak subjectivity) remain active research topics specific to PoS.

The crash-tolerant family: consensus among friends (Paxos / Raft)

Paxos: the classic of crash-tolerant consensus

Leslie Lamport’s Paxos is the theoretical foundation of consensus under the crash-fault model. Its core idea is the majority quorum: any two majorities must share at least one node, which guarantees that a value once chosen can never be reversed. There are three roles: Proposers propose values, Acceptors vote to accept them, and Learners learn the outcome (in practice a single node usually plays all three).

Agreement takes two phases. First Prepare/Promise: a proposer sends Prepare with a monotonically increasing proposal number n and gathers, from a majority of acceptors, promises to reject anything below n, along with any value already accepted. Then Accept/Accepted: the proposer sends Accept with “the already-accepted value if any promise contained one, otherwise its own value,” and the value is chosen once a majority accepts. This rule of inheriting accepted values is precisely what makes a chosen value irreversible.

• Why it is called hard: the algorithm itself is short, but the paper leaves out the machinery needed to run it for real, such as dueling proposers (livelock), crash recovery, and state persistence, so every implementer had to interpret it themselves.
• Multi-Paxos: chaining instances of single-value Paxos and installing a stable leader (which lets the Prepare phase be skipped) turns it into a practical log-replication system.
• Deployments: Google’s lock service Chubby, and the Spanner lineage of distributed databases, are built on Paxos.

Raft: consensus designed for understandability

Raft (Ongaro & Ousterhout, 2014) was designed under the banner “the performance and safety of Paxos, in a form people can understand.” It decomposes the problem into leader election, log replication, and safety, and simplifies thinking by always having one strong leader (the original paper is ongaro2014search in the references).

1. Leader election: time is divided into monotonically increasing terms. A follower that misses the leader’s heartbeat within a randomized timeout (e.g. 150-300 ms) becomes a candidate, increments the term, and solicits votes; a majority makes it the new leader. The randomized timeouts elegantly dissolve split votes.
2. Log replication: client commands are appended to the leader’s log and replicated to followers via AppendEntries RPCs. An entry replicated to a majority is committed and applied to each node’s state machine.
3. Safety (Leader Completeness): nodes refuse to vote for candidates whose logs are older than their own, so no node lacking committed entries can become leader, guaranteeing committed commands are never lost.

Understandability translated directly into adoption: etcd at the heart of Kubernetes, and the NewSQL databases TiDB and CockroachDB (huang2020tidb / taft2020cockroachdb in the references). Raft runs everywhere in modern infrastructure.

The Byzantine-tolerant family: consensus that survives traitors (PBFT / HotStuff)

PBFT: the classic BFT consensus for permissioned networks

PBFT (Practical Byzantine Fault Tolerance, 1999) is the classic Byzantine-tolerant consensus for settings with known participants, such as consortium chains and financial systems. With n nodes of which at most f may fail arbitrarily (maliciously), it reaches correct agreement as long as n ≥ 3f+1: 4 nodes tolerate 1 traitor, 7 tolerate 2.

Agreement proceeds in three phases:

1. pre-prepare: the leader (primary) assigns a sequence number to the client’s request and broadcasts the proposal to all replicas.
2. prepare: each replica validates the proposal and sends a prepare message (“I accept this proposal”) to every other node. Collecting 2f+1 of them proves that enough honest nodes have seen the same proposal.
3. commit: nodes then exchange commit messages; on collecting 2f+1, each executes the request and replies to the client, who trusts the result upon f+1 matching replies.

Unlike Nakamoto-style chains where blocks may be reorganized, PBFT has immediate finality: the result is settled at the moment of commit. The price: in the prepare/commit phases every node messages every other node, so traffic grows as O(n²), capping practical deployments at tens to about a hundred nodes. And when the leader fails, a heavyweight “view change” protocol must elect a new one.

HotStuff: modern BFT with linear communication

HotStuff (2019) is a leader-based BFT algorithm that solved PBFT’s communication problem. Its key move: instead of replicas messaging each other, all votes flow to the leader, who bundles 2f+1 of them into a single certificate (a Quorum Certificate, QC) and distributes it in the next round. With threshold signatures the certificate compresses into one signature, bringing per-round communication down to O(n).

Its second hallmark is the three-chain rule: a block is final once three consecutive generations of QCs (corresponding to prepare, precommit, and commit) stack on top of it. This design unifies a consensus phase and a leader change into a single kind of processing, making it cheap to rotate the leader every round. The view change that was PBFT’s heavyweight exception becomes part of normal operation in HotStuff.

• It became widely known when Facebook (now Meta)’s Libra/Diem project adopted it as LibraBFT.
• HotStuff-family consensus (including refinements) remains at the core of high-performance blockchains such as Aptos.
• The design vocabulary (leader aggregation, threshold signatures, chaining) became the common language of subsequent BFT research, from two-round variants to DAG-based consensus.

Where PoS meets BFT consensus: the layer that selects validators, and the layer that turns votes into agreement

Look inside a major PoS chain and you find two clearly separated, stacked layers: a PoS layer deciding who holds voting power, and a BFT consensus layer deciding how collected votes become final agreement. Tendermint, Diem/Aptos, and Ethereum make this layering concrete.

Tendermint (Cosmos): PBFT’s three phases, run with stake-weighted votes

Tendermint is a BFT consensus whose propose → prevote → precommit sequence is structurally almost identical to PBFT’s pre-prepare → prepare → commit (buchman2018tendermint in the references). The differences: the proposer rotates each round, weighted by stake, rather than being drawn from a fixed known set, and the quorum threshold is “over 2/3 of stake” rather than “2f+1 nodes.” PoS here is purely an input, who proposes and how much one vote weighs, while the actual agreement logic is nearly a direct descendant of PBFT, inheriting its O(n²) communication weakness too. The Cosmos ecosystem keeps this practical by capping validator counts at roughly 100–150.

Diem (Libra) / Aptos: running HotStuff itself atop a PoS validator set

The consensus layers of LibraBFT (now Diem) and Aptos are nearly direct implementations of the HotStuff paper (yin2018hotstuff in the references). PoS stake determines both the membership and the voting weight of the validator set, and HotStuff’s leader aggregation, QCs, and three-chain rule run inside it. Where PBFT-family Tendermint struggles to scale past O(n²) communication, the HotStuff family’s O(n) communication holds up throughput even with larger validator sets. Aptos builds on this with further-optimized derivatives such as DiemBFTv4 (Jolteon).

Ethereum: a two-layer hybrid of PBFT-style finality and Nakamoto-style fork choice

Ethereum is neither a pure “Tendermint-style” nor “HotStuff-style” chain; it is a two-layer hybrid. Proposing the latest block and picking the head of the chain is handled by LMD-GHOST, a Nakamoto-style fork-choice rule (follow the heaviest branch); on its own, this leaves only probabilistic finality. Layered on top is Casper FFG (the Friendly Finality Gadget): at each epoch-boundary checkpoint, once over 2/3 of validator stake approves across two voting rounds (justify → finalize), that checkpoint becomes irreversibly final. This two-round, 2/3-supermajority structure is the same idea as PBFT’s prepare/commit, and the original paper (buterin2017casper in the references) explicitly draws on the Byzantine-tolerant consensus lineage.

PoS decides who votes (Sybil resistance, voting weight); PBFT/HotStuff decide how those votes become agreement (safety, finality). Most major chains today are built as a combination of these two layers. The “Proof family” and “Byzantine-tolerant family” look like separate groups in the earlier table because that axis classifies by fault model and participation model; in implementation, the two layers stack and coexist.

Comparing the six schemes

The schemes differ fundamentally in who may participate, which failures they assume, and what backs their security. Choosing by use case is what matters.

Related academic literature is collected on the References page.