Paxos Algorithm

What is Paxos?

Imagine you and your friends are trying to decide where to eat dinner. You're all texting each other, but some messages are delayed, some friends drop offline because of bad reception, and two different friends are simultaneously suggesting different restaurants. How do you all eventually agree on one single restaurant without anyone getting confused?

This is exactly the problem Paxos solves in distributed systems. It's a consensus algorithm that helps a network of computers agree on a single value, even if some computers fail, messages get lost, or the network is unreliable.

The Core Concept

In distributed systems, you often have multiple nodes (servers) that need to keep their data in sync. If a user updates their password, every database node needs to agree on that new password. But what if two different users try to book the exact same seat on an airplane at the exact same millisecond, and their requests hit different servers?

Paxos ensures that only one decision is made, and once a decision is made, it can never be changed.

The Roles in Paxos

Think of a parliament where a law needs to be passed:

1. Proposers: These are the servers suggesting a value (e.g., "Let's book seat 12A for Alice").
2. Acceptors: The voters. They listen to proposals and vote on whether to accept them.
3. Learners: The nodes that just need to know what the final decision was once it's made.

In most real-world systems, a single server plays all three roles simultaneously.

How Paxos Works: The Two Phases

Paxos operates in two main phases. Let's stick with our dinner analogy.

Phase 1: The Prepare Phase (Getting Attention)

A Proposer wants to suggest a value. It creates a proposal with a unique, monotonically increasing ID (let's say, ID 10) and sends a "Prepare" message to a majority of Acceptors.

• Analogy: You shout, "Hey everyone, listen to me! I'm proposal #10!"
• If the Acceptors haven't promised to listen to a higher proposal number (like #11), they reply: "Okay, I'll listen to you, and I promise I won't accept any proposals with an ID less than 10."

Phase 2: The Accept Phase (Making the Proposal)

Once the Proposer gets a "Yes" from a majority of Acceptors, it sends an "Accept" message with the actual value (e.g., "Let's eat at Pizza Hut").

• Analogy: You say, "Great, since you're listening, let's go to Pizza Hut!"
• If the Acceptors haven't made promises to a newer, higher ID in the meantime, they accept the value.

Once a majority accepts the value, consensus is reached. The Learners are then informed of the decision.

Why is Paxos so Hard?

You might be thinking, "That doesn't sound too bad!" But here's the thing: Paxos is notoriously difficult to understand and even harder to implement correctly.

What happens if a Proposer crashes halfway through Phase 1? What if two Proposers keep outbidding each other with higher IDs in an endless loop (known as "dueling proposers" or "livelock")? Implementing the logic to handle every single edge case of network failure is a massive engineering feat.

Real-World Examples

Because of its complexity, engineers don't usually write Paxos from scratch. Instead, they rely on battle-tested systems that use it under the hood:

• Google Spanner: Google's globally distributed database uses Paxos to replicate data across data centers synchronously. When you write data to Spanner, it uses Paxos to ensure a majority of replicas agree on the transaction.
• Apache Cassandra: Cassandra uses a variant of Paxos for its Lightweight Transactions (LWTs). When you do an "Insert if not exists" query, Cassandra uses Paxos to ensure no two users can insert the same unique record at the same time.
• Chubby: Google's distributed lock service (which inspired ZooKeeper) uses Paxos at its core to maintain a consistent state across its replicas.

Summary

• Paxos is a foundational consensus algorithm that allows distributed nodes to agree on a single value in an unreliable network.
• It uses Proposers, Acceptors, and Learners through a two-phase commit-like process (Prepare and Accept).
• It requires a majority quorum to make a decision, ensuring consistency even if some nodes fail.
• While mathematically proven to work, its complexity led to the creation of more understandable alternatives like Raft. However, it remains heavily used in massive-scale systems like Google Spanner.