Consensus Algorithms: Paxos, Raft, and Beyond

Hello! Welcome to the fifth lesson in our course on Distributed Systems Architecture.

In our last lesson, we analyzed the CAP and PACELC theorems, establishing that distributed systems facing a network partition must choose between consistency (CP) and availability (AP). We concluded that for many critical systems, like the financial ledgers you've worked on, sacrificing consistency is not an option.

This raises a crucial question: how do distributed nodes achieve consistency? How do they agree on a single, shared truth—like the state of an order book or a user's balance—when they can't trust the network and can fail independently?

Today, we will answer that question by exploring consensus algorithms. These algorithms are the engines that power fault-tolerant, strongly consistent (CP) systems.

Learning Outcome:

Compare the roles and high-level mechanisms of consensus algorithms (e.g., Paxos, Raft) in providing fault-tolerance and strong consistency.

We will dissect two of the most influential consensus algorithms, Paxos and Raft, to understand their roles, their core mechanics, and the trade-offs between them.

1. The Consensus Problem

At its heart, consensus is about getting a group of computers to agree on something. This is fundamental to building reliable systems from unreliable parts. If you have multiple replicas of a database, you need a way to ensure they all apply the same transactions in the same order. This is known as state machine replication. Consensus algorithms provide the mechanism to make the replicated log of operations identical across all machines.

Let's start with a short video that introduces the consensus problem in the context of building a fault-tolerant service.

As the video explains, without a consensus algorithm, replicas of your service could diverge, leading to inconsistent state. For a financial platform, this could mean one server thinks a trade was executed while another doesn't—a catastrophic failure. Consensus algorithms prevent this by providing a provably correct way for nodes to agree on an ordered sequence of operations.

2. Raft: Consensus Through Leadership

While many consensus algorithms exist, we'll start with Raft. It was developed in 2014 with the explicit goal of being more understandable than its famous predecessor, Paxos, without sacrificing performance. Its design centers on a strong leader who coordinates all activity.

Raft decomposes the consensus problem into two main parts:

1. Leader Election: One server is elected as the Leader. This leader is solely responsible for managing the replicated log.
2. Log Replication: The leader accepts commands from clients, appends them to its own log, and replicates them to the other servers (the Followers). An entry is considered committed (and can be applied to the state machine) only after it has been replicated on a majority of servers.

The following video provides a comprehensive and clear walkthrough of Raft's mechanisms.

Raft's key safety property is that a newly elected leader is guaranteed to have all the committed entries from previous terms. It achieves this by a simple rule during elections: followers will only vote for a candidate whose log is at least as up-to-date as their own. This ensures that no committed data is ever lost or overwritten.

3. Paxos: The Original Consensus Algorithm

Now let's turn to Paxos. Published by Leslie Lamport in 1989, Paxos was the first provably correct consensus algorithm for asynchronous environments (where there are no bounds on message delay). It is famously difficult to understand, but its core ideas are foundational to the field.

Unlike Raft's strong leader model, Paxos operates on a more democratic, two-phase protocol. The nodes in Paxos have three roles:

• Proposer: A node that suggests a value.
• Acceptor: A node that votes on proposed values.
• Learner: A node that learns the final, agreed-upon value.

In practice, a single server typically performs all three roles. The core of Paxos is a two-phase process for agreeing on a single value:

1. Phase 1 (Prepare/Promise): A Proposer sends a prepare message with a unique proposal number. Acceptors respond with a promise not to accept any older proposals and, crucially, they also include any value they may have already accepted from a previous proposal.
2. Phase 2 (Accept/Accepted): If the Proposer receives promises from a majority of Acceptors, it sends an accept request. If it received any previously accepted values in the promise phase, it must propose the value associated with the highest proposal number it saw. Otherwise, it can propose its own value. An Acceptor accepts the request if it hasn't already promised to ignore it.

Consensus is achieved when a majority of Acceptors have accepted the same value.

The following video from a Google TechTalk provides a detailed walkthrough of the classic Paxos algorithm.

The process described is for agreeing on a single value. To build a replicated log (state machine replication), an algorithm called Multi-Paxos runs a separate instance of Paxos for each log entry. To optimize this, Multi-Paxos elects a "distinguished proposer" (a leader) that can skip the prepare phase for subsequent proposals as long as it remains the leader, making it perform similarly to Raft in the steady state.

4. Comparison: Paxos vs. Raft

Now that we have a high-level understanding of both algorithms, we can compare them directly. While they both solve the same problem and provide the same safety guarantees (strong consistency), their approaches and design philosophies differ significantly.

The primary difference lies in understandability and leader election.

• Raft was designed for understandability. It has a stronger, more explicit leader concept. The leader is the sole source of truth, and the election process ensures the leader is always the most up-to-date node.
• Paxos is more of a decentralized, democratic protocol. Its "leader" (the distinguished proposer in Multi-Paxos) is weaker and can be challenged by other proposers, leading to potential contention. The original algorithm is underspecified, leading to a "family" of Paxos variants that can be difficult to compare.

Let's look at a concise visual comparison.

To dig deeper, the following academic paper provides a fantastic, direct comparison by describing a simplified Paxos algorithm using Raft's terminology.

As the paper highlights, the core differences are:

1. Leader Election: Raft uses randomized timeouts and a voting process where followers vet the candidate's log. Paxos allows any node to attempt to become a leader, with higher proposal numbers winning out.
2. Log Up-to-dateness: Raft ensures the leader has an up-to-date log before being elected. In Paxos, a new leader is elected first and then discovers the correct state of the log by communicating with a majority.
3. Log Entries: Raft preserves the original term number of a log entry. Paxos leaders may re-number uncommitted entries from previous leaders with the current term.

Here's another visual mapping the concepts between the two algorithms:

Finally, let's read a more accessible summary of the comparison points.

Conclusion

In this lesson, we've explored the core problem of distributed consensus and compared the two most prominent algorithms for solving it: Paxos and Raft.

Key Takeaways:

• Role of Consensus: Consensus algorithms are essential for fault tolerance and strong consistency in distributed systems. They are the mechanism used to implement state machine replication, ensuring all nodes agree on an ordered log of operations.
• Raft's Mechanism: Raft uses a strong, explicit leader elected via a voting process. The leader manages a replicated log, and commands are committed once replicated on a majority of nodes. Its design prioritizes understandability.
• Paxos's Mechanism: Classic Paxos uses a more decentralized two-phase (Prepare/Accept) protocol to agree on a single value. Multi-Paxos extends this to a log by electing a "distinguished proposer," but its leadership is weaker and more susceptible to contention than Raft's.
• Key Differences: The main distinctions lie in their approach to leader election and understandability. Raft's election process is more restrictive, ensuring the leader is up-to-date from the start. Paxos is often considered a family of algorithms and is notoriously harder to implement correctly, whereas Raft provides a more complete and practical specification.

Preview of the Next Lesson:
We've just seen how consensus algorithms help systems tolerate failures. But what kinds of failures are there? In our next and final lesson for this module, we will formally define different failure models, including network partitions, node failures, and Byzantine failures, and provide concrete examples of how each could manifest in a high-stakes financial system.