1 of 39

(Single Instance) Paxos

CSE 452 Spring 2024

2 of 39

Part-Time Parliament

“My attempt at inserting some humor into the subject was a dismal failure. People who attended my lecture remembered Indiana Jones, but not the algorithm. People reading the paper apparently got so distracted by the Greek parable that they didn’t understand the algorithm. Among the people I sent the paper to, and who claimed to have read it, were Nancy Lynch, Vassos Hadzilacos, and Phil Bernstein. A couple of months later I emailed them the following question:

Can you implement a distributed database that can tolerate the failure of any number of its processes (possibly all of them) without losing consistency, and that will resume normal behavior when more than half the processes are again working properly?

None of them noticed any connection between this question and the Paxos algorithm.” –Leslie Lamport

3 of 39

Where we are in the course:

Lab 1: Exactly-once execution of RPCs despite unreliable network conditions

Lab 2: Primary/backup replication

Lab 3: Multi-paxos

No node failure tolerance

Tolerate some node failures (VS is single point of failure)

Tolerate less than majority node failure

4 of 39

Motivation

Consensus: want to decide on a single value among multiple distributed nodes

Each node is a replica of a state machine (in our case a key/value store)

Want to be able to do this even if some nodes fail

Should be able to continue operation if a majority are alive

Want to be able to do this asynchronously
All servers must execute all client requests in the same order

Asynchronous distributed system:

Clocks may be out of sync
Messages can be delayed an for an arbitrary amount of time (no upper limit on message delays).

Primary Backup could tolerate some failures, but not failures of the VS.

With paxos we can handle about n/2 failures with an n-node cluster for any node type.

Biggest thing with DS is that, if you have multiple servers, you want their state to be consistent (linearizability)

Op(Add $100 to my account), Op(Double the money in my account). Order matters, you want the nodes to execute these in the same order. How to do this? PAXOS

What does PAXOS guarantee? Only one value will be selected, meaning all nodes will agree on value/op that they want to execute.

Consensus: We should eventually choose a value, We should only choose one value

5 of 39

Today...

We’re talking about a single instance of Paxos:

How to decide on a single value

Rest of week: Multi(-instance) Paxos [What you’re doing for Lab 3!]:

How to decide on multiple values

Put k1 v1

Get k1

Put k1 v2

Get k1

…

Slots

6 of 39

Example: Proposer Protocol

A proposer chooses a new proposal number n and sends a request to each member of some (majority) set of acceptors, asking it to respond with:

A

Q

M

K

Proposers

Acceptors

2, V1

4, V2

8

Prepare Request

HP# 2

HP# 4

-1, null

*HP#: highest prepare proposal number

7 of 39

Example: Proposer Protocol

A proposer chooses a new proposal number n and sends a request to each member of some (majority) set of acceptors, asking it to respond with:

A

Q

M

K

Proposers

Acceptors

2, V1

4, V2

HP# 8

-1, null

i solemnly promise to never accept anything less than 8

*HP#: highest prepare proposal number

8 of 39

Example: Proposer Protocol

A proposer chooses a new proposal number n and sends a prepare request to each member of some (majority) set of acceptors, asking it to respond with:

a promise to never accept a proposal numbered less than n, and
the accepted value associated with the highest proposal number less than n if any.

A

Q

M

K

Proposers

Acceptors

2, V1

4, V2

HP# 8

HP# 4

-1, null

2, V1

-1, null

4, V2

Prepare Reply

*HP#: highest prepare proposal number

majority,

:D

i solemnly promise to never accept anything less than 8

9 of 39

Example: Proposer Protocol

A

Q

M

K

Proposers

Acceptors

2, V1

4, V2

HP# 8

HP# 4

-1, null

*HP#: highest prepare proposal number

What value could be proposed?

the value associated with the highest proposal-numbered response among all the 1b messages, or
any value selected by the proposer if all responders in the majority had not accepted any previous values

8, V2

Accept Request

10 of 39

Acceptor Protocol [acceptor <- proposer]

An acceptor receives prepare and accept requests from proposers. It can ignore these without affecting safety.

11 of 39

Acceptor Protocol [acceptor <- proposer]

An acceptor receives prepare and accept requests from proposers. It can ignore these without affecting safety.

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

12 of 39

Acceptor Protocol [acceptor <- proposer]

An acceptor receives prepare and accept requests from proposers. It can ignore these without affecting safety.

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

P1a: An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having proposal number greater than n

13 of 39

Key Takeaways

Proposer:

Always proposes the value with the highest proposal number

Acceptor:

Only accept values with a higher proposal number than the current highest seen proposal number.
Always reply with value associated with highest seen proposal number.

P2: “If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.”

14 of 39

Paxos in 25 lines

--- 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, n_a, v_a) from majority:� 5 v' = v_a with highest n_a; 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 acceptor state on each node (persistent):� 10 n_p --- highest prepare seen� 11 n_a, v_a --- highest accept seen� � 12 acceptor's prepare(n) handler:� 13 if n > n_p� 14 n_p = n� 15 reply prepare_ok(n, n_a, v_a)� 16 else� 17 reply prepare_reject� � 18 acceptor's accept(n, v) handler:� 19 if n >= n_p� 20 n_p = n� 21 n_a = n� 22 v_a = v� 23 reply accept_ok(n)� 24 else� 25 reply accept_reject�

http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html

15 of 39

Example Key

Messages

P(n): prepare request with proposal number n
PR(n,v): prepare reply with n as the highest proposal number accepted and v as the corresponding accepted value
A(n,v): accept request with proposal number n and value v
AR(ok): accept reply with either "accept" or "reject"

Acceptor State

HP#: Highest Prepare Proposal Number Seen
HA#: Highest Accepted Proposal Number
HAV: Highest Accepted Value

16 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

-1, -1, null

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

17 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

-1, -1, null

P(1)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

18 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, -1, null

-1, -1, null

1, -1, null

PR(-1, null)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

19 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, -1, null

-1, -1, null

1, -1, null

A(1, v1)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

20 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

-1, -1, null

1, -1, null

AR(accept)

A(1, v1)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

21 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

-1, -1, null

1, -1, null

A(1, v1)

P(2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

22 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, -1, null

A(1, v1)

PR(-1, null)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

23 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, -1, null

A(1, v1)

A(2, v2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

24 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, 2, v2

2, -1, null

A(1, v1)

A(2, v2)

AR(accept)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

25 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, 2, v2

2, -1, null

A(1, v1)

A(2, v2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

26 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, 2, v2

2, -1, null

AR(reject)

A(2, v2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

27 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

1, 1, v1

2, 2, v2

2, -1, null

A(2, v2)

P(3)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

28 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 1, v1

2, 2, v2

3, -1, null

A(2, v2)

PR(1, v1)

PR(-1, null)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

29 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 1, v1

2, 2, v2

3, -1, null

A(2, v2)

A(3, v1)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

30 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

2, 2, v2

3, 3, v1

A(2, v2)

AR(accept)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

31 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

2, 2, v2

3, 3, v1

A(2, v2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

32 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

2, 2, v2

3, 3, v1

AR(reject)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

33 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

2, 2, v2

3, 3, v1

P(4)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

34 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

4, 2, v2

4, 3, v1

PR(3, v1)

PR(2, v2)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

35 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

4, 2, v2

4, 3, v1

A(4, v1)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

36 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

4, 4, v1

AR(accept)

P: Prepare Request

PR: Prepare Reply

A: Accept Request

AR: Accept Reply

HP#: Highest Prepare Proposal Number

HA#: Highest Accepted Proposal Number

HAV: Highest Accepted Value

37 of 39

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

4, 4, v1

Consensus Value: v1

🥳🎉🙌

38 of 39

A Problem: Reusing Proposal Numbers

4

5

A

B

(4, A)

(4, B)

(4, A), (4, B)???

39 of 39

Guaranteeing Unique Proposal Numbers

Proposers only use strictly increasing proposal numbers
Each proposer is assigned a “slice” of all numbers
Example:

P1: 1, 4, 7 …
P2: 2, 5, 8 …
P3: 3, 6, 9 …

Alternatively, make the proposal number unique by combining with the proposer’s address

Server1: 1.1, 2.1, 3.1, 4.1, ...
Server2: 1.2, 2.2, 3.2, 4.2, ...
Server3: 1.3, 2.3, 3.3, 4.3, ...