Implementing Replicated Logs With Paxos: John Ousterhout and Diego Ongaro Stanford University
Implementing Replicated Logs With Paxos: John Ousterhout and Diego Ongaro Stanford University
Implementing Replicated Logs With Paxos: John Ousterhout and Diego Ongaro Stanford University
with Paxos
Note: this material borrows heavily from slides by Lorenzo Alvisi, Ali Ghodsi, and David Mazières
Goal: Replicated Log
Clients
shl
Consensus State Consensus State Consensus State
Module Machine Module Machine Module Machine
Servers
Log Log Log
add jmp mov shl add jmp mov shl add jmp mov shl
accept?(red) accepted(red)
s1
accepted(red)
s2
accept?(blue) accepted(blue)
s3
accepted(blue)
s4
accept?(green) accepted(green)
s5
time
Red Chosen??
accept?(red) accepted(red)
s1
accepted(red)
s2
accepted(blue) accepted(red)
s3
accepted(blue)
s4
accepted(blue)
s5
prop(blue) time
Blue Chosen
X s1 P 3.1 A 3.1 X
s2 P 3.1 A 3.1 X
s4 P 4.5 A 4.5 X
Y s5 P 4.5 A 4.5 X
time
“Prepare proposal 3.1 (from s1)”
March 1, 2013 Implementing Replicated Logs with Paxos Slide 13
Basic Paxos Examples, cont’d
Three possibilities when later proposal prepares:
2. Previous value not chosen, but new proposer sees it:
New proposer will use existing value
Both proposers can succeed
X s1 P 3.1 A 3.1 X
s2 P 3.1 A 3.1 X
s4 P 4.5 A 4.5 X
Y s5 P 4.5 A 4.5 X
time
X s1 P 3.1 A 3.1 X
s2 P 3.1 A 3.1 X
s4 P 4.5 A 4.5 Y
Y s5 P 4.5 A 4.5 Y
time
s1 mov add cmp ret s1 mov add cmp sub jmp ret
s2 mov add sub ret s2 mov add cmp sub jmp ret
s3 mov add cmp cmp ret s3 mov add cmp shl ret
Solution:
1. Pick a leader
At any given time, only one server acts as Proposer
● Safety requirement:
During configuration changes, it must not be possible for
different majorities to choose different values for the same log
entry:
New Configuration
Old Configuration