1 of 48

Section 4: Lab 3

CSE 452 Autumn 2025

2 of 48

Announcements

Lab 2 code due tomorrow (01/30)
Pset 3 due Tuesday (02/03)
Review syllabus for late day policy

48 hr grace period for lab 2
48 hr grace period for Pset 3
NO grace period for design docs

Lab 2 design doc feedback released on Gradescope

Review all comments on design doc => page through even if close to full credit received

3 of 48

Where we are in the course:

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

Lab 2: primary/backup replication

What if server crashes :’)

What if view server crashes :’)

4 of 48

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 48

At a high level, Paxos works with majorities (more than half) and promises

What is in a majority gets propagated
Not accepting anything lower is maintained

6 of 48

Simple Paxos

Purpose: reach consensus on a single value in a distributed system
Roles

Proposers
Acceptors

Phases

Prepare phase

Initiated by the proposers

Send a proposal with proposal number to acceptors

Propose phase

Begins once a proposal has been accepted by a majority
Proposer sends the actual value to acceptors

7 of 48

Simple Paxos

Implementation Details

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

8 of 48

Example: Proposer Protocol

A

Q

M

K

Proposers

Acceptors

HP#

*HP#: highest prepare proposal number

2

-1, null

2, V1

A(2, V1)

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

9 of 48

Example: Proposer Protocol

A

Q

M

K

Proposers

Acceptors

HP#

*HP#: highest prepare proposal number

2

-1, null

2, V1

4

2

4

-1, null

4, V2

A(4, V2)

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

10 of 48

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

Q

M

K

Proposers

Acceptors

2, V1

4, V2

8

Prepare Request

HP# 2

HP# 4

-1, null

*HP#: highest prepare proposal number

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

11 of 48

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

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

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

12 of 48

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 never again to 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

-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

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

13 of 48

Example: Proposer Protocol

A

Q

M

K

Proposers

Acceptors

2, V1

4, V2

HP# 8

-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

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

14 of 48

A more detailed example…

15 of 48

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

-1, -1, null

16 of 48

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

17 of 48

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

18 of 48

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

19 of 48

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

20 of 48

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

21 of 48

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

22 of 48

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

23 of 48

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

Worksheet: Once A3 has accepted A(2, v2), what are the possible final consensus values?

24 of 48

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

25 of 48

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

26 of 48

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

Worksheet: What are acceptor responses to P(3), what happens to HP#, HA#, HAV?

27 of 48

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

28 of 48

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

29 of 48

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

Worksheet: Once A1 and A2 accept A(3, v1), what are the possible final consensus values?

30 of 48

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

Worksheet: What happens to the delayed A(2, v2)?

31 of 48

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

32 of 48

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

33 of 48

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

34 of 48

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

35 of 48

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

36 of 48

p1

p2

A1

A2

A3

HP#, HA#, HAV

3, 3, v1

4, 4, v1

Consensus Value: v1

🥳🎉🙌

37 of 48

A Problem: Reusing Proposal Numbers

P1

P2

P3

P(0)

(0, -)

(0, u), (0, v)???

A(0, u)

(0, u)

(0, v)

A(0, v)

What could now go wrong at p3 when it sends the Prepare msg?

38 of 48

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, ...

39 of 48

Putting it all together…

40 of 48

Server1

1

2

3

4

...

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

41 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

P(1, 1.1)

Key:

<message>(<slot #>, <proposal #>)

Colors:

Not started

In progress

Value chosen

42 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

PR(1, -1, null)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

Colors:

Not started

In progress

Value chosen

43 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

PR(1, -1, null)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

Colors:

Not started

In progress

Value chosen

P(2, 1.3)

Paxos election can happen across multiple slots simultaneously.

44 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

A(1, 1.1, S1)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

A(<slot #>, <proposal #>, <proposal value>)

Colors:

Not started

In progress

Value chosen

PR(2, -1, null)

Paxos election can happen across multiple slots simultaneously.

45 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

AR()

A(1, 1.1, S1)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

A(<slot #>, <proposal #>, <proposal value>)

AR() // accepted

Colors:

Not started

In progress

Value chosen

PR(2, -1, null)

Paxos election can happen across multiple slots simultaneously.

46 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:1.3

HAV:S2

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:

HAV:

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

A(1, 1.1, S1)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

A(<slot #>, <proposal #>, <proposal value>)

AR() // accepted

Colors:

Not started

In progress

Value chosen

A(2, 1.3, S3)

Paxos election can happen across multiple slots simultaneously.

47 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:1.3

HAV:S3

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:1.3

HAV:S2

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:1.3

HAV:S3

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

A(1, 1.1, S1)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

A(<slot #>, <proposal #>, <proposal value>)

AR() // accepted

Colors:

Not started

In progress

Value chosen

AR()

Paxos election can happen across multiple slots simultaneously.

48 of 48

Server1

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:1.3

HAV:S3

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server3

1

2

3

4

...

HP#:1.1

HA#:

HAV:

HP#:1.3

HA#:1.3

HAV:S2

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

Server2

1

2

3

4

...

HP#:1.1

HA#:1.1

HAV:S1

HP#:1.3

HA#:1.3

HAV:S3

HP#:

HA#:

HAV:

HP#:

HA#:

HAV:

A(1, 1.1, S1)

Key:

P(<slot #>, <proposal #>)

PR(<slot #>, HP#, HAV)

A(<slot #>, <proposal #>, <proposal value>)

AR() // accepted

Colors:

Not started

In progress

Value chosen

Paxos election can happen across multiple slots simultaneously.