### slides

```Leslie Lamport
Summary: Piras Maha
Outline
 History
 Problem
 Choosing A Value
 Learning
 Simple Example
History
 Leslie Lamport
 Presented in 1990
 Almost everyone dismissed it
 The first paper was a difficult read, hard to understand
 Took 10 years before publication, required almost a
complete re-write
 Gained popularity really quickly in distributed system
 Lots of decomposition and optimizations, still being
applied to date
The Problem
 Assume a collection of processes
 Each process proposes a value
 Considered consensus algorithm( chooses a single
value is chosen)
 If no value is proposed then no value should be chosen
 If a value has been chosen processes should be able to
learn chosen value
The Problem
 Safety requirement for consensus
 Only a value proposed may be chosen
 Only single value is chosen
 Process never learns value has been chosen unless it
actually has been
 Three roles of algorithm preformed by three classes of
agents
 Proposers
 Acceptors
 Learners
The Problem
 Agents can communicate with each asynchronously
(through messaging)
 Agents operate at arbitrary speed
 May fail, may restart (information should be
remembered)
 Messages may take arbitrary delivery times, can be
duplicated, can be lost but not corrupted
Choosing A Value – Simple Logic
 A simple method: have one acceptor
 A proposer sends a proposal to acceptor
 Acceptor chooses first value it receives
 Issue: if acceptor fails, make further progress not
possible
Choosing A Value – P1
 What if we used multiple acceptors?
 Proposer sends value to a set of acceptors
 An acceptor may accept proposed value
 Value chosen if majority (or large enough set of
acceptors) chooses it
 In absence of message loss or failure, want a value
chosen even if only one value proposed by proposer
 P1: An acceptor must accept the first proposal that it
receives
Choosing A Value – P1
 P1 raises an issue: several values proposed by different
proposers , where every accepted a value but no
majority
 Or two values were proposed and half were chosen by
one set of acceptors
 Failure of single acceptor could make it impossible to
learn which value was chosen
Choosing A Value – P1
 P1 and requirement considering value is chosen when
accepted by a majority imply acceptor must be allowed
to accept multiple proposals
 To track the proposals, each proposal consists of
proposal number and value
 Different proposal would have different numbers
 A value is chosen when single proposal with that value
is accepted by majority of acceptors
Choosing A Value – P2
 Multiple proposals may be chosen but value must be




same in all
P2: If a proposal with value v is chosen, then every
higher-number proposal that is chosen has value v
This guarantees that only single value will be chosen
Again, to be chosen, proposal must be accepted by at
least one acceptor
P2a: If a proposal with a value v is chosen, then every
higher-numbered proposal accepted by any acceptor
has value v
Choosing A Value
 Since communication is asynchronous, a proposal may
be chosen with an acceptor c, not received any
proposal
 At this point if a new proposer issues a higher-number
proposal with a different value, P1 requires c to accept,
thereby violating P2a
 P2b: IF a proposal with value v is chosen then every
higher number proposal issued by any proposer has
value v
Choosing A Value
 Since proposal must be issued before it is accepted,
P2b implies P2a which implies P2
 Prove P2
 Assume proposal with number m and value v chosen
 Any proposal issued with number n, n>m has value v
 Using induction on n, can prove n had value v, with
additional assumption: every proposal number with a
number in the range m to (n-1) has value v
 For proposal m to be chosen, a majority of acceptors C,
where every acceptor in C has accepted it
Choosing A Value
 This m (Hypothesis ) is chosen and it implies:
 Every acceptor in C has accepted a proposal with number in
the range m ...(n-1) and every proposal with a number in
m...(n-1) accepted by any acceptor has value v
 Since any set S, with majority acceptors, contains at least
one C leads to proposal number n has value v by(leading
to) :
 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 number less
than n
Choosing A Value – Issuing
Proposals
 Or (b) v is the value of the highest numbered proposal among
all proposals numbered less than n accepted by the acceptors
in S
 A proposer that wants to issue a proposal numbered n,
must learn the highest numbered proposal with number
less than n, if any, that has been accepted so far
 To do this: a proposer chooses number n, sends request to
acceptors asking for response containing
 Promise to not accept proposal numbered less than n
 Proposal with highest number less than n, that has been
accepted
 Called: Prepare Request
Choosing A Value – Issuing
Proposals
 If proposer receives requested responses from
majority, then issue proposal with number n and value
v (where v is highest numbered proposal among
responses or new number if no proposals reported)
 Proposer later sends a request that proposal has been
accepted
Choosing A Value - Acceptor
 Acceptor can receive two kinds of requests from
proposers
 Prepare request
 Accept request
 Can ignore requests
 P1a: an acceptor can accept a proposal number n if and
only if it has not responded to a prepare request
having a number greater than n
 With this, a complete algorithm for choosing value
Choosing A Value – Algorithm
Optimization
 Consider acceptor receives a prepare request with
number n, but already responded to prepare request
with number greater than n
 Therefore promised not to accept any proposal
numbered n
 Which means no reason to respond to this request or
respond to a request for a for a proposal that was already
accepted
Choosing A Value
 Now, acceptor only needs to remember the highest –
number proposal that was accepted and the number of
highest-numbered prepare request which was
responded to
 Since P2c kept invariant regardless of failures, acceptor
must remember this information if failure or restart
 Note: proposer can abandon proposal and forget all
about it, as long as it doesn’t issue another proposal
with same number
Choosing A Value - Algorithm
 Phase 1
 Proposer sends prepare request with number n to
majority of acceptors with proposal number n
 If an acceptor receives a prepare request with number n
(this n is greater than any prepare request which it has
already responded up until now), then it responds to the
request with a promise not to accept any more proposals
numbered less than n and with the highest-numbered
proposal (if any) that it has accepted
Choosing A Value - Algorithm
 Phase 2
 If proposer receives response to its prepare request (for
example numbered n) from majority of acceptors


Proposer sends accept request to all acceptors with proposal
number n (with value v), where v is the value of the highestnumbered proposal from the responses OR is any value, if no
responses were heard
If acceptor receives request for proposal number n, it will
accept this proposal unless it already responded to a prepare
with a number greater than n
Choosing A Value
 Multiple proposals can be made
 Follows algorithm each time
 Proposer can abandon in the middle of protocol
 Correctness should be maintained
Sequence with no errors
Learning A Chosen Value
 To learn a value is chosen, learner must first know the
proposal has been accepted by majority
 Obvious solution to let each acceptor respond to all
learners (sending proposal)
 Good: allows all learners find out about chosen value
quickly
 Bad: requires each acceptor to respond to each learner
(large number of responses, number of learners x
number of acceptors)
Learning A Chosen Value
 Another option: have one distinguished learner
 Have this learner communicate to all other learners
(which value chosen)
 Bad: less reliable, if distinguished learner fails
 Requires extra round for all learners to discover chosen
value
 Good: requires less responses( number of acceptors +
number of learners)
Learning A Chosen Value
 Next approach would be to have a set of distinguished
learners
 Acceptors send acceptances to the set of distinguished
learners
 Larger the set, more reliable but adds
complexity/greater communication
Progress
 Consider: proposer p, completes phase 1, proposal





number n1
Another proposer q, then completes phase 1 for
proposal number n2, n2>n1
Proposer p’s accept request for n1 are ignored since
acceptors promised not to accept proposal number<
n2
Then p, begins and completes phase 1 for n3, n3>n2
Therefore q’s phase 2 accept requests ignored,
...
Progress
 Use distinguished proposer, only one to try issuing
proposals
 If distinguished proposer communicates with majority
of acceptors, using proposal number greater than any
already used, then it can succeed issuing an accepted
proposal
 Abandon proposal then trying again if it learns of new
request with higher proposal number, this
distinguished proposer will eventually choose high
enough proposal number
Progress
 If enough of proposers, acceptors and communication
network is working properly, electing single
distinguished proposer can lead to liveness
 Reliable algorithm for electing distinguished proposer
may require randomness or real-time (based on
research results)
The Implementation
 Paxos algorithm assumes network of processes
 In its heart, considered consensus algorithm, with agents




playing proposer, acceptor, learner
Leader is chosen, plays distinguished proposer and learner
Paxos consensus algorithm requests and responses sent as
ordinary messages
Stable storage (alive during failure) contains information
acceptor must remember
Acceptor records in stable storage before sending response
State Machine Implementation
 Use collection of servers, each one implementing state
machine independently
 Deterministic
 Guarantee execution osfsame sequence of state machine
commands
Another Look
 To put it simple terms: Paxos is used to have
consistency (ordering of semantics) on a platform with
multiple machines
 Why is this important?



If ordering is jumbled, the meaning is lost
Unreliable
Could cause safety issues
Another Look - Example
 Jane has \$0 in her account
 Joe sends \$100 to Jane
 When Jane is notified she received \$100, she sends \$50
cheque to CRA
 CRA cashs the cheque and spends it on something
useless
 Without consistent ordering, each machine might
view these in different order
Author QA
 What would you like to convey to current and future
researchers and practitioners?
Don’t pay attention to pedantic old farts like me telling
you what to do.
 What are the most important lessons you’ve learned in
your career?
My career has been idiosyncratic. Any meaningful
lessons I could draw from it would, at best, apply to
people starting their careers 30 years ago.
Ref: http://research.microsoft.com/en-us/um/people/lamport/pubs/ds-interview.pdf
References
 http://ayende.com/blog/4496/paxos-enlightment
 http://www.inf.usi.ch/faculty/pedone/MScThesis/mar
co.pdf
 http://the-paper-trail.org/blog/?p=173
 Paxos Made Simple by Leslie Lamport (2001)
```