Consensus Algorithms in Paxos
Consensus Algorithms
Administrivia
●
Quiz 2 grades/solutions released
●
HW2 released - due next Thursday!
Paxos
Citation: Google Tech Talks video on Paxos
Paxos
What do we mean by consensus?
●
C
o
n
s
e
n
s
u
s
i
s
o
n
o
n
e
v
a
l
u
e
.
●
C
o
n
s
e
n
s
u
s
i
s
r
e
a
c
h
e
d
o
n
c
e
a
m
a
j
o
r
i
t
y
o
f
p
a
r
t
i
c
i
p
a
n
t
s
a
g
r
e
e
.
●
O
n
c
e
a
c
o
n
s
e
n
s
u
s
i
s
r
e
a
c
h
e
d
,
e
v
e
r
y
o
n
e
c
a
n
e
v
e
n
t
u
a
l
l
y
k
n
o
w
t
h
e
r
e
s
u
l
t
.
●
P
a
r
t
i
c
i
p
a
n
t
s
a
r
e
h
a
p
p
y
t
o
r
e
a
c
h
c
o
n
s
e
n
s
u
s
o
n
a
n
y
r
e
s
u
l
t
,
n
o
t
j
u
s
t
t
h
e
o
n
e
t
h
e
y
p
r
o
p
o
s
e
.
●
C
o
m
m
u
n
i
c
a
t
i
o
n
c
h
a
n
n
e
l
s
a
r
e
n
o
t
p
e
r
f
e
c
t
(
m
e
s
s
a
g
e
s
m
a
y
b
e
l
o
s
t
)
.
Paxos
Alice
Bob
Charlie
Debbie
Erica
“Let’s see Finding Nemo”
“Sure, Finding Nemo is great”
“What about Mission
Impossible”
“Finding Nemooooooooo”
“OK, I guess it’s Finding Nemo”
“Ugh, OK fine”
Paxos
Alice
Bob
Charlie
Debbie
Erica
“Let’s see Finding Nemo”
“Sure, Finding Nemo is great”
“What about Mission
Impossible”
“Finding Nemooooooooo”
“Yes, Finding Nemo!”
“Ugh, OK fine”
Paxos
Paxos defines three different roles for the nodes in the system:
●
Proposers
○
These propose values for consensus.
●
Acceptors
○
These “vote” on proposals and form the majority.
●
Learners
○
These record whatever the acceptors have accepted as the decision.
Decisions must be persistent. Nodes must know how many acceptors there are.
Note: we’re talking about them separately, but in practice any single machine can
play any number of roles simultaneously
Paxos
●
Proposer
picks a proposal ID (ID
p
) and
sends a PREPARE ID
p
message to
Acceptors
○
IDp must be unique (i.e. different
proposers should pick different IDs)
○
Timeout? Pick higher ID
p
●
Proposer
gets PROMISE response from
majority of acceptors. It sends
ACCEPT_REQUEST (ID
p
,
value
) to
Acceptors
.
○
value
can be anything
Proposer
Acceptors
●
Acceptor
receives PREPARE request. Did
it promise to ignore requests with ID
p
?
○
If yes, then ignore request
○
If no, then promise to ignore ID < ID
p
(and
send PROMISE ID
p
in reply)
●
Acceptor
receives ACCEPT_REQUST. Did it
promise to ignore IDp?
○
If yes, then ignore request
○
If no, reply ACCEPT (ID
p
,
value
) and also
send to
Learners
Paxos
●
Proposer
picks a proposal ID (ID
p
) and
sends a PREPARE ID
p
message to
Acceptors
○
IDp must be unique (i.e. different
proposers should pick different IDs)
○
Timeout? Pick higher ID
p
Proposer
Acceptors
●
Acceptor
receives PREPARE request. Did
it promise to ignore requests with ID
p
?
○
If yes, then ignore request
○
If no, then promise to ignore ID < ID
p
(and
send PROMISE ID
p
in reply)
Reminder: ‘nemo’ is already consensus
●
Proposer
gets PROMISE response from
majority of acceptors. It sends
ACCEPT_REQUEST (ID
p
,
value
) to
Acceptors
.
○
value
can be anything
●
Acceptor
receives ACCEPT_REQUST. Did it
promise to ignore IDp?
○
If yes, then ignore request
○
If no, reply ACCEPT (ID
p
,
value
) and also
send to
Learners
Paxos
●
Proposer
picks a proposal ID (ID
p
) and
sends a PREPARE ID
p
message to
Acceptors
○
IDp must be unique (i.e. different
proposers should pick different IDs)
○
Timeout? Pick higher ID
p
Proposer
Acceptors
●
Acceptor
receives PREPARE request. Did it
promise to ignore requests with ID
p
?
○
If yes, then ignore request
○
If no, then promise to ignore ID < ID
p
. Did we already
ACCEPT something?
■
If yes, send PROMISE ID
p
, ACCEPTED
value
■
If no, send PROMISE ID
p
Reminder: ‘nemo’ is already consensus
●
Proposer
gets PROMISE response from
majority of acceptors. It sends
ACCEPT_REQUEST (ID
p
,
value
) to
Acceptors
.
○
value
can be anything
●
Acceptor
receives ACCEPT_REQUST. Did it
promise to ignore IDp?
○
If yes, then ignore request
○
If no, reply ACCEPT (ID
p
,
value
) and also
send to
Learners
Paxos
●
Proposer
picks a proposal ID (ID
p
) and
sends a PREPARE ID
p
message to
Acceptors
○
IDp must be unique (i.e. different
proposers should pick different IDs)
○
Timeout? Pick higher ID
p
Proposer
Acceptors
●
Acceptor
receives PREPARE request. Did it
promise to ignore requests with ID
p
?
○
If yes, then ignore request
○
If no, then promise to ignore ID < ID
p
. Did we already
ACCEPT something?
■
If yes, send PROMISE ID
p
, ACCEPTED
value
■
If no, send PROMISE ID
p
Reminder: ‘nemo’ is already consensus
●
Proposer
gets PROMISE response from
majority of acceptors. It sends
ACCEPT_REQUEST (ID
p
,
value
) to
Acceptors
. Did PROMISES come with
values
?
○
If yes,
Proposer
must use
value
with highest
ID
p
.
○
If no,
value
can be anything
●
Acceptor
receives ACCEPT_REQUST. Did it
promise to ignore IDp?
○
If yes, then ignore request
○
If no, reply ACCEPT (ID
p
,
value
) and also
send to
Learners
Paxos
PREPARE 5
PROMISE 5
PROMISE 5
PREPARE 2
(ignored)
(ignored)
ACCEPT-REQUEST (5, ‘nemo’)
PROMISE 2
Paxos: Distributed Storage
Server 1
Server 2
Server 3
Paxos: Distributed Storage
Server 1
Server 2
Server 3
+$200 = $270
+$200 = $270
Log ID 3
+$1000 = $1070
Paxos: Distributed Storage
Server 1
Server 2
Server 3
+$200 = $270
+$200 = $270
Log ID 3
+$200 = $270
+$1000 = $1070
Paxos: Distributed Storage
Server 1
Server 2
Server 3
+$200 = $270
+$200 = $270
Log ID 3
+$200 = $270
-$40 = $230
Paxos: Distributed Storage
Server 1
Server 2
Server 3
+$200 = $270
+$200 = $270
Log ID 3
+$200 = $270
-$40 = $230
+$1000 = $1070
Log ID 5
+$1000 = $1070
+$1000 = $1070
Paxos: Master Election
Paxos
PREPARE 5
PROMISE 5
PROMISE 5
PREPARE 7
PROMISE 7
PROMISE 7
ACCEPT-REQUEST (5, ‘nemo’)
(ignored)
(ignored)
PREPARE 9
PROMISE 9
PROMISE 9
ACCEPT-REQUEST (7, ‘star wars’)
(ignored)
(ignored)
PREPARE
11
PROMISE 11
PROMISE 11
Digression: Contention
●
Contention is a general issue in concurrent algorithms.
○
Race conditions
○
Deadlock
○
Livelock
●
Concurrency is HARD!
Digression: Contention (Race Condition)
●
What happens if two machines run this code at once?
def incrementSharedValue(value_server):
x = value_server.get_value()
y = x + 1
value_server.set_value(y)
Digression: Contention (Race Condition)
●
What happens if two machines run this code at once?
def incrementSharedValue(value_server):
value_server.lock()
x = value_server.get_value()
y = x + 1
value_server.set_value(y)
value_server.unlock()
Digression: Contention (Deadlock)
●
What happens if two machines are calling these functions?
def incrementSharedValue(s1, s2):
s1.lock()
s2.lock()
x = s1.get_value() + 1
y = s2.get_value() + 1
s1.set_value(x)
s2.set_value(y)
s2.unlock()
s1.unlock()
def incrementSharedValue(s1, s2):
s2.lock()
s1.lock()
x = s1.get_value() + 1
y = s2.get_value() + 1
s1.set_value(x)
s2.set_value(y)
s1.unlock()
s2.unlock()
Digression: Contention (Livelock)
●
Sort of like deadlock, but state is changing
○
Paxos example from earlier
○
Two people walking toward each other in a hallway
●
Possible solutions
○
Exponential backoff
○
Backoff fuzzing
●
Both of those solutions are generally good practice for request retries
Consensus algorithms play a vital role in distributed systems like Paxos. Paxos is a protocol that aims to achieve consensus among a majority of participants. It defines roles for nodes like proposers, acceptors, and learners, each serving a specific purpose in reaching agreement on a single value. The process involves proposals, voting, and recording decisions persistently. Communication channels may not be perfect, but with the right mechanisms in place, consensus can be achieved effectively. The protocol ensures that decisions are made collectively and known by all participants.
Uploaded on Sep 22, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Administrivia Quiz 2 grades/solutions released HW2 released - due next Thursday!
Paxos Citation: Google Tech Talks video on Paxos
Paxos What do we mean by consensus? Consensus is on one value. Consensus is reached once a majority of participants agree. Once a consensus is reached, everyone can eventually know the result. Participants are happy to reach consensus on any result, not just the one they propose. Communication channels are not perfect (messages may be lost).
Paxos Sure, Finding Nemo is great What about Mission Impossible Ugh, OK fine Bob Charlie Finding Nemooooooooo Let s see Finding Nemo Alice Debbie Erica OK, I guess it s Finding Nemo
Paxos Sure, Finding Nemo is great What about Mission Impossible Ugh, OK fine Bob Charlie Finding Nemooooooooo Let s see Finding Nemo Alice Debbie Fred Erica Yes, Finding Nemo!
Paxos Paxos defines three different roles for the nodes in the system: Proposers Acceptors Learners These propose values for consensus. These vote on proposals and form the majority. These record whatever the acceptors have accepted as the decision. Decisions must be persistent. Nodes must know how many acceptors there are. Note: we re talking about them separately, but in practice any single machine can play any number of roles simultaneously
Paxos ACCEPT-REQUEST (5, nemo ) PREPARE 5 Proposer Acceptors ACCEPT (5, nemo ) PROMISE 5 Learners Proposer picks a proposal ID (IDp) and sends a PREPARE IDpmessage to Acceptors IDp must be unique (i.e. different proposers should pick different IDs) Timeout? Pick higher IDp Acceptor receives PREPARE request. Did it promise to ignore requests with IDp? If yes, then ignore request If no, then promise to ignore ID < IDp(and send PROMISE IDpin reply) Proposer gets PROMISE response from majority of acceptors. It sends ACCEPT_REQUEST (IDp, value) to Acceptors. value can be anything Acceptor receives ACCEPT_REQUST. Did it promise to ignore IDp? If yes, then ignore request If no, reply ACCEPT (IDp, value) and also send to Learners
Paxos PREPARE 3 PREPARE 6 Proposer Acceptors Reminder: nemo is already consensus Proposer picks a proposal ID (IDp) and sends a PREPARE IDpmessage to Acceptors IDp must be unique (i.e. different proposers should pick different IDs) Timeout? Pick higher IDp Acceptor receives PREPARE request. Did it promise to ignore requests with IDp? If yes, then ignore request If no, then promise to ignore ID < IDp(and send PROMISE IDpin reply) Proposer gets PROMISE response from majority of acceptors. It sends ACCEPT_REQUEST (IDp, value) to Acceptors. value can be anything Acceptor receives ACCEPT_REQUST. Did it promise to ignore IDp? If yes, then ignore request If no, reply ACCEPT (IDp, value) and also send to Learners
Paxos PREPARE 3 PREPARE 6 Proposer Acceptors PROMISE 6, ACCEPTED nemo Reminder: nemo is already consensus Proposer picks a proposal ID (IDp) and sends a PREPARE IDpmessage to Acceptors IDp must be unique (i.e. different proposers should pick different IDs) Timeout? Pick higher IDp Acceptor receives PREPARE request. Did it promise to ignore requests with IDp? If yes, then ignore request If no, then promise to ignore ID < IDp. Did we already ACCEPT something? If yes, send PROMISE IDp, ACCEPTED value If no, send PROMISE IDp Proposer gets PROMISE response from majority of acceptors. It sends ACCEPT_REQUEST (IDp, value) to Acceptors. value can be anything Acceptor receives ACCEPT_REQUST. Did it promise to ignore IDp? If yes, then ignore request If no, reply ACCEPT (IDp, value) and also send to Learners
Paxos ACCEPT-REQUEST (6, nemo ) PREPARE 3 PREPARE 6 Proposer Acceptors ACCEPT (6, nemo ) PROMISE 6, ACCEPTED nemo Reminder: nemo is already consensus Learners Proposer gets PROMISE response from majority of acceptors. It sends ACCEPT_REQUEST (IDp, value) to Acceptors. Did PROMISES come with values? If yes, Proposer must use value with highest IDp. If no, value can be anything Acceptor receives ACCEPT_REQUST. Did it promise to ignore IDp? If yes, then ignore request If no, reply ACCEPT (IDp, value) and also send to Learners Proposer picks a proposal ID (IDp) and sends a PREPARE IDpmessage to Acceptors IDp must be unique (i.e. different proposers should pick different IDs) Timeout? Pick higher IDp Acceptor receives PREPARE request. Did it promise to ignore requests with IDp? If yes, then ignore request If no, then promise to ignore ID < IDp. Did we already ACCEPT something? If yes, send PROMISE IDp, ACCEPTED value If no, send PROMISE IDp
Paxos PREPARE 5 ACCEPT-REQUEST (5, nemo ) Proposer PREPARE 2 Proposer Acceptor (ignored) PROMISE 5 Acceptor (ignored) PROMISE 5 Acceptor PROMISE 2
Paxos: Distributed Storage +$200 = $270 Log ID 3 -$50 = $70 -$50 = $70 -$50 = $70 Log ID 2 +$20 = $120 +$20 = $120 +$20 = $120 Log ID 1 $100 $100 $100 Log ID 0 Acceptance Server 1 Server 2 Server 3 Proposal
Paxos: Distributed Storage -$40 = $230 -$40 = $230 Log ID 4 +$200 = $270 +$200 = $270 +$1000 = $1070 Log ID 3 -$50 = $70 -$50 = $70 -$50 = $70 Log ID 2 +$20 = $120 +$20 = $120 +$20 = $120 Log ID 1 $100 $100 $100 Log ID 0 Accepted +$200 = $270 Server 1 Server 2 Server 3 Proposal
Paxos: Distributed Storage -$40 = $230 -$40 = $230 +$1000 = $1070 Log ID 4 +$200 = $270 +$200 = $270 +$200 = $270 Log ID 3 -$50 = $70 -$50 = $70 -$50 = $70 Log ID 2 +$20 = $120 +$20 = $120 +$20 = $120 Log ID 1 $100 $100 $100 Log ID 0 Accepted -$40 = $230 Server 1 Server 2 Server 3 Proposal
Paxos: Distributed Storage Log ID 5 +$1000 = $1070 -$40 = $230 -$40 = $230 -$40 = $230 Log ID 4 +$200 = $270 +$200 = $270 +$200 = $270 Log ID 3 -$50 = $70 -$50 = $70 -$50 = $70 Log ID 2 +$20 = $120 +$20 = $120 +$20 = $120 Log ID 1 $100 $100 $100 Log ID 0 Acceptance Server 1 Server 2 Server 3 Proposal
Paxos: Distributed Storage Log ID 5 +$1000 = $1070 +$1000 = $1070 +$1000 = $1070 -$40 = $230 -$40 = $230 -$40 = $230 Log ID 4 +$200 = $270 +$200 = $270 +$200 = $270 Log ID 3 -$50 = $70 -$50 = $70 -$50 = $70 Log ID 2 +$20 = $120 +$20 = $120 +$20 = $120 Log ID 1 $100 $100 $100 Log ID 0 Server 1 Server 2 Server 3
Paxos: Master Election Peer-to-peer Primary/Secondary
Paxos ACCEPT-REQUEST (5, nemo ) PREPARE 9 PREPARE 5 P ACCEPT-REQUEST (7, star wars ) PREPARE 11 PREPARE 7 P A (ignored) (ignored) PROMISE 7 PROMISE 11 PROMISE 9 PROMISE 5 A PROMISE 7 PROMISE 11 PROMISE 5 (ignored) (ignored) PROMISE 9 A
Digression: Contention Contention is a general issue in concurrent algorithms. Race conditions Deadlock Livelock Concurrency is HARD!
Digression: Contention (Race Condition) What happens if two machines run this code at once? def incrementSharedValue(value_server): x = value_server.get_value() y = x + 1 value_server.set_value(y)
Digression: Contention (Race Condition) What happens if two machines run this code at once? def incrementSharedValue(value_server): value_server.lock() x = value_server.get_value() y = x + 1 value_server.set_value(y) value_server.unlock() This will block if some other machine has the lock, until they release it
Digression: Contention (Deadlock) What happens if two machines are calling these functions? def incrementSharedValue(s1, s2): s1.lock() s2.lock() x = s1.get_value() + 1 y = s2.get_value() + 1 s1.set_value(x) s2.set_value(y) s2.unlock() s1.unlock() def incrementSharedValue(s1, s2): s2.lock() s1.lock() x = s1.get_value() + 1 y = s2.get_value() + 1 s1.set_value(x) s2.set_value(y) s1.unlock() s2.unlock()
Digression: Contention (Livelock) Sort of like deadlock, but state is changing Paxos example from earlier Two people walking toward each other in a hallway Possible solutions Exponential backoff Backoff fuzzing Both of those solutions are generally good practice for request retries
