Paxos Algorithm

By the Apiary Team

Introduction

In a world where data lives in thousands of machines, in clouds that span continents, the tiniest mis‑step can cause a cascade of inconsistencies. Imagine a bank that records a transaction on one server but, because another replica disagrees, the same account shows two different balances. Or picture a swarm of autonomous drones that need to agree on a shared flight plan—if they diverge, the result could be a mid‑air collision. The invisible glue that keeps distributed systems coherent is a consensus algorithm, and among the many designs that have emerged, Paxos stands out as the most studied, most implemented, and, paradoxically, the most misunderstood.

The name “Paxos” might evoke the ancient Greek island where philosophers debated the nature of truth. In computer science, Paxos is the formalization of a set of rules that lets a collection of unreliable machines agree on a single value, even when some of them crash, lose messages, or temporarily fall out of sync. It was first described by Leslie Lamport in 1998, and since then it has become the backbone of services that power everything from search engines to financial exchanges.

Why does this matter to Apiary, a platform devoted to bee conservation and self‑governing AI agents? Bees, like distributed systems, must reach consensus on where to forage, how to allocate hive resources, and when to swarm. The same mathematical guarantees that keep a database consistent can inspire algorithms for managing autonomous AI colonies that monitor hive health, predict pesticide exposure, and coordinate rescue missions. By demystifying Paxos, we equip engineers, ecologists, and AI designers with a shared language for solving the toughest coordination problems—whether the participants are servers in a data center or workers in a honey‑comb.

This article dives deep into the mechanics of Paxos: its roles, its two‑phase protocol, its failure‑handling strategies, and its real‑world deployments in modern databases. We will also draw honest analogies to bee societies and AI agents, showing how the principles of quorum, leader election, and state replication resonate far beyond the realm of code.

1. The Problem of Distributed Consensus

When a system is distributed, no single node has a global view of the entire state. Each node only knows its own local data and the messages it receives. To maintain a coherent view, the nodes must agree on a sequence of operations—commonly called a log—that all will apply in the same order. This is the essence of the consensus problem.

1.1 Formal Definition

In the classic formulation, a consensus protocol must satisfy three properties for a set of processes P:

A protocol that meets these constraints under asynchronous network conditions (where messages can be delayed arbitrarily) and crash failures (where nodes can stop working but do not act maliciously) is said to achieve fault‑tolerant consensus.

1.2 Why Naïve Approaches Fail

Consider a simple “majority vote” where each node broadcasts its proposal and the value with the most votes wins. This works only if all nodes are alive and messages arrive instantly. In a real network:

• Message delays can cause a node to see a different majority than another node.
• Node crashes may reduce the number of participants below the majority threshold, causing the system to stall.
• Network partitions can create two disjoint majorities that each think they have won, violating safety.

The impossibility result proven by Fischer, Lynch, and Paterson (the FLP theorem, 1985) shows that in a purely asynchronous system with even a single crash failure, no deterministic algorithm can guarantee both safety and liveness. Paxos sidesteps this impossibility by making a minimal synchrony assumption: it proceeds as long as a quorum of nodes can communicate reliably, while still guaranteeing safety under any circumstances.

2. The Core Idea Behind Paxos

At its heart, Paxos is a state machine replication technique. It treats the distributed system as a collection of replicas that each run the same deterministic program. The algorithm ensures that every replica receives the same sequence of commands, so their state evolves identically.

The key insight is to decouple the process of proposing a value from the process of learning that value. Paxos introduces three logical roles:

1. Proposers – generate proposals for the next command.
2. Acceptors – act as the voting body; they decide whether to accept a proposal.
3. Learners – observe the outcome and apply the decided command to their local state machine.

A single physical node can play any combination of these roles; in many implementations a node is both a proposer and an acceptor, and all nodes are learners.

The algorithm proceeds in rounds (also called ballots). Each round is identified by a monotonically increasing number, often called a proposal number. The numbers are chosen so that no two proposals ever share the same identifier, guaranteeing a total order among competing proposals.

3. The Three Roles in Detail

3.1 Proposers

A proposer’s responsibility is to initiate a consensus instance. It selects a value (e.g., a transaction log entry) and a proposal number n. The number is typically constructed as:

n = (epoch * 2^32) + node_id

where epoch increments each time the proposer retries after a failure, and node_id uniquely identifies the node. This construction guarantees that:

• n is globally unique.
• Later attempts always have a larger n than earlier attempts, preventing older proposals from overriding newer ones.

Proposers can be clients that want to write data, or leaders that periodically drive the consensus for a stream of commands (as in Multi‑Paxos).

3.2 Acceptors

Acceptors are the sole source of truth for a consensus instance. They store two pieces of information per instance:

When an acceptor receives a Prepare request with proposal number n, it does the following:

1. If n > promised_n, it updates promised_n = n and replies with a Promise that includes any previously accepted (accepted_n, accepted_value).
2. If n ≤ promised_n, it rejects the request (a Nack) because it has already promised to a higher-numbered proposal.

Later, when the proposer sends an Accept request with the same n and a value v, the acceptor will:

1. Accept the value only if n ≥ promised_n. It then records accepted_n = n and accepted_value = v.
2. Otherwise, it rejects (again a Nack).

The acceptor’s promise is the core safety mechanism: once it has promised to a higher-numbered proposal, it will never accept a lower one, preventing conflicting decisions.

3.3 Learners

Learners do not participate in the voting; they simply observe the outcome. An acceptor sends a Learn message to all learners (including itself) whenever it accepts a value. Once a learner receives the same (n, v) from a quorum of acceptors, it can safely apply v to its local state machine.

In many deployments, every node is a learner, so the system automatically replicates the decided command to all replicas.

4. The Two‑Phase Protocol (Prepare & Accept)

Paxos proceeds in two logical phases per consensus instance. The phases are atomic from the perspective of the proposer: it must complete Phase 1 before moving to Phase 2.

4.1 Phase 1 – Prepare

1. Proposer → Acceptors: Send Prepare(n).
2. Acceptors → Proposer: Reply with Promise(n, accepted_n, accepted_value) if n is greater than any previous promise; otherwise, reply with Nack.
3. Quorum Requirement: The proposer must collect promises from a majority (⌈|A|/2⌉+1) of the acceptors. This majority is called a quorum.

If any acceptor has already accepted a value, it includes that value in its promise. The proposer records the highest accepted_n it learns and adopts the corresponding accepted_value. This ensures that a later proposal never overwrites a previously decided value.

4.2 Phase 2 – Accept

1. Proposer → Acceptors: Send Accept(n, v) where v is either the value originally proposed (if no acceptor reported a prior acceptance) or the highest previously accepted value.
2. Acceptors → Learners: If n ≥ promised_n, the acceptor records accepted_n = n and accepted_value = v, then sends a Learn(v) to all learners.
3. Quorum Requirement: Once a learner observes the same (n, v) from a quorum of acceptors, it can consider the value chosen and apply it.

If any acceptor rejects the Accept (because it had promised a higher n), the proposer must start a new round with a larger proposal number, repeating Phase 1. In practice, this “retry” is rare when a single leader drives the protocol, because the leader holds the highest proposal number.

4.3 Example Walkthrough

Suppose we have five acceptors A1‑A5 and a proposer P wants to commit the transaction T = "deposit $10".

If, in step 2, A4 had previously accepted "deposit $5" with accepted_n = 0, its promise would have been Promise(1, 0, "deposit $5"). The proposer would then adopt "deposit $5" as the value for this round, preserving safety.

5. Handling Failure Scenarios

Paxos is designed to survive a wide range of faults. Below we examine the most common failure modes and how the algorithm reacts.

5.1 Crash Failures

A crash failure is when a node simply stops responding (e.g., due to a power loss). Since Paxos only requires a quorum of acceptors, the system can continue as long as a majority remains alive. For a cluster of 2f+1 acceptors, Paxos tolerates up to f crashes.

Example: In a 5‑node cluster (f = 2), the system can lose any two acceptors and still reach consensus. The remaining three form a quorum.

When a crashed node recovers, it may have stale promised_n and accepted_n values. Upon rejoining, it typically re‑synchronizes by fetching the latest log from a learner or by participating in a new Prepare round, where the higher proposal numbers overwrite any old promises.

5.2 Network Partitions

A partition splits the network into two or more groups that cannot communicate. Suppose a 5‑node cluster splits into a 3‑node group (A1‑A3) and a 2‑node group (A4‑A5). The 3‑node group can still form a quorum, so consensus proceeds there. The minority side cannot form a quorum and will block, but it will not violate safety because it cannot accept any new proposals without a quorum.

When the partition heals, the minority side learns the values chosen by the majority via the Learn messages. Any divergent proposals that were made in the minority group are discarded because they never reached a quorum.

5.3 Message Loss and Reordering

Paxos tolerates arbitrary message delays, loss, and reordering. The protocol’s safety does not depend on messages arriving in any particular order. If a proposer receives a Nack because an acceptor had promised a higher number, the proposer simply generates a larger number and retries. This “back‑off” can be exponential to avoid overwhelming the network.

5.4 Leader Failure in Multi‑Paxos

In Multi‑Paxos, a single proposer acts as a leader for many consecutive instances, avoiding the cost of Phase 1 for each instance. If the leader crashes, the system must elect a new leader. The election works by having a new proposer start a fresh Prepare round with a higher proposal number. Because the new proposal number must exceed any previous number, the new leader will gain a quorum of promises, possibly learning the last accepted value from each acceptor. The new leader then resumes appending commands.

The worst‑case latency for leader election is bounded by the message round‑trip time (RTT) plus the time to collect a quorum. In practice, with a typical data center RTT of ~0.5 ms, leader changes take on the order of a few milliseconds.

5.5 Byzantine Failures (What Paxos Does Not Cover)

Paxos assumes non‑malicious failures: nodes may crash or become temporarily unreachable, but they never send contradictory or deliberately false messages. In environments where nodes might be compromised (e.g., a hostile cloud tenant), a Byzantine Fault Tolerant (BFT) algorithm such as PBFT or Tendermint is required. Paxos is not designed for Byzantine scenarios, and attempting to use it under such conditions can lead to safety violations.

6. Optimizations and Variants

Since its original description, Paxos has spawned a family of optimizations that improve throughput, latency, or deployment simplicity. The most widely used in production are Multi‑Paxos, Fast Paxos, and Cheap Paxos.

6.1 Multi‑Paxos

Multi‑Paxos extends the single‑instance protocol to a sequence of instances (a log). The key observation is that once a leader is chosen, the Prepare phase can be performed once for the whole series, after which the leader can send Accept messages for each new command without repeating Phase 1. This reduces the per‑command message cost from 2 × quorum to 1 × quorum.

Google’s Spanner database uses a variant of Multi‑Paxos combined with TrueTime (a globally synchronized clock) to achieve external consistency across data centers. Spanner’s implementation can commit a transaction in ~6 ms for reads and ~30 ms for writes, even when replicas are spread across continents.

6.2 Fast Paxos

Fast Paxos (1999) eliminates the leader for the first round of a command by allowing proposers to send Accept messages directly to acceptors, bypassing the Prepare phase. This reduces latency to a single round‑trip, at the cost of requiring a larger quorum: ⌈(N + f)/2⌉ acceptors instead of a simple majority. In practice, Fast Paxos is useful when the system experiences low contention and can afford the extra quorum size.

6.3 Cheap Paxos

Cheap Paxos (2006) introduces cheap acceptors that can be replaced quickly if they fail. The idea is to have a small set of core acceptors (e.g., three) and a larger pool of auxiliary acceptors that can step in. The protocol guarantees progress as long as at least f + 1 core acceptors survive, which reduces the cost of maintaining a fully replicated set of high‑performance nodes.

6.4 Paxos‑based Log Replication Libraries

Several open‑source libraries implement Paxos or its variants:

These libraries hide the intricacies of proposal numbers and quorum management behind clean APIs, allowing developers to focus on application logic.

7. Paxos in Modern Databases

7.1 Google Spanner

Spanner’s architecture combines TrueTime, a globally synchronized clock with bounded uncertainty, with Multi‑Paxos for replication. Each data partition (called a tablet) is replicated across three (or more) data centers. The leader for a tablet runs a Paxos instance, and writes are committed only after a majority of replicas acknowledge the transaction. Spanner guarantees external consistency: if transaction A commits before transaction B starts, then all replicas see A before B.

Key numbers:

• Replication factor: 3 (with optional 5 for higher durability).
• Write latency: 30 ms median across continents.
• Availability: > 99.999% (five‑nines) SLA across regions.

7.2 Apache Cassandra (Lightweight Transactions)

Cassandra implements Paxos for its lightweight transactions (LWT). When a client issues a conditional INSERT IF NOT EXISTS, Cassandra runs a Paxos round across the nodes responsible for the partition key. The process involves:

1. Prepare: Each replica records a proposal number and returns any existing value.
2. Accept: The coordinator proposes the new row if no conflicting value exists.
3. Commit: Once a quorum (usually RF/2 + 1 where RF is replication factor) acknowledges, the write is considered successful.

Cassandra’s LWT latency is typically 5–10 ms for a three‑node quorum, making Paxos viable for occasional strong consistency without sacrificing the eventual‑consistency model for the bulk of operations.

7.3 etcd and Kubernetes

etcd uses the Raft algorithm, which is a simplified version of Multi‑Paxos with a stronger emphasis on understandability. Nevertheless, the underlying guarantees are identical: a majority of nodes must agree on each entry. etcd stores the cluster state for Kubernetes, including the desired configuration of pods, services, and secrets. Any disruption to the etcd quorum can halt the entire Kubernetes control plane; therefore, production clusters typically run an odd number of etcd members (3, 5, or 7) across separate failure domains.

7.4 Financial Trading Platforms

High‑frequency trading firms rely on Paxos for order‑book replication. A typical deployment uses a 5‑node quorum across two data centers, achieving sub‑millisecond latency for order matching. The guarantee that every replica sees the same sequence of orders eliminates the risk of double‑spending or order mismatches that could cost millions of dollars.

8. Lessons for Bee Colonies and AI Agents

8.1 Quorum as a Decision Mechanism

In a bee colony, the queen does not unilaterally decide when to swarm; instead, workers perform a consensus through waggle‑dance communication. A sufficient number of foragers must agree on a new nest site before the colony commits to moving. This mirrors Paxos’ quorum: a majority of workers (acceptors) must “promise” to a proposed site (value) before the swarm (learn) proceeds.

Researchers have modeled this process using threshold voting where each bee’s probability of supporting a site increases with the number of dances it observes. The critical threshold is often around 30‑40 % of the colony, not a strict majority, but the principle—that a subset must reach a tipping point—aligns with Paxos’ requirement for a quorum to guarantee safety.

8.2 Leader Election in Autonomous Drones

Consider a fleet of AI‑controlled drones tasked with monitoring a hive for disease. The drones must agree on a sampling schedule so they do not overlap or miss critical time windows. Implementing a Multi‑Paxos leader among the drones provides a lightweight way to elect a coordinator that serializes schedule updates. If the leader drone crashes (e.g., due to battery failure), the remaining drones can quickly start a new Prepare round and elect a successor, ensuring the monitoring mission never stalls.

8.3 Fault Tolerance for Sensor Networks

A sensor network spread across a forest may experience intermittent connectivity due to weather. Using Paxos’s asynchronous guarantees, the network can continue to aggregate temperature readings as long as a quorum of sensors remains reachable. The system can tolerate up to f sensor failures without losing data consistency, which is critical when the network feeds a predictive model for bee foraging patterns.

8.4 Bridging Theory and Practice

By teaching conservationists and AI researchers about Paxos, we enable cross‑disciplinary tooling:

• Simulation frameworks can embed Paxos to model how bees reach consensus on resource allocation.
• AI agents can adopt Paxos‑style protocols to negotiate shared policies without central control, preserving autonomy while guaranteeing safety.
• Data pipelines that ingest hive sensor streams can rely on Paxos‑backed databases (e.g., CockroachDB) to ensure that every observation is stored exactly once, even under network partitions.

9. Practical Tips for Implementing Paxos

10. Why It Matters

Paxos may appear as an abstract theorem about numbers and messages, but its impact is concrete: it keeps our money safe, ensures the reliability of cloud services, and enables autonomous agents to cooperate without a single point of control. For the Apiary community, understanding Paxos unlocks a toolkit for building resilient, self‑governing AI systems that can monitor, protect, and nurture bee populations at scale.

When a hive’s health data is stored in a Paxos‑backed database, a single node failure does not erase a critical observation of pesticide exposure. When a swarm of drones negotiates a flight plan using a Multi‑Paxos leader, they avoid mid‑air collisions and keep the monitoring mission on schedule. When researchers model bee consensus with Paxos‑inspired thresholds, they gain insights that translate into better pollination strategies and habitat preservation.

In short, consensus is the invisible glue that binds distributed entities—whether they are servers, bees, or AI agents. By demystifying Paxos, we give you the confidence to design systems that are safe, live, and valid, no matter how chaotic the world around them becomes.

Ready to explore more? Check out our deeper dive into distributed-systems and the fascinating parallels between bees-and-self-organization and consensus algorithms.