DISTRIBUTED CONSENSUS-
PAXOS
Shah Khalid
Shah.khalid{@}seecs.edu.pk
National University of Sciences and
Technology (NUST)
DISTRIBUTED CONSENSUS-PAXOS
Overview
What is Paxos?
Why is Paxos needed?
What we need in a distributed consensus protocol?
How Paxos works?
Paxos Algorithm
Practical case
2
MONARCHY VS. PARLIAMENT SYSTEM
Issue: how to detect and
sequence concurrent requests?
3
PAXOS AND ASSOCIATED ALGORITHM
In fact, it is among the
simplest and most
obvious of distributed
algorithms. Fictional consensus system
4
PAXOS
Paxos is an algorithm that is used to achieve
consensus among a distributed set of computers that
communicate….
https://simbo1905.blog/2016/01/02/paxos-uses-
leaders-multi-paxos-is-paxos/
Proposed in the following paper:
Lamport, Leslie. "Paxos made simple." ACM Sigact
News 32.4 (2001): 18-25.
5
WHAT IS TO REACH CONSENSUS WITH PAXOS?
6
WHAT IS TO REACH CONSENSUS WITH PAXOS?
7
WHAT IS TO REACH CONSENSUS WITH PAXOS?
8
REAL WORD EXAMPLE
Explanation …………..
9
WHY DO SYSTEMS NEED TO REACH CONSENSUS
10
WHY DO SYSTEMS NEED TO REACH CONSENSUS
11
WHY DO SYSTEMS NEED TO REACH CONSENSUS
12
WHY DO SYSTEMS NEED TO REACH CONSENSUS
13
WHY DO SYSTEMS NEED TO REACH CONSENSUS
14
WHY DO SYSTEMS NEED TO REACH CONSENSUS
15
ASSUMPTIONS FOR THE ALGORITHM
Concurrent proposals: One or more systems may
propose a value concurrently. If only one system would
propose a value then it is clear what the consensus would
be. With multiple systems, we need to select one from
among those values.
Validity: The chosen value that is agreed upon must be
one of the proposed values. The servers cannot just
choose a random number.
Majority rule: Once a majority of Paxos servers agrees
on one of the proposed values, we have consensus on that
value. This also implies that a majority of servers need to
be functioning for the algorithm to run. To
survive m failures, we will need 2m+1 systems.
Announcement: Once consensus is reached, the results
can be made known to everyone.
16
PAXOS BASICS
17
WHAT WE NEED IN A DISTRIBUTED CONSENSUS
PROTOCOL?
We have an environment of multiple systems (nodes)
connected by a network, where one or more of these
nodes may concurrently propose a value
e.g. perform an operation on a server, select a coordinator, add
to a log, whatever…. We need a protocol to choose exactly one
value in cases where multiple competing values may be
proposed…
Multiple proposers, single acceptor
what if the acceptor crashes?
Fault tolerance: multiple acceptors
18
HOW PAXOS WORKS?
Paxos has three entities:
Proposers: Receive requests (values) from clients and try to
convince acceptors to accept their proposed values.
Acceptors: Accept certain proposed values from proposers and
let proposers know if something else was accepted. A response
from an acceptor represents a vote for a particular proposal.
Learners: Announce the outcome.
In practice, a single node may run proposer, acceptor,
and learner roles. It is common for Paxos to co-exist with
the service that requires consensus (e.g., distributed
storage) on a set of replicated servers, with each server
taking on all three roles rather than using separate
servers dedicated to Paxos. For the sake of discussing the
protocol, however, we consider these to be independent
entities.
19
THE PAXOS PROTOCOL
two-phase protocol,
the proposers interact with the acceptors twice
Phase-1
A proposer asks all the working acceptors whether
anyone already received a proposal. If the answer is no,
propose a value
Phase-2
If a majority of acceptors agree to this value then that is
our consensus
20
THE PAXOS PROTOCOL (CONT…)
When a proposer receives a client request to reach
consensus on a value, the proposer must create
a proposal number. This number must have two
properties:
It must be unique. No two proposers can come up with
the same number. An easy way of doing this is to use a
global process identifier for the least significant bits of
the number. For example, instead of an ID=12, node 3
will generate ID=12.3 and node 2 will generate 12.2.
It must be bigger than any previously used identifier
used in the cluster. A proposer may use an incrementing
counter or use a nanosecond-level timestamp to achieve
this. If the number is not bigger than one previously
used, the proposer will find out by having its proposal
rejected and will have to try again.
21
PHASE 1: PREPARE-PROMISE
proposer receives a consensus request for a VALUE from
a client.
creates a unique proposal number, ID, and sends
a PREPARE(ID) message to at least a majority of acceptors.
Each acceptor that receives the PREPARE message looks at
the ID in the message and decides:
If the proposer receives a PROMISE response from a majority
of acceptors, it now knows that a majority of them are willing
to participate in this proposal. The proposer can now proceed
with getting consensus. Each of these acceptors made
a promise that no other proposal with a smaller number can
make it to consensus.
22
PHASE 2: PROPOSE-ACCEPT
If a proposer received a PROMISE message from the
majority of acceptors, it now has to tell the acceptors
to accept that proposal. If not, it has to start over
with another round of Paxos…
In this phase of the protocol, the proposer tells all
the acceptors (that are live) what value to accept. It
sends:
PROPOSE(ID,VALUE )
The logic the acceptor uses is
23
CONT..
The ACCEPTED message can be sent back to the
proposer as well as to the learners so they can propagate
the value to wherever its action is needed (e.g., append to
a log, modify a replicated database, …).
When the proposer or learner receives a majority of accept
messages then it knows that consensus has been reached on
the value.
To summarize
Phase-1, the proposer finds out that no promises have been
made to higher numbered proposals.
Phase-2, the proposer asks the acceptors to accept the proposal
with a specific value. As long as no higher numbered proposals
have arrived during this time, the acceptor responds back that
the proposal has been accepted.
24
BASIC PAXOS ALGORITHM
Phase 1a: “Prepare”
Select proposal number* N and send a prepare(N) request to a
quorum of acceptors.
Phase 1b: “Promise”
If N > number of any previous promises or acceptances,
Proposer * promise to never accept any future proposal less than N,
- send a promise(N, U) response
(where U is the highest-numbered proposal accepted so far (if any))
Phase 2a: “Accept!”
If proposer received promise responses from a quorum,
- send an accept(N, W) request to those acceptors Acceptor
(where W is the value of the highest-numbered proposal among the promise
responses, or any value if no promise contained a proposal)
Phase 2b: “Accepted”
If N >= number of any previous promise,
* accept the proposal
- send an accepted notification to the learner
25
EXAMPLE
26
EXAMPLE
27
EXAMPLE
28
29
Good Luck
30
