FoundationConcept & Pseudocode Entry

Paxos Consensus

Reaches fault-tolerant distributed consensus across asynchronous replicated servers using two-phase Prepare/Promise and Accept/Accepted quorum rounds.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Consensus
Difficulty: Advanced
Family: Distributed Consensus
Tier: Foundation
Status: Reviewed
Review: AI Reviewed
Sources: 2
Formulas: 1
Relationships: 1
Code example: Not ready
Visualization: Not ready
Aliases: Single-Decree Paxos, Multi-Paxos

Overview

Paxos is the foundational fault-tolerant consensus protocol by Leslie Lamport that guarantees safety under asynchronous network delays, packet loss, and non-Byzantine node crashes whenever a majority quorum (⌊N/2⌋ + 1) of acceptors is reachable. Multi-Paxos elects a stable distinguished proposer (leader) to amortize Phase 1 across a sequence of replicated log instances.

Core Concepts

monotonic term numbersmajority quorum intersectionup-to-date log election restrictionleader completeness

Quick facts

Complexity

Runtime and memory behavior at a glance.

Not yet documented

When to Use

Fault-tolerant distributed quorum consensus protocol (Prepare/Promise and Propose/Accept phases) enabling replicated servers to agree on a single value or state machine log despite node crashes and network delays.
Fault-tolerant state machine replication and distributed consensus across 3, 5, or 7 server replicas.
Consensus coordination, leader lease management, and strongly consistent metadata stores.

When Not to Use

Single-node local queues or round-robin CPU scheduling without network replication.
Byzantine environments with malicious actors (use PBFT or HotStuff instead).

What It Does

Coordinates proposers, acceptors, and learners using monotonically increasing ballot numbers so at most one value is chosen per log slot.
Elects a distinguished proposer in Multi-Paxos so steady-state log replication requires a single round-trip quorum broadcast.

Use Cases

Consensus among replicated servers in distributed KV stores (etcd, CockroachDB, Consul, TiKV)
Leader election and configuration management in cluster control planes
Fault-tolerant replicated state machines

Inputs

Cluster node states, current term, replicated log entries, and RPC messages (RequestVote, AppendEntries)

Outputs

Linearizable committed log prefix and elected cluster leader

Key Formulas (1)

Crash-Fault Quorum

Q = \lfloor N / 2 \rfloor + 1,\quad N = 2f + 1

Q = \lfloor N / 2 \rfloor + 1,\quad N = 2f + 1

Any two majority quorums intersect in at least one server.

Pseudocode

1.Follower converts to Candidate if election timeout elapses without leader AppendEntries
2.Candidate increments currentTerm, votes for self, and broadcasts RequestVote(term, lastLogIndex, lastLogTerm)
3.Voter grants vote iff candidateTerm >= currentTerm, not yet voted in term, and candidate log is at least as up-to-date
4.Candidate receiving majority votes (> N/2) becomes Leader and sends AppendEntries heartbeats
5.Leader advances commitIndex to N once a majority of matchIndex[i] >= N and log[N].term == currentTerm

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Follower converts to Candidate if election timeout elapses without leader AppendEntries
Candidate increments currentTerm, votes for self, and broadcasts RequestVote(term, lastLogIndex, lastLogTerm)
Voter grants vote iff candidateTerm >= currentTerm, not yet voted in term, and candidate log is at least as up-to-date
Candidate receiving majority votes (> N/2) becomes Leader and sends AppendEntries heartbeats
Leader advances commitIndex to N once a majority of matchIndex[i] >= N and log[N].term == currentTerm

Canonical Example

Input: 5-node cluster (quorum = 3), Leader L1 replicates command x=42 at index 8 (term 2)
Output: Committed once L1 + 2 followers acknowledge index 8 in term 2
Explanation: Any future leader elected in term > 2 must overlap with at least one node in the 3-node quorum and therefore possesses index 8.

Implementation Notes

Persist currentTerm, votedFor, and log[] to stable storage before responding to any RPC.

Common Pitfalls

Dueling proposers causing livelock without randomized backoff or a stable Multi-Paxos leader.
Failing to fsync promised ballot numbers and accepted values before replying to proposers.

Interactive Mechanism Walkthrough & State Debugger

Graph Frontier & Edge Relaxation

Follower -> Candidate -> Leader state transitions and majority quorum log commit.

active vertexs

visited set V{ s }

frontier queue[ u ]

edges relaxed0 / 7

Step 1 of 5: Follower converts to Candidate if election timeout elapses without leader AppendEntries

graph-search

Notes

Tolerates up to f crash/network faults in a cluster of 2f + 1 nodes (unlike Byzantine fault tolerance which requires 3f + 1).

Sources (2)

What each reference supports for this entry.

Lamport (1998) — The Part-Time Parliament

Paper

Original specification of the Paxos fault-tolerant consensus state machine.

Open source

Lamport (2001) — Paxos Made Simple

Paper

Concise derivation of the two-phase Paxos safety invariant.