Scribd
Upload
210 views18 pages

Paxos for Distributed Systems Experts

This document summarizes Leslie Lamport's Paxos algorithm for reaching distributed consensus. Paxos provides a simple way for a group of distributed processes to agree on a single value. It works by having proposers suggest values to acceptors, who promise not to accept any other values. If a majority of acceptors promise the same value, that value is chosen. The algorithm uses proposal numbers to ensure consistency even if multiple proposals are in progress simultaneously. Paxos guarantees safety by only allowing a chosen value to be one that was proposed, and only choosing a single value.

Uploaded by

Parth Thakkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
210 views18 pages

Paxos for Distributed Systems Experts

This document summarizes Leslie Lamport's Paxos algorithm for reaching distributed consensus. Paxos provides a simple way for a group of distributed processes to agree on a single value. It works by having proposers suggest values to acceptors, who promise not to accept any other values. If a majority of acceptors promise the same value, that value is chosen. The algorithm uses proposal numbers to ensure consistency even if multiple proposals are in progress simultaneously. Paxos guarantees safety by only allowing a chosen value to be one that was proposed, and only choosing a single value.

Uploaded by

Parth Thakkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 18

Paxos Made Simple

Gene Pang
Paxos
• L. Lamport, The Part-Time Parliament,
September 1989

• Aegean island of Paxos


• A part-time parliament
– Goal: determine the sequence of decrees passed
• Lamport related their protocol to fault-
tolerant distributed systems
So Simple, So Obvious

• “In fact, it is among the simplest and most


obvious of distributed algorithms.”
- Leslie Lamport
Simple Pseudocode
Paxos Made Simple - 2001
• It actually IS simple
– Lamport walks through the algorithm

• Distributed consensus problem


– Group of processes must agree on a single value
– Value must be proposed
– After value is agreed upon, it can be learned
Safety Requirements
• Only a value which has been proposed can be
chosen
• Only a single value can be chosen
• A process never learns a value unless it was
actually chosen
3 Types of Agents
• Proposers
• Acceptors
• Learners

• Assumption: asynchronous, non-byzantine


model
Choosing a Value
• Proposer sends proposal to group of acceptors
– Value is chosen when majority accepts
• P1: an acceptor must accept first proposal it
receives
Multiple Pending Proposals?
• If there are multiple proposals, no proposal
may get the majority
– 3 proposals may each get 1/3 of the acceptors

• Solution: acceptors can accept multiple


proposals, distinguished by a unique proposal
number
Multiple Accepted Proposals
• All chosen proposals must have the same
value

• P2: If a proposal with value v is chosen, then


every higher-numbered proposal that is
chosen also has value v
– P2a: … accepted …
– P2b: … proposed …
Guaranteeing P2b
• For any proposal number n with value v, and a
majority set S:
– Acceptors in S have not accepted any proposal less
than n
OR
– v is the same value as the highest-numbered
protocol less than n, that was accepted in S

• Proposers ask acceptors to “promise”


2 Phase Protocol – Phase 1
• (a) proposers send PREPARE(n) to acceptors
• (b) acceptors response:
– if n is larger than any other
• send the value v of the highest-numbered accepted
proposal, if it exists
• this is a “promise” to not accept anything less than n
– if acceptor already responded to message greater
than n
• Do nothing
2 Phase Protocol – Phase 2
• (a) If the proposer gets responses from a
majority, sends ACCEPT(n, v) to acceptors
– v is the value of the highest-numbered accepted
proposal, or a new value
• (b) An acceptor accepts the ACCEPT(n, v) if it
did not respond to a higher-numbered
PREPARE(n’) message
Simple Implementation
• Every process is acceptor, proposer, and
learner
• A leader is elected to be the distinguished
proposer and learner
– Distinguished proposer to guarantee progress
• Avoid dueling proposers
– Distinguished learner to reduce too many
broadcast messages
Example: Prepare

PREPARE(10) PREPARE(10)

ACCEPT(5, “A”)

Highest Accept: Highest Accept:


(5, “A”) (5, “A”)
Highest Prepare: Highest Prepare:
(15) (8)
(10)
Example: Accept

ACCEPT(10, “A”) ACCEPT(10, “A”)

YES

Highest Accept: Highest Accept:


(5, “A”) (5, “A”)
(10, “A”)
Highest Prepare: Highest Prepare:
(15) (10)
Example: Livelock

ACCEPT(10,
PREPARE(10)
PREPARE(12)
“A”) ACCEPT(11, “A”)
PREPARE(11)
PREPARE(13)

ACCEPT(5, “A”) ACCEPT(5, “A”)

Highest Accept:
(5, “A”)
Highest Prepare:
(8)
(10)
(11)
(12)
(13)
Future
• Paxos already used for many distributed
systems/storage
• Paxos (and variations) will be important in the
future
– Achieve various points in the CAP spectrum
• Newer distributed consensus algorithms may
need to consider:
– Wide-area networks
– Varying latencies
– Performance characteristics and probabilistic
guarantees

You might also like