Skip to content

Fast Paxos and its tradeoffs#

2024-02-27

Fast Paxos (Lamport, 2005) reduces the common-case latency from 2 message delays to 1, but the price is a larger quorum.

Classic Paxos#

Two-phase, two message delays:

  • Phase 1: Prepare/Promise — leader collects promises from a majority.
  • Phase 2: Accept/Accepted — leader proposes value, waits for majority accepts.

Fast Paxos#

Under low contention, clients send values directly to acceptors, skipping the leader. Acceptors accept the value if it's the first they see in the current round.

  • Fast round: 1 message delay, but requires a fast quorum of ⌈3n/4⌉ (not ⌈n/2⌉+1).
  • Classic recovery round: falls back to 2 delays if fast quorum can't agree.

The math#

For n acceptors, the fast quorum size Q_f must satisfy:

Q_f + Q_f - n ≥ Q_c

where Q_c is the classic majority (⌈n/2⌉+1). Solving: Q_f ≥ ⌈3n/4⌉.

When Fast Paxos helps#

  • Low contention — different clients propose different values but into different slots.
  • WAN latency dominates — a single round-trip saved is a big deal.
  • Enough replicas that ⌈3n/4⌉ is achievable — with 5 acceptors, fast quorum is 4; with 3 acceptors, fast quorum is 3 (i.e., unanimity, which defeats the purpose).

When Fast Paxos hurts#

  • High contention — Fast rounds often fail, forcing recovery rounds, which are slower than classic Paxos.
  • Small clusters — the fast quorum requirement is too strict.
  • Anywhere you'd use Raft — Raft's simplicity usually wins over Fast Paxos's theoretical speedup.

Reference#

  • Lamport, Fast Paxos (Distributed Computing, 2006).
  • Junqueira, Reed, Serafini, Zab: High-performance broadcast for primary- backup systems (DSN 2011) — related but different.