Paxos 共识

6.5840 2026 Lecture 4: Fault-Tolerant Agreement, Paxos

From Paxos Made Simple, by Leslie Lamport, 2001

remember GFS coordinator
  what if the coordinator fails?
  GFS paper did not have much to say about what happens
  many services built on GFS, so ought to be automatic and reliable
  what to do?

good overall goals:
  high availability via replication
    continue even if one server has crashed or can't be contacted
    "no single point of failure"
  strongly consistent
    look as if a single server

why designing a fault-tolerant coordinator is hard
  suppose we want to use primary/backup replication
    we want clients to switch to backup if primary fails
  a broken scheme:
  [C1, C2, net, S1, S2]
  clients ordinarily send all ops to S1
    S1 replies, and also forwards to S2 (for replication)
    S1 is primary, S2 is backup
  if client gets no response from S1, re-send to S2
    so the system can tolerate the failure of S1
  problem:
    suppose network failure:
      C1 and S1 can communicate;
      C2 and S2 can communicate;
      but C1/S1 can't talk to C2/S2
    on both sides, it seems like the other failed
    so both S1 and S2 will independently act as primary
    "network partition"
    "split brain"
  computers can't distinguish "server crashed" from "network broken"
    all they can observe is "no response to my request"
  this comes up again and again in fault-tolerant designs!

for a while automated fault-tolerant fail-over seemed impossible
  due to possibility of partition
  special external agent (a human) was used to switch primaries
  but that's a single point of failure
  not very scalable for big systems

around 1989 a few solutions appeared -- surprise!
  Paxos is the simplest, easiest to understand
  inspired many widely used schemes
    we'll see Paxos in multiple papers later in the course
  incorporates ideas worth knowing

Paxos provides fault-tolerant "agreement", "consensus"
  to allow a set of computers to agree on a single value
  for example, who the current primary is
  if some Paxos participants agree on X,
    no participant will think some other value was agreed
  despite computer or network failures
  no split brain even if partition

Paxos performs just one agreement
  Real systems need a sequence of Paxos agreements
    e.g. a new agreement to recover after each coordinator failure

a key idea: quorums
  [diagram: three servers]
  an odd number of servers, e.g. 3
  responses from a majority are required to do anything -- 2 out of 3
  if cannot contact a majority, cannot make progress
  (quorum idea is much older than Paxos)

a useful property of majorities is that any two intersect
  if some information is known by a majority,
    any later majority will contain at least one server that knows
  so each step in a quorum system typically looks like
    send message to all participants
    gather a majority of responses (but don't wait for more)
      look at responses to find latest state
    send updated state message to all participants
  nice:
    tolerates minority of failed or slow servers
    overlap ensures state changes aren't lost

another property of majorities:
  at most one network partition can contain a majority of servers
  servers in the minority partitions won't get a quorum, won't proceed
  so at most one partition will perform operations
    helps avoid split brain

note: majority is out of all servers, not just out of live ones

we say 2f+1 servers can tolerate f failed servers
  since the remaining f+1 is a majority of 2f+1
  3 servers can tolerate 1 failed server
  5 servers can tolerate 2 failed
  so you can get more availability (at some expense!)

What properties does Paxos guarantee?
  correctness:
    if agreement reached, all agreeing servers agree on same value
    once any agreement reached, never changes its mind
  fault-tolerance:
    can proceed if f+1 of 2f+1 (a majority) can communicate
      i.e. can tolerate <= f failed servers
    no majority -> cannot proceed
      but will resume correctly once f+1 are again available
      e.g. can survive a site-wide power failure
  liveness:
    will reach agreement when a majority can communicate for long enough
    (this is a weak property)

let's look at the Paxos algorithm
  this is a pseudo-code version of the paper

to cope with failures during agreement protocol,
  Paxos may go through multiple numbered rounds,
    each driven by a proposer.
  any server can propose if it thinks agreement hasn't yet been reached.
  two message exchanges per round:
    prepare, prepare_ok
    accept, accept_ok

definition: S accepts n/v
  S responded accept_ok to accept(n, v)

definition: n/v is chosen
  a majority accepted n/v

the crucial property:
  if v is chosen, any subsequent choice will also == v
    protocol will not change its mind
    maybe a different proposer &c, but same value!
  tricky b/c "chosen" is system-wide property
    e.g. what if majority accepts, then proposer crashes?
    no server can tell locally that a value was chosen

----------------

proposer(v):
  choose n, unique and higher than any n seen so far
  send prepare(n) to all servers including self
  if prepare_ok(n, n_a, v_a) from majority:
    v' = v_a with highest n_a; choose own v otherwise
    send accept(n, v') to all
    if accept_ok(n) from majority:
      send decided(v') to all

acceptor state:
  must persist across reboots
  n_p (highest prepare seen)
  n_a, v_a (highest accept seen)

acceptor's prepare(n) handler:
  if n > n_p
    n_p = n
    reply prepare_ok(n, n_a, v_a)
  else
    reject

acceptor's accept(n, v) handler:
  if n >= n_p
    n_p = n
    n_a = n
    v_a = v
    reply accept_ok(n)
  else
    reject

-----------------

example 1 (normal operation):
  S1, S2, S3
  but S3 is dead or slow
  S1 starts proposal, n=5 v=A
S1: p5    a5A    dA
S2: p5    a5A    dA
S3: dead...
"p5" means Sx receives prepare(n=5)
"a5A" means Sx receives accept(n=5, v=A)
"dA" means Sx receives decided(v=A)
these diagrams are not specific about who the proposer is
  we only care about what acceptors saw and replied

Proposer only needs to wait for a majority
  so it can continue even though S3 was down

What would happen if S3 was alive, but network partitioned?
  and S3 wanted to propose value B?
  S3's prepare would not assemble a majority

the homework question:
  How does Paxos ensure that the following sequence of events can't
  happen? What actually happens, and which value is ultimately chosen?
  S1 wants to propose v=X, crashes after sending two accepts
  S2 wants v=Y
  S1: p1 a1X
  S2: p1     p2 a2?
  S3: p1 a1X p2 a2?
  S3's prepare_ok to prepare(2) would have included "X"
    thus a2X
    good: X had been chosen in the first round; chosen again in 2nd
  the point:
    if the system has already reached agreement, majority will know value.
    any new majority of prepares will intersect that majority.
    so subsequent proposer will learn of already-agreed-on value,
    and send it in accept msgs

example 2 (concurrent proposers):
S1 starts proposing n=10
S1 sends first accept v=X; meanwhile
S3 starts proposing n=11
  but S1 does not receive its proposal
  S3 only has to wait for a majority of prepare responses
S1: p10 a10X
S2: p10        p11
S3: p10        p11  a11Y
S1 is still sending out accept messages...
has a value been chosen?
what will happen?
  what will S2 do if it gets a10X accept msg from S1?
  what will S1 do if it gets a11Y accept msg from S3?
what if S3 were to crash after just one a11Y (and not restart)?

important design pattern:
  if there's evidence that agreement *might* have been reached already,
    must act as if it had been.
  proposer may not *know*,
    since its majority may overlap by just one with previous.
  nevertheless, must be conservative.

how about this:
S1: p10  a10X               p12
S2: p10          p11  a11Y
S3: p10          p11        p12   a12X
has the system agreed to a value at this point?
  after all, a majority have accepted value "X"

what's the "commit point"?
  i.e. exactly when has agreement been reached?
  i.e. at what point can a server safely act on the agreement?
  i.e. at what point might *some other* server have already acted?
  after a majority has the same v_a? no -- why not?  above counterexample
  after a majority has the same v_a/n_a? yes

why does the proposer need to pick v_a with highest n_a?
S1: p10  a10A               p12
S2: p10          p11  a11B
S3: p10          p11  a11B  p12   a12?
n=11 already agreed on vB
n=12 sees both vA and vB, but must choose vB
why this makes sense: two cases:
  1. a value had been chosen before n=11
     n=11's prepares would have seen value and re-used it
     so it's safe for n=12 to re-use n=11's value
  2. no value had been chosen before n=11
     n=11 might have obtained a majority
     so it's required for n=12 to re-use n=11's value

why does accept handler check n >= n_p?
  w/o n >= n_p check, you could get this bad scenario:
  S1: p1 p2 a1A
  S2: p1 p2 a1A a2B
  S3: p1 p2     a2B
  oops, for a while A was chosen, then changed to B!

why does accept handler update n_p = n?
  required to prevent earlier n's from being accepted
  server can receive accept(n,v) even though it never saw prepare(n)
  without n_p = n, can get this bad scenario:
  S1: p1    a2B a1A p3 a3A
  S2: p1 p2         p3 a3A
  S3:    p2 a2B
  oops, for a while B was chosen, then changed to A!

what if proposer S2 chooses n < S1's n?
  e.g. S2 didn't see any of S1's messages
  S2 won't make progress, so no correctness problem

what if an acceptor crashes+reboots after sending accept_ok?
S1: p1  a1X
S2: p1  a1X reboot  p2  a2?
S3: p1              p2  a2?
we know X was chosen; but will proposal #2 preserve X?
the story:
  S2 is the only intersection between p1's and p2's majorities
  thus the only evidence that Paxos already chose X
  so S2 *must* return X in prepare_ok(n=2)
  so S2 must be able to recover its pre-crash n_a/v_a (and n_p)
thus: if S2 wants to re-join this Paxos instance after crash,
  it must remember its n_p/v_a/n_a on disk.
  if lost, do not re-join!

what if an acceptor reboots after sending prepare_ok?
  does it have to remember n_p on disk?
  if n_p not remembered, this could happen:
  S1: p10            a10X
  S2: p10 p11 reboot a10X a11Y
  S3:     p11             a11Y
  11's did not receive a prepare_ok w/ X, so 11 proposed its own value Y
  but just before that, X had been chosen!
  b/c S2 did not remember to ignore a10X
  so: persisting n_p prevents this

can Paxos get stuck?
  yes, if there is not a majority that can communicate
  once net/computers repaired, Paxos will continue

Performance?
  viewed as slow due to multiple communication rounds
    but lots of schemes for optimizing/batching
  viewed as expensive: need 3 replicas (not 2)
  but hard to avoid in serious fault-tolerant systems

-----------------

Many systems use Paxos internally, in a couple of styles.
  To agree on a new coordinator when the old one doesn't respond.
  To agree on when the backup should take over from the primary.
  To agree on the sequence of operations in an RSM.

How to build a database RSM using Paxos
  [diagram: clients, 3 replicas, paxos layer, log, DB layer]
  clients can send operations to any replica
  servers use Paxos to *agree* on each next op to append to the log
  servers apply agreed+logged operations to state (e.g. k/v DB)
    in log order

example:
  client sends "x=1" to S1
  S1 picks log entry 3
  S1 uses Paxos to get all servers to agree that entry 3 holds x=1
  after agreement ("commit"), all DBs execute x=1

example:
  client sends "x?" to S2
  S2 picks log entry 4
  S2 uses Paxos to get all servers to agree that entry 4 holds "x?"
  after agreement, S2's DB executes "x?"
    and replies to the client

why a log?
  help cope with concurrency
    need to hold later operations until earlier ones have committed
  help replicas catch up
    not in majority, briefly offline, &c
  usually only the tail of the log is kept, along with "state"

next:
  guest lecture by a Go wizard
  then Raft
  Lab 1 due tomorrow

--- Paxos Proposer ---

     1  proposer(v):
     2    while not decided:
     2      choose n, unique and higher than any n seen so far
     3      send prepare(n) to all servers including self
     4      if prepare_ok(n, na, va) from majority:
     5        v' = va with highest na; choose own v otherwise
     6        send accept(n, v') to all
     7        if accept_ok(n) from majority:
     8          send decided(v') to all


        --- Paxos Acceptor ---

     9  state on each node (persistent):
    10   np     --- highest prepare seen
    11   na, va --- highest accept seen

    12  prepare(n) handler:
    13   if n > np
    14     np = n
    15     reply prepare_ok(n, na, va)
    16   else
    17     reply reject


    18  accept(n, v) handler:
    19   if n >= np
    20     np = n
    21     na = n
    22     va = v
    23     reply accept_ok(n)
    24   else
    25     reply reject

Paxos Made Simple
Leslie Lamport
01 Nov 2001

Abstract
The Paxos algorithm, when presented in plain English, is very simple.

Contents
1 Introduction 1
2 The Consensus Algorithm 1
2.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Choosing a Value . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Learning a Chosen Value . . . . . . . . . . . . . . . . . . . . . 6
2.4 Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 The Implementation . . . . . . . . . . . . . . . . . . . . . . . 7
3 Implementing a State Machine 8
References 11

1 Introduction
The Paxos algorithm for implementing a fault-tolerant distributed system
has been regarded as difficult to understand, perhaps because the original
presentation was Greek to many readers [5]. In fact, it is among the sim-
plest and most obvious of distributed algorithms. At its heart is a consensus
algorithm—the “synod” algorithm of [5]. The next section shows that this
consensus algorithm follows almost unavoidably from the properties we want
it to satisfy. The last section explains the complete Paxos algorithm, which
is obtained by the straightforward application of consensus to the state ma-
chine approach for building a distributed system—an approach that should
be well-known, since it is the subject of what is probably the most often-cited
article on the theory of distributed systems [4].
2 The Consensus Algorithm
2.1 The Problem
Assume a collection of processes that can propose values. A consensus al-
gorithm ensures that a single one among the proposed values is chosen. If
no value is proposed, then no value should be chosen. If a value has been
chosen, then processes should be able to learn the chosen value. The safety
requirements for consensus are:
• Only a value that has been proposed may be chosen,
• Only a single value is chosen, and
• A process never learns that a value has been chosen unless it actually
has been.
We won’t try to specify precise liveness requirements. However, the goal is
to ensure that some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.
We let the three roles in the consensus algorithm be performed by three
classes of agents: proposers, acceptors, and learners. In an implementation,
a single process may act as more than one agent, but the mapping from
agents to processes does not concern us here.
Assume that agents can communicate with one another by sending mes-
sages. We use the customary asynchronous, non-Byzantine model, in which:
1

• Agents operate at arbitrary speed, may fail by stopping, and may
restart. Since all agents may fail after a value is chosen and then
restart, a solution is impossible unless some information can be re-
membered by an agent that has failed and restarted.
• Messages can take arbitrarily long to be delivered, can be duplicated,
and can be lost, but they are not corrupted.
2.2 Choosing a Value
The easiest way to choose a value is to have a single acceptor agent. A pro-
poser sends a proposal to the acceptor, who chooses the first proposed value
that it receives. Although simple, this solution is unsatisfactory because the
failure of the acceptor makes any further progress impossible.
So, let’s try another way of choosing a value. Instead of a single acceptor,
let’s use multiple acceptor agents. A proposer sends a proposed value to a
set of acceptors. An acceptor may accept the proposed value. The value is
chosen when a large enough set of acceptors have accepted it. How large is
large enough? To ensure that only a single value is chosen, we can let a large
enough set consist of any majority of the agents. Because any two majorities
have at least one acceptor in common, this works if an acceptor can accept
at most one value. (There is an obvious generalization of a majority that
has been observed in numerous papers, apparently starting with [3].)
In the absence of failure or message loss, we want a value to be chosen
even if only one value is proposed by a single proposer. This suggests the
requirement:
P1. An acceptor must accept the first proposal that it receives.
But this requirement raises a problem. Several values could be proposed by
different proposers at about the same time, leading to a situation in which
every acceptor has accepted a value, but no single value is accepted by a
majority of them. Even with just two proposed values, if each is accepted by
about half the acceptors, failure of a single acceptor could make it impossible
to learn which of the values was chosen.
P1 and the requirement that a value is chosen only when it is accepted
by a majority of acceptors imply that an acceptor must be allowed to accept
more than one proposal. We keep track of the different proposals that an
acceptor may accept by assigning a (natural) number to each proposal, so a
proposal consists of a proposal number and a value. To prevent confusion,
we require that different proposals have different numbers. How this is
2

achieved depends on the implementation, so for now we just assume it. A
value is chosen when a single proposal with that value has been accepted by
a majority of the acceptors. In that case, we say that the proposal (as well
as its value) has been chosen.
We can allow multiple proposals to be chosen, but we must guarantee
that all chosen proposals have the same value. By induction on the proposal
number, it suffices to guarantee:
P2. If a proposal with value v is chosen, then every higher-numbered pro-
posal that is chosen has value v .
Since numbers are totally ordered, condition P2 guarantees the crucial safety
property that only a single value is chosen.
To be chosen, a proposal must be accepted by at least one acceptor. So,
we can satisfy P2 by satisfying:
P2a . If a proposal with value v is chosen, then every higher-numbered pro-
posal accepted by any acceptor has value v .
We still maintain P1 to ensure that some proposal is chosen. Because com-
munication is asynchronous, a proposal could be chosen with some particu-
lar acceptor c never having received any proposal. Suppose a new proposer
“wakes up” and issues a higher-numbered proposal with a different value.
P1 requires c to accept this proposal, violating P2 a . Maintaining both P1
and P2 a requires strengthening P2 a to:
P2b. If a proposal with value v is chosen, then every higher-numbered pro-
posal issued by any proposer has value v .
Since a proposal must be issued by a proposer before it can be accepted by
an acceptor, P2 b implies P2 a , which in turn implies P 2.
To discover how to satisfy P2 b, let’s consider how we would prove that
it holds. We would assume that some proposal with number m and value
v is chosen and show that any proposal issued with number n > m also
has value v . We would make the proof easier by using induction on n,
so we can prove that proposal number n has value v under the additional
assumption that every proposal issued with a number in m . . (n − 1) has
value v , where i . . j denotes the set of numbers from i through j . For the
proposal numbered m to be chosen, there must be some set C consisting of a
majority of acceptors such that every acceptor in C accepted it. Combining
this with the induction assumption, the hypothesis that m is chosen implies:
3

Every acceptor in C has accepted a proposal with number in
m . . (n − 1), and every proposal with number in m . . (n − 1)
accepted by any acceptor has value v .
Since any set S consisting of a majority of acceptors contains at least one
member of C , we can conclude that a proposal numbered n has value v by
ensuring that the following invariant is maintained:
P2c. For any v and n, if a proposal with value v and number n is issued,
then there is a set S consisting of a majority of acceptors such that
either (a) no acceptor in S has accepted any proposal numbered less
than n, or (b) v is the value of the highest-numbered proposal among
all proposals numbered less than n accepted by the acceptors in S .
We can therefore satisfy P2 b by maintaining the invariance of P2 c.
To maintain the invariance of P2 c, a proposer that wants to issue a pro-
posal numbered n must learn the highest-numbered proposal with number
less than n, if any, that has been or will be accepted by each acceptor in
some majority of acceptors. Learning about proposals already accepted is
easy enough; predicting future acceptances is hard. Instead of trying to pre-
dict the future, the proposer controls it by extracting a promise that there
won’t be any such acceptances. In other words, the proposer requests that
the acceptors not accept any more proposals numbered less than n. This
leads to the following algorithm for issuing proposals.
1. A proposer chooses a new proposal number n and sends a request to
each member of some set of acceptors, asking it to respond with:
(a) A promise never again to accept a proposal numbered less than
n, and
(b) The proposal with the highest number less than n that it has
accepted, if any.
I will call such a request a prepare request with number n.
2. If the proposer receives the requested responses from a majority of
the acceptors, then it can issue a proposal with number n and value
v , where v is the value of the highest-numbered proposal among the
responses, or is any value selected by the proposer if the responders
reported no proposals.
4

A proposer issues a proposal by sending, to some set of acceptors, a request
that the proposal be accepted. (This need not be the same set of acceptors
that responded to the initial requests.) Let’s call this an accept request.
This describes a proposer’s algorithm. What about an acceptor? It can
receive two kinds of requests from proposers: prepare requests and accept
requests. An acceptor can ignore any request without compromising safety.
So, we need to say only when it is allowed to respond to a request. It can
always respond to a prepare request. It can respond to an accept request,
accepting the proposal, iff it has not promised not to. In other words:
P1a . An acceptor can accept a proposal numbered n iff it has not responded
to a prepare request having a number greater than n.
Observe that P1 a subsumes P1.
We now have a complete algorithm for choosing a value that satisfies the
required safety properties—assuming unique proposal numbers. The final
algorithm is obtained by making one small optimization.
Suppose an acceptor receives a prepare request numbered n, but it has
already responded to a prepare request numbered greater than n, thereby
promising not to accept any new proposal numbered n. There is then no
reason for the acceptor to respond to the new prepare request, since it will
not accept the proposal numbered n that the proposer wants to issue. So
we have the acceptor ignore such a prepare request. We also have it ignore
a prepare request for a proposal it has already accepted.
With this optimization, an acceptor needs to remember only the highest-
numbered proposal that it has ever accepted and the number of the highest-
numbered prepare request to which it has responded. Because P2 c must
be kept invariant regardless of failures, an acceptor must remember this
information even if it fails and then restarts. Note that the proposer can
always abandon a proposal and forget all about it—as long as it never tries
to issue another proposal with the same number.
Putting the actions of the proposer and acceptor together, we see that
the algorithm operates in the following two phases.
Phase 1. (a) A proposer selects a proposal number n and sends a prepare
request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater
than that of any prepare request to which it has already responded,
then it responds to the request with a promise not to accept any more
proposals numbered less than n and with the highest-numbered pro-
posal (if any) that it has accepted.
5

Phase 2. (a) If the proposer receives a response to its prepare requests
(numbered n) from a majority of acceptors, then it sends an accept
request to each of those acceptors for a proposal numbered n with a
value v , where v is the value of the highest-numbered proposal among
the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered
n, it accepts the proposal unless it has already responded to a prepare
request having a number greater than n.
A proposer can make multiple proposals, so long as it follows the algorithm
for each one. It can abandon a proposal in the middle of the protocol at any
time. (Correctness is maintained, even though requests and/or responses
for the proposal may arrive at their destinations long after the proposal
was abandoned.) It is probably a good idea to abandon a proposal if some
proposer has begun trying to issue a higher-numbered one. Therefore, if an
acceptor ignores a prepare or accept request because it has already received
a prepare request with a higher number, then it should probably inform
the proposer, who should then abandon its proposal. This is a performance
optimization that does not affect correctness.
2.3 Learning a Chosen Value
To learn that a value has been chosen, a learner must find out that a pro-
posal has been accepted by a majority of acceptors. The obvious algorithm
is to have each acceptor, whenever it accepts a proposal, respond to all
learners, sending them the proposal. This allows learners to find out about
a chosen value as soon as possible, but it requires each acceptor to respond
to each learner—a number of responses equal to the product of the number
of acceptors and the number of learners.
The assumption of non-Byzantine failures makes it easy for one learner
to find out from another learner that a value has been accepted. We can
have the acceptors respond with their acceptances to a distinguished learner,
which in turn informs the other learners when a value has been chosen. This
approach requires an extra round for all the learners to discover the chosen
value. It is also less reliable, since the distinguished learner could fail. But
it requires a number of responses equal only to the sum of the number of
acceptors and the number of learners.
More generally, the acceptors could respond with their acceptances to
some set of distinguished learners, each of which can then inform all the
learners when a value has been chosen. Using a larger set of distinguished
6

learners provides greater reliability at the cost of greater communication
complexity.
Because of message loss, a value could be chosen with no learner ever
finding out. The learner could ask the acceptors what proposals they have
accepted, but failure of an acceptor could make it impossible to know whether
or not a majority had accepted a particular proposal. In that case, learners
will find out what value is chosen only when a new proposal is chosen. If
a learner needs to know whether a value has been chosen, it can have a
proposer issue a proposal, using the algorithm described above.
2.4 Progress
It’s easy to construct a scenario in which two proposers each keep issuing
a sequence of proposals with increasing numbers, none of which are ever
chosen. Proposer p completes phase 1 for a proposal number n 1. Another
proposer q then completes phase 1 for a proposal number n 2 > n 1. Proposer
p’s phase 2 accept requests for a proposal numbered n 1 are ignored because
the acceptors have all promised not to accept any new proposal numbered
less than n 2. So, proposer p then begins and completes phase 1 for a new
proposal number n 3 > n 2, causing the second phase 2 accept requests of
proposer q to be ignored. And so on.
To guarantee progress, a distinguished proposer must be selected as the
only one to try issuing proposals. If the distinguished proposer can com-
municate successfully with a majority of acceptors, and if it uses a proposal
with number greater than any already used, then it will succeed in issuing a
proposal that is accepted. By abandoning a proposal and trying again if it
learns about some request with a higher proposal number, the distinguished
proposer will eventually choose a high enough proposal number.
If enough of the system (proposer, acceptors, and communication net-
work) is working properly, liveness can therefore be achieved by electing a
single distinguished proposer. The famous result of Fischer, Lynch, and Pat-
terson [1] implies that a reliable algorithm for electing a proposer must use
either randomness or real time—for example, by using timeouts. However,
safety is ensured regardless of the success or failure of the election.
2.5 The Implementation
The Paxos algorithm [5] assumes a network of processes. In its consensus
algorithm, each process plays the role of proposer, acceptor, and learner.
The algorithm chooses a leader, which plays the roles of the distinguished
7

proposer and the distinguished learner. The Paxos consensus algorithm is
precisely the one described above, where requests and responses are sent as
ordinary messages. (Response messages are tagged with the corresponding
proposal number to prevent confusion.) Stable storage, preserved during
failures, is used to maintain the information that the acceptor must re-
member. An acceptor records its intended response in stable storage before
actually sending the response.
All that remains is to describe the mechanism for guaranteeing that no
two proposals are ever issued with the same number. Different proposers
choose their numbers from disjoint sets of numbers, so two different pro-
posers never issue a proposal with the same number. Each proposer remem-
bers (in stable storage) the highest-numbered proposal it has tried to issue,
and begins phase 1 with a higher proposal number than any it has already
used.
3 Implementing a State Machine
A simple way to implement a distributed system is as a collection of clients
that issue commands to a central server. The server can be described as
a deterministic state machine that performs client commands in some se-
quence. The state machine has a current state; it performs a step by taking
as input a command and producing an output and a new state. For ex-
ample, the clients of a distributed banking system might be tellers, and
the state-machine state might consist of the account balances of all users.
A withdrawal would be performed by executing a state machine command
that decreases an account’s balance if and only if the balance is greater than
the amount withdrawn, producing as output the old and new balances.
An implementation that uses a single central server fails if that server
fails. We therefore instead use a collection of servers, each one independently
implementing the state machine. Because the state machine is deterministic,
all the servers will produce the same sequences of states and outputs if they
all execute the same sequence of commands. A client issuing a command
can then use the output generated for it by any server.
To guarantee that all servers execute the same sequence of state machine
commands, we implement a sequence of separate instances of the Paxos
consensus algorithm, the value chosen by the i th instance being the i th state
machine command in the sequence. Each server plays all the roles (proposer,
acceptor, and learner) in each instance of the algorithm. For now, I assume
that the set of servers is fixed, so all instances of the consensus algorithm
8

use the same sets of agents.
In normal operation, a single server is elected to be the leader, which
acts as the distinguished proposer (the only one that tries to issue proposals)
in all instances of the consensus algorithm. Clients send commands to the
leader, who decides where in the sequence each command should appear.
If the leader decides that a certain client command should be the 135 th
command, it tries to have that command chosen as the value of the 135 th
instance of the consensus algorithm. It will usually succeed. It might fail
because of failures, or because another server also believes itself to be the
leader and has a different idea of what the 135 th command should be. But
the consensus algorithm ensures that at most one command can be chosen
as the 135 th one.
Key to the efficiency of this approach is that, in the Paxos consensus
algorithm, the value to be proposed is not chosen until phase 2. Recall that,
after completing phase 1 of the proposer’s algorithm, either the value to be
proposed is determined or else the proposer is free to propose any value.
I will now describe how the Paxos state machine implementation works
during normal operation. Later, I will discuss what can go wrong. I consider
what happens when the previous leader has just failed and a new leader has
been selected. (System startup is a special case in which no commands have
yet been proposed.)
The new leader, being a learner in all instances of the consensus algo-
rithm, should know most of the commands that have already been chosen.
Suppose it knows commands 1–134, 138, and 139—that is, the values cho-
sen in instances 1–134, 138, and 139 of the consensus algorithm. (We will
see later how such a gap in the command sequence could arise.) It then
executes phase 1 of instances 135–137 and of all instances greater than 139.
(I describe below how this is done.) Suppose that the outcome of these ex-
ecutions determine the value to be proposed in instances 135 and 140, but
leaves the proposed value unconstrained in all other instances. The leader
then executes phase 2 for instances 135 and 140, thereby choosing commands
135 and 140.
The leader, as well as any other server that learns all the commands
the leader knows, can now execute commands 1–135. However, it can’t
execute commands 138–140, which it also knows, because commands 136
and 137 have yet to be chosen. The leader could take the next two commands
requested by clients to be commands 136 and 137. Instead, we let it fill the
gap immediately by proposing, as commands 136 and 137, a special “no-
op” command that leaves the state unchanged. (It does this by executing
phase 2 of instances 136 and 137 of the consensus algorithm.) Once these
9

no-op commands have been chosen, commands 138–140 can be executed.
Commands 1–140 have now been chosen. The leader has also completed
phase 1 for all instances greater than 140 of the consensus algorithm, and it
is free to propose any value in phase 2 of those instances. It assigns command
number 141 to the next command requested by a client, proposing it as the
value in phase 2 of instance 141 of the consensus algorithm. It proposes the
next client command it receives as command 142, and so on.
The leader can propose command 142 before it learns that its proposed
command 141 has been chosen. It’s possible for all the messages it sent
in proposing command 141 to be lost, and for command 142 to be chosen
before any other server has learned what the leader proposed as command
141. When the leader fails to receive the expected response to its phase 2
messages in instance 141, it will retransmit those messages. If all goes well,
its proposed command will be chosen. However, it could fail first, leaving a
gap in the sequence of chosen commands. In general, suppose a leader can
get α commands ahead—that is, it can propose commands i + 1 through
i +α after commands 1 through i are chosen. A gap of up to α−1 commands
could then arise.
A newly chosen leader executes phase 1 for infinitely many instances
of the consensus algorithm—in the scenario above, for instances 135–137
and all instances greater than 139. Using the same proposal number for
all instances, it can do this by sending a single reasonably short message
to the other servers. In phase 1, an acceptor responds with more than a
simple OK only if it has already received a phase 2 message from some
proposer. (In the scenario, this was the case only for instances 135 and
140.) Thus, a server (acting as acceptor) can respond for all instances with
a single reasonably short message. Executing these infinitely many instances
of phase 1 therefore poses no problem.
Since failure of the leader and election of a new one should be rare
events, the effective cost of executing a state machine command—that is, of
achieving consensus on the command/value—is the cost of executing only
phase 2 of the consensus algorithm. It can be shown that phase 2 of the
Paxos consensus algorithm has the minimum possible cost of any algorithm
for reaching agreement in the presence of faults [2]. Hence, the Paxos algo-
rithm is essentially optimal.
This discussion of the normal operation of the system assumes that there
is always a single leader, except for a brief period between the failure of the
current leader and the election of a new one. In abnormal circumstances,
the leader election might fail. If no server is acting as leader, then no new
commands will be proposed. If multiple servers think they are leaders, then
10

they can all propose values in the same instance of the consensus algo-
rithm, which could prevent any value from being chosen. However, safety is
preserved—two different servers will never disagree on the value chosen as
the i th state machine command. Election of a single leader is needed only
to ensure progress.
If the set of servers can change, then there must be some way of deter-
mining what servers implement what instances of the consensus algorithm.
The easiest way to do this is through the state machine itself. The current
set of servers can be made part of the state and can be changed with ordi-
nary state-machine commands. We can allow a leader to get α commands
ahead by letting the set of servers that execute instance i + α of the con-
sensus algorithm be specified by the state after execution of the i th state
machine command. This permits a simple implementation of an arbitrarily
sophisticated reconfiguration algorithm.
References
[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility
of distributed consensus with one faulty process. Journal of the ACM ,
32(2):374–382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus
when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821,
Laboratory for Computer Science, Massachusetts Institute Technology,
Cambridge, MA, 02139, May 2001. also published in SIGACT News
32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess
systems. Computer Networks , 2:95–114, 1978.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed
system. Communications of the ACM , 21(7):558–565, July 1978.
[5] Leslie Lamport. The part-time parliament. ACM Transactions on Com-
puter Systems , 16(2):133–169, May 1998.
11

Paxos FAQ

Q: How does Paxos prevent split-brain?

A: For Paxos, split brain means that different servers "agree" on
different values. The places in Paxos where it must wait for a
majority to respond are enough to prevent this. If there are two
active proposers, the Paxos algorithm requires them both to get
prepare replies from a majority of acceptors, and accept replies from
a majority of acceptors. The two proposers' majorities must overlap in
at least one server; the reply from that server will tell the losing
proposer (the one with the smaller n) that it has lost, or (if the
lower number proposer has already reached agreement) will tell the
higher-numbered server what the agreed value was.

If a network failure has partitioned the servers, then at most one of
the partitions can possibly contain a majority of the servers. So
Paxos will only be able to reach agreement in that partition. Servers
in the other partitions won't be able to agree on anything. Thus split
brain is avoided under network partition.

Q: What are some ways to ensure unique proposal numbers?

A: A proposer can put an ID that's different for each proposer in the
low bits of the proposal number. For example, a proposer could put its
IP address in the low bits. Then different proposers will never use
the same proposal number. Each proposer can avoid re-using the same
proposal number by keeping a variable holding the highest proposal
number it has used so far, and, when it starts a new proposal, make
sure the new proposal number is higher.

If you are feeling lucky, you could use numbers that have the current
time in the high bits and a random number in the low bits. You'd want
lots of bits for the random number to keep the probability of
collision super low.

Q: In 2.4, what is the distinguished proposer about?

A: The idea is that the implementation should try to make it likely
that there's at most one active proposal at a time. This is not a
requirement for correctness; it is advice about how to reach agreement
faster. One way to do this is to have each proposer wait a random
amount of time before sending prepare messages. Then there the
proposer who chose the smallest random number will go first and will
likely complete agreement before the other proposers finish their
sleeping. There can still be more than one proposer, but this
randomization scheme breaks the symmetry among the proposers and
causes it to be likely that one of them wins.

Q: How does the algorithm terminate?

A: A Paxos agreement doesn't have a well-defined termination point.
However, if there are no failures, a proposer can observe that
agreement has been reached (because it gets accept replies from
everyone), and it can safely stop proposing at that point.

Q: What are some use cases for Paxos?

A: Paxos helps you build replicated services, which can increase fault
tolerance. For example, one can build a Paxos-replicated database with
three servers, such that if one of the servers fails, the other two
can continue to execute database requests.

You can see various uses if you search the web for papers about Chubby,
Spanner, Megastore, Spinnaker, and Zookeeper.

Q: How fast is Paxos?

A: There are two main limits to performance: message exchanges, and
writing updated n and v information to disk (so they can be recovered
if the server crashes and restarts). Paxos requires at least two
message exchanges in order to agree; if all hosts are within the same
datacenter this might take a few hundred microseconds. Paxos also
requires two writes to the disk (one for prepare, one for accept);
depending on disk technology this could take anywhere from a few
hundred microseconds to a few tens of milliseconds.

So without clever optimizations Paxos will be relatively slow. This
paper describes some of what's needed for good performance:

  http://research.google.com/archive/paxos_made_live.html

Q: What does the paper mean by a leader on page 9? Does Paxos have a
leader?

A: Section 3 of the paper is not about Paxos itself, but about one way to
implement and use Paxos. Paxos itself doesn't require a leader. I do not
know whether any real-world Paxos implementations use the ideas in
Section 3. It may be that when the paper speaks of electing a leader, it
means using Paxos to agree on a leader. Or one could use any of a number
of schemes that usually (but not always) result in agreement on a leader
(since Paxos will be correct regardless), such as letting the
participant with the lowest IP address propose with no delay, but
requiring other participants to sleep for a random amount of time before
proposing. Much of the point of a leader is to avoid simultaneous
different proposals, which require multiple Paxos rounds to sort out.

The best paper I know about real-life implementation and use of Paxos is
Paxos Made Live:

  http://research.google.com/archive/paxos_made_live.html

Section 5.2 on master leases may be the most relevant.