1 of 48

Visualizing the 6 rules of Primary-Backup

CSE 452 Spring 2026

2 of 48

Announcements

Lab 1, Lab 1 design doc, Pset 1 due today (04/08)
Lab 2 design doc, Pset 2 due next Friday (04/17)

3 of 48

Motivating Primary-Backup:

What will we have accomplished in lab 1?

Exactly-once execution of RPCs despite unreliable network conditions

What do we aim to achieve in lab 2?

To understand replication
Tolerate some node failures (ViewServer is still a single point of failure)

4 of 48

General Flow

Pool of Idle Servers

Client

Primary

Backup

View Server

Request

Forward Request

Forward

Ack

Response

Ping

GetView

What messages do they send/receive?

5 of 48

General Flow

Pool of Idle Servers

Client

Primary

Backup

View Server

Request

Forward Request

Forward

Ack

Response

Ping

GetView

What messages do they send/receive?

ViewReply (VR)

VR

6 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

7 of 48

Rule 1: What if we did not forward requests before executing them? (primary changes)

Client

Server A

Server B

{}

Server C

{}

Append(foo->bar)

AppendOk(bar)

Primary: A

Backup: B

{foo: bar}

Append(foo->bar)

8 of 48

Rule 1: What if we did not forward requests before executing them? (primary changes)

Client

Server A

{foo: bar}

Server B

{}

Server C

{}

Get(foo)

Primary: B

Backup: C

KeyNotFound

9 of 48

Rule 1: What if we did not forward requests before executing them? (different views)

Client

Server A

Server B

{foo: bar}

Server C

{foo: bar}

Append(foo->baz)

Primary: B

Backup: C

AppendRes(barbaz)

Suppose both the client and Server A do not get the new View…

Append(foo->baz)

Primary: A

Backup: B

Primary: A

Backup: B

Primary: B

Backup: C

{foo: bar}

{foo: barbaz}

10 of 48

Rule 1: What if we did not forward requests before executing them? (different views)

Client

Server A

{foo: barbaz}

Server B

{foo: bar}

Server C

{foo: bar}

Primary: B

Backup: C

When the client eventually

gets the new view…

Get(foo)

GetRes(bar)

Primary: B

Backup: C

Primary: B

Backup: C

11 of 48

Rule 1: Solution

Primary must wait for backup to execute the command before executing it and replying to client.

…could there be an optimization on read commands…?

12 of 48

Rule 1: Solution

Primary must wait for backup to execute the command before executing it and replying to client.

…could there be an optimization on read commands…?

Yes, as long as you are okay with stale reads.

13 of 48

14 of 48

Rule 1: Takeaway

Forwarding!

Only execute a command on the Primary after receiving an acknowledgement from the Backup during forwarding
The backup is at most one command ahead of the primary at all time.
Hint: You may want to use a timer to ensure forwarded messages get processed. (A forwarded message could get dropped)
Note: In lab 2, the primary-backup will only handle one client request at a time

15 of 48

Aside: What happens if you try to process more than one client request at a time?

Primary

Backup

Put(“a”, “foo”)

“a” -> “foo”

Client 1

Put(“a”, “foo”)

Client 2

Put(“a”, “bar”)

“a” -> “bar”

“a” -> “foo”

16 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

17 of 48

Rule 2: Problem & Takeaway

Primary: A

Backup: B

Primary: B

Backup: C

Primary: C

Backup: D

Primary: D

Backup: B

Delayed Forward or a

Duplicated Forward

18 of 48

Rule 2: Problem & Takeaway

Takeaway: Have the view number on all messages

Primary: A

Backup: B

Primary: B

Backup: C

Primary: C

Backup: D

Primary: D

Backup: B

Delayed Forward or a

Duplicated Forward

19 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

20 of 48

Rule 3: What if the new Primary was not in the previous view?

Client

Server A

{}

Server B

{}

Server C

{}

Server D

{}

Append(foo->bar)

AppendRes(bar)

Primary: A

Backup: B

Server A

{foo: bar}

Server B

{foo: bar}

21 of 48

Rule 3: What if the new Primary was not in the previous view?

Client

Server A

{foo: bar}

Server B

{foo: bar}

Server C

{}

Server D

{}

Primary: C

Backup: D

Get(foo)

KeyNotFound()

Get(foo)

KeyNotFound()

22 of 48

Rule 3: Takeaway

Primary or backup in the previous view will have the most up to date application state. (recall rule 1)
An idle server could have an empty application state.

23 of 48

Possible Transitions?

The new primary MUST have been in the previous view

View i

Primary: A

Backup: B

View i+1

Primary: A

Backup: NULL

View i

Primary: A

Backup: B

View i+1

Primary: B

Backup: NULL

View i

Primary: A

Backup: B

View i+1

Primary: B

Backup: A

Some Possible? Transitions

24 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

25 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{}

Server B

{}

Put(a->bar)

Primary: A

Backup: B

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

26 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{a:bar}

Server B

{}

Put(a->bar)

Primary: A

Backup: B

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

27 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{a:bar}

Server B

{}

PutOk()

Primary: A

Backup: B

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

28 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{a:bar}

Server B

{}

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

29 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{a:bar}

Server B

{}

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

Get(a)

30 of 48

Rule 4: What if a non-primary responds to a client?

Server C

{}

Primary: B

Backup: null

Client

Server A

{a:bar}

Server B

{}

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: null

Primary: B

Backup: C

KeyNotFound()

31 of 48

Rule 4: Takeaway

Client is not guaranteed that they will be talking to the primary
Any node could be on an outdated view
Servers should only process/respond to client if they believe they are the primary

32 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

33 of 48

Recap: State Transfer (State Machine Replication)

Why do we state transfer?

To bring new backup (formerly idle server) up to date.

When do we do a state transfer?

If primary receives a new view with a new backup - need to do state transfer
V1: {S1, S2}, V2: {S1, S3}

What do we transfer?

Application state (In lab 2, that’s your entire AMOApplication)

34 of 48

Rule 5: Problem

Primary: A

Backup: B

Server A

{a:bar}

Primary: A

Backup: B

Everyone is in view 1…

Server B

{a:bar}

Primary: A

Backup: B

Server C

{}

Primary: A

Backup: B

VS

35 of 48

Rule 5: Problem

Primary: A

Backup: B

Server A

{a:bar}

Server B

{a:bar}

Primary: A

Backup: B

Primary: A

Backup: B

VS

Server B dies, ViewServer moves on to view 2. Server C is the “new” backup

Primary: A

Backup: C

Server C

{}

Primary: A

Backup: B

36 of 48

Rule 5: Problem

Server A

{a:bar}

Primary: A

Backup: B

VS

Server A dies and Server C is made primary (without view 2 ever being acked by A)

Primary: A

Backup: C

Primary: C

Backup: null

Server C

{}

Primary: A

Backup: B

Server B

{a:bar}

Primary: A

Backup: B

Primary: C

Backup: null

37 of 48

Rule 5: Problem

Server A

{a:bar}

Primary: A

Backup: B

VS

But when client shows up again..its not looking good:/

Primary: C

Backup: null

Server C

{}

Server B

{a:bar}

Primary: A

Backup: B

Primary: C

Backup: null

Client

Primary: C

Backup: null

KeyNotFound()

Get(a)

38 of 48

Rule 5: Problem Explained

The issue was changing the view before view 2 was acknowledged by the current primary (Server A) at the time

Prerequisite of an acknowledgement includes a completed state transfer to bring a “new” backup up to speed
If this is not done we lose app state which leads to a violation of the safety property

39 of 48

Rule 5: Ideal Flow

Server A

{a:bar}

Server B

{a:bar}

Primary: A

Backup: B

Primary: A

Backup: null

VS

Ideally, right after B dies, Server A completes a state transfer

Primary: A

Backup: C

Server C

{}

Primary: A

Backup: B

StateTransfer((“a” -> “bar”))

Server C

{a:bar}

Primary: A

Backup: C

Primary: A

Backup: C

40 of 48

Rule 5: Ideal Flow

Server A

{a:bar}

Server B

{a:bar}

Primary: A

Backup: C

Primary: A

Backup: null

VS

And send an ack to ViewServer, to indicate state sync between all involved servers in the current view

Primary: A

Backup: C

Server C

{a:bar}

Primary: A

Backup: C

View2 ack

41 of 48

Rule 5: Takeaway

Server A

{a:bar}

Primary: A

Backup: null

VS

So that when views change and C becomes primary, everything remains consistent

Primary: C

Backup: null

Server C

{a:bar}

Server B

{a:bar}

Primary: A

Backup: null

Primary: C

Backup: null

Client

Primary: C

Backup: null

GetResult(bar)

Get(a)

42 of 48

Recap: State Transfer (Subtle details)

Recall that the ViewServer must not transition onto a new view until the current view has been acknowledged by the primary.

During state transfer, primary can just stop sending out pings.
Or primary can continue pinging the ViewServer with old view.

Backup can receive duplicated/late state transfer messages �(i.e. a state transfer message is duplicated/come later).

We need to guarantee that state on backup is only overwritten once per view change (A common source of bugs)

What happens if the state transfer ack gets dropped?

Resend state transfer message, but backup should not overwrite their state if they have already the state transfer

43 of 48

Executing Duplicate State Transfer Requests

Primary

Backup

StateTransfer((“a” -> “foo”))

StateTransferAck

“a” -> “foo”

44 of 48

Executing Duplicate State Transfer Requests

Primary

Backup

StateTransfer((“a” -> “foo”))

“a” -> “foobarbaz”

“a” -> “foo”

StateTransferAck

Once backup becomes the next primary, clients could get unexpected results.

Takeaway: Execute a state transfer once per view. The backup should still always respond to a state transfer request acknowledging the request.

45 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)

46 of 48

Rule 6: What if we processed requests during state transfer?

Primary

Backup

StateTransfer((“a” -> “foo”))

“a” -> “foo”

Client 1

Put(“a”, “bar”)

“a” -> “foo”

“a” -> “bar”

StateTransferAck

47 of 48

Rule 6: Takeaway

State transfer will overwrite the state of the new backup so don’t process requests during a state transfer, otherwise the results could be overwritten.
Primary should ignore client requests while in the middle of a state transfer.

48 of 48

Rules:

Primary must wait for backup to accept/execute each op before doing op and replying to client
Backup must accept forwarded requests only if view is correct
Primary in view i+1 must have been backup or primary in view i
Non-primary must reject client requests
ViewServer cannot move on to view i+1 until ack from primary in view i is received
Every operation must be before or after state transfer (Problem with processing requests during a state transfer)