Distributed Systems Consensus: Raft, Paxos & CAP Explained

The hardest problems in distributed systems are not about speed or scale. They are about agreement. How do you get a cluster of independent machines — each one capable of crashing, losing connectivity, or receiving messages in the wrong order — to consistently agree on a single value? This is the consensus problem, and it sits at the heart of every reliable distributed system in production today. From the etcd clusters that back Kubernetes to the coordination services inside Google's Spanner database, consensus algorithms are the invisible glue that makes distributed systems behave like coherent, trustworthy units rather than chaotic collections of independent processes.

What Is Consensus and Why Is It Hard?

In a single-node system, consistency is trivial. One machine holds the authoritative state; reads and writes serialize naturally. In a distributed system, you have multiple nodes, each with their own copy of state. The moment you allow multiple writers — or even multiple readers that must see consistent data — you need a protocol to ensure they all agree.

Consensus, formally defined, requires that all non-faulty nodes in a system eventually agree on the same value, that the agreed value was proposed by some node (not invented), and that the agreement is final. These properties sound simple, but a 1985 result known as the FLP impossibility theorem — proved by Fischer, Lynch, and Paterson — demonstrated that no deterministic algorithm can guarantee consensus in an asynchronous distributed system if even one process might fail. Real-world consensus algorithms navigate this impossibility by making pragmatic assumptions about timing and failure modes, which is why they work in practice even though the theoretical impossibility stands.

The CAP Theorem: Choosing Two of Three

Before diving into specific algorithms, it helps to understand the constraints they operate under. Eric Brewer's CAP theorem — first stated as a conjecture in his 2000 PODC keynote and formally proved by Gilbert and Lynch in 2002 — asserts that a distributed data store can provide at most two of three guarantees simultaneously:

• Consistency (C): Every read receives the most recent write or an error. All nodes see the same data at the same time.
• Availability (A): Every request receives a response (not necessarily the latest data), with no guarantee of how recent it is.
• Partition Tolerance (P): The system continues operating even when network partitions prevent some nodes from communicating with others.

Because network partitions are a physical reality in any distributed system — cables fail, switches misbehave, data centers lose connectivity — partition tolerance is non-negotiable. Engineers therefore choose between CP systems (consistent but potentially unavailable during a partition) and AP systems (always available but potentially returning stale data during a partition). Consensus algorithms are fundamentally CP: they prioritize consistency and will sacrifice availability rather than allow divergent state.

Image: File:IBMPortableModularDataCenter3.jpg — Raysonho @ Open Grid Scheduler (CC BY 3.0), via Wikimedia Commons

Paxos: The Original Blueprint

Leslie Lamport introduced the Paxos algorithm in a 1989 paper (published as a DEC SRC Technical Report and later in ACM TOCS in 1998, with a simplified version in his widely-read 2001 paper "Paxos Made Simple"). Paxos solves the single-value consensus problem through two phases involving three roles: proposers, acceptors, and learners.

In the Prepare phase, a proposer selects a proposal number n and sends a Prepare(n) message to a quorum of acceptors. Each acceptor that receives this message promises not to accept proposals with a lower number and reports the highest-numbered proposal it has already accepted.

In the Accept phase, if the proposer receives promises from a majority quorum, it sends Accept(n, v) — where v is either its own proposed value or the highest-numbered value reported by any acceptor. Once a majority of acceptors accept this value, consensus is reached and learners are notified.

Paxos is mathematically elegant and has been proven correct. Its practical problem is implementation complexity. The original paper describes single-decree consensus (agreement on one value). Building Multi-Paxos — the version required for a replicated log — requires substantial additional machinery for leader election, log compaction, membership changes, and reconfiguration. Many engineers who have implemented Paxos-based systems describe the experience as significantly more difficult than the published algorithms suggest. Google's Chubby lock service and Apache Zookeeper are prominent production implementations that took years of engineering to get right.

Raft: Designed for Understandability

Diego Ongaro and John Ousterhout introduced Raft in their 2014 USENIX ATC paper "In Search of an Understandable Consensus Algorithm" with an explicit goal: produce a consensus algorithm that engineers could actually understand, implement correctly, and reason about when things go wrong. They succeeded. Raft is now the consensus algorithm of choice for most new distributed systems infrastructure, including etcd (which backs Kubernetes), CockroachDB, TiKV (which backs TiDB), and many others.

Raft decomposes the consensus problem into three relatively independent sub-problems:

• Leader election: At any given time, one server is the leader. All log entries flow through the leader. If the leader fails, a new election produces a replacement. Raft uses randomized election timeouts to avoid split votes — each server waits a random interval before starting an election, which means one server almost always starts first and wins.
• Log replication: The leader accepts client requests, appends them to its log, and replicates the log to followers. Once a majority of servers have written an entry to their local log, the entry is committed and the leader notifies followers. Followers apply committed entries to their state machines in order.
• Safety: Raft guarantees that if any server has applied a log entry at a given index, no other server will ever apply a different entry at that same index. This property holds even across leader changes.

The leader election mechanism is particularly clean. Servers start as followers. If a follower receives no communication from a leader within its election timeout, it transitions to candidate, votes for itself, and requests votes from other servers. A candidate that receives votes from a majority of the cluster becomes the new leader. The term number — a monotonically increasing integer — prevents stale leaders from causing harm: any server that receives a message with a higher term immediately updates its own term and steps back to follower status.

Byzantine Fault Tolerance: When Nodes Can Lie

Both Paxos and Raft assume crash-stop failures — nodes that fail do so by stopping, not by sending incorrect or malicious messages. This assumption holds in most internal datacenter environments where you control every machine. But there is a class of failure — Byzantine faults — where a node can behave arbitrarily: sending inconsistent messages to different peers, responding with fabricated data, or actively trying to subvert the protocol.

Byzantine Fault Tolerant (BFT) algorithms handle this harder failure model. They require at least 3f + 1 nodes to tolerate f Byzantine failures, and they add communication rounds so that nodes can cross-verify messages before accepting them. Practical Byzantine Fault Tolerance (PBFT), introduced by Castro and Liskov in 1999, demonstrated that BFT was implementable at practical latencies in LAN environments.

BFT has become significantly more relevant with the rise of permissioned blockchain systems (Hyperledger Fabric uses a BFT-inspired ordering service) and financial infrastructure where regulatory requirements demand protection against malicious node behavior. The tradeoff is cost: BFT systems require more nodes and more network traffic than crash-fault-tolerant alternatives.

Image: File:Distribfaultredudance.PNG — Logical Premise (Public domain), via Wikimedia Commons

Choosing the Right Consensus Approach for Your System

The choice of consensus algorithm — or whether to use one at all — depends on your failure model, consistency requirements, and operational constraints.

For the vast majority of distributed systems built inside trusted datacenters, Raft is the right default choice. It is well-understood, has multiple high-quality open-source implementations (etcd's raft library, HashiCorp Raft), and its documentation and behavior are sufficiently clear that engineering teams can reason about failure scenarios without deep distributed systems expertise.

If you are building on top of existing infrastructure, consider using a proven coordination service — etcd or ZooKeeper — rather than implementing consensus from scratch. These services have absorbed years of production battle-testing and provide clean APIs for distributed locks, leader election, and configuration management.

Reserve BFT approaches for systems where node compromise is a realistic concern: inter-organizational systems without a trusted central authority, public or permissioned blockchain infrastructure, or critical financial systems subject to strict adversarial threat models.

One practical caveat applies to all consensus approaches: they fundamentally trade availability for consistency during network partitions. A Raft cluster of five nodes can survive two simultaneous node failures; if three nodes become unreachable at once, the cluster stops accepting writes rather than risk split-brain. This is the right behavior, but system operators must plan for it explicitly — with proper monitoring, runbooks, and circuit breakers at the application layer.

Frequently Asked Questions

What is the difference between consensus and replication?

Replication copies data to multiple nodes for durability and read scalability. Consensus is the mechanism that ensures replicas stay consistent — that they apply the same sequence of operations in the same order. You can have replication without strong consensus (asynchronous replication, eventual consistency), but you cannot have strong consistency across replicas without some form of consensus protocol coordinating writes.

Why does Raft require a leader, and what happens when the leader fails?

Raft's strong-leader model centralizes all decisions through one node, which dramatically simplifies reasoning about consistency — there is only one place writes happen. When a leader fails, followers notice the absence of heartbeat messages and start a new election after their randomized timeout expires. In a five-node cluster, a new leader is typically elected within one to two election timeout periods, often 150 to 300 milliseconds in practice. During this window the cluster cannot commit new entries, but it preserves all previously committed data.

Is consensus necessary for every distributed system?

No. Many distributed systems tolerate eventual consistency — different nodes may return different values for a period, but they eventually converge. DNS, shopping cart data, social media feeds, and read-heavy caches frequently use eventually consistent models. Consensus is essential when you need linearizability: the guarantee that operations appear to execute instantaneously and in order, even across multiple nodes. Metadata stores, configuration services, distributed locks, and financial ledgers typically require this guarantee.

Bottom Line

Distributed systems consensus is one of the fundamental problems in computer science — provably impossible in its strongest form, yet practically solvable with careful engineering tradeoffs. Raft has become the consensus algorithm of choice for most new distributed infrastructure because it makes the tradeoffs explicit and the implementation tractable. Understanding the CAP theorem, the difference between crash-fault and Byzantine-fault tolerant approaches, and the operational implications of a leaderless cluster during a partition are the conceptual anchors every distributed systems engineer should have before designing coordination-dependent services. Build on proven implementations where you can, understand the failure model of whatever you choose, and plan explicitly for the windows when consensus is unavailable.

Disclaimer: This article is for informational purposes only. Technology landscapes change rapidly; verify information with official sources before making technical decisions.