Consensus Algorithms

Why consensus exists

Imagine 5 friends trying to choose a restaurant over a glitchy group chat: some messages arrive late, one phone dies, and two people reply at the same time. A distributed system has the same problem. Multiple machines must agree on one value—like who is leader, which command is next, or whether a transaction committed—even when some machines crash or networks delay messages.

This is the job of a consensus algorithm. It aims to guarantee:

• Agreement: honest nodes don't decide different values
• Validity: the chosen value was actually proposed
• Fault tolerance: the system still works if some nodes fail

A common rule is majority quorum. With 5 servers, a majority is 3. If one value is accepted by 3 servers, no different value can also get a majority, because any two majorities must overlap in at least one server.

Paxos: agree without trusting timing

Paxos is the classic consensus algorithm. It is famous for being correct, powerful, and hard to read. Its core idea: before choosing a value, nodes use proposal numbers so newer attempts don't accidentally overwrite older safe decisions.

Think of Paxos as a formal auction:

• A proposer suggests a numbered proposal, like #12
• Acceptors promise not to accept lower-numbered proposals after seeing #12
• If a majority promises, the proposer sends an accept request
• If a majority accepts, the value is chosen

If an acceptor already accepted an older value, the proposer may be forced to carry that value forward. That's the safety trick: even if leaders change, a chosen value cannot be replaced.

Paxos is often used as a foundation for replicated state machines, though production teams often prefer friendlier variants.

Raft: consensus designed for humans

Raft solves the same problem as Paxos but organizes it around a strong leader, making it easier to understand and implement. Time is divided into terms. In each term:

• servers may become candidates and request votes
• one wins a majority and becomes leader
• the leader appends client commands to its log and replicates them
• an entry is committed once stored on a majority

Raft separates the problem into leader election, log replication, and safety rules. Here's the basic flow:

Client -> Leader: "set x = 7"
Leader -> Followers: AppendEntries(term=4, index=9, command="set x = 7")
Followers -> Leader: ack
Leader: once majority ack, mark index 9 committed
Leader -> Followers: commit index 9

This makes Raft popular in systems like etcd and Consul, where operators need reliability and clarity.

Paxos vs. Raft: what to remember

Both algorithms solve the same core challenge: getting distributed machines to act like one reliable system. Both rely on majorities, so with N servers, you typically tolerate up to floor((N-1)/2) failures. Example: with 5 servers, you can lose 2; with 3, you can lose 1.

The practical difference is often about structure:

• Paxos: minimal, elegant, but conceptually dense
• Raft: more explicit roles and steps, easier to teach and debug

Neither magically defeats network partitions. If a cluster splits 2-3, only the side with 3 can continue making decisions safely.

Consensus is not about making everyone fast. It's about making disagreement impossible in the presence of failure.

If you remember one thing, remember this: distributed systems stay trustworthy because they choose safety first, then recover liveness when the network cooperates.