-
Notifications
You must be signed in to change notification settings - Fork 0
/
Paxos
109 lines (94 loc) · 4.21 KB
/
Paxos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#This document contains notes about Paxos protocol
Paxos is an algorithm for achieving a "consensus" in distributed systems.
Assumptions:
Network:
* Network is asynchronous (i.e. msg losses and delays)
* Msgs can be lost/duplicated but no corruption (i.e. TCP)
Processes:
* Processes can crash
* Processes are non-byzantine (only crash-stop)
* Processes have permanent stop
* Processes can propose values
Goal:
Every process agrees on a value from the set of proposed values
Requirements:
* Protocol should work under process failures and message delays/losses
* Consensus is reached via a majority
Roles of a process (aka PAL):
1) Proposer:
processes which proposes values
2) Acceptor:
processes that accepts values. Accept meaning it is "considering" that value.
Majority acceptance = value chosen
3) Learner
processes that learns the outcome (i.e. chosen value)
Protocol Overview:
* Proposal -> P(N,V)
where N-> Proposal number. This should be strictly increasing and glabally unique across all proposers. i.e. NO TIE
e.g. of N- > 3.1, 3.2,3.3 for process with pid 3
* PHASES (AKA PPL):
Prepare:
Proposer prepares what to propose. For this it will first learn previously-accepted proposals from acceptots
Propose:
After preparation, proposer sends out the proposal
Learn:
Learners learn the outcome
PHASE 1-> PREPARE
step 1: Proposer chooses a proposal number "N" and sends a "prepare" request to acceptors. This is a question to acceptors "have you accepted any proposal yet"
Acceptors keeps a cache of all the proposals it has received.
step 2: On receiving this "prepare" request from Proposors, an acceptor will:
a) Will no longer accept any proposal with proposal number < N
b) If it has accepted anything, than it will respond back with the accepted value with the highest proposal number less than N
For instance
step 1: P0(5) -> to the acceptors A0 and A1
step 2: A0 -> Highest acceptance (4, 10)
A1 -> Highest acceptance (2, 20)
A0 -(sends)-> (4, 10) to P0
A1 -(sends)-> (2, 20) to P0
PHASE 2-> PROPOSE (lets get naughty):
If proposer accepts replies from majority of acceptors, it sends an accept request for proposal P(N,V) where
N-> Highest proposal number received in replies from Acceptos.
V-> Value corresponding to "N"
If no replies or no accepted values was returned in phase1, proposer sends out an "accept" request for the new proposal P(N,V)
Acceptors can either
*Accept this proposal
*Reject this proposal: This in case if acceptor has received an another "prepare" request with "N'"> "N"
PHASE 3: LEARN:
Learner gets to know the chosen value. Ways to do this:
a) Each acceptor notifies the learner when it accepts a proposal:
Learners will know if majority has accepted a proposal
Costly (more messages)
b) Elect a "Distinguished Leaner (DL)":
Acceptors sends their accepted values to this DL process
DL than notifies other learners
Drawback: SPOF
c) Elect a set of DL's.
Problematic Scenarios:
step1: P0 -send Prepare(4)-> A0 and A1
step2: A0 -Replies (3, 10)-> P0
A1 -Replies (2, 20)-> P0
A0 and A1 sets the highest N to 4
P0 on receiving the replies, sets the value as (4,10)
step3: P1 -sends Prepare(5)-> A0 and A1
step4: A0 -Replies (3, 10)-> P1
A1 -Replies (2, 20)-> P1
A0 and A1 sets the highest N to 5
P1 on receiving the replies, sets the N,V as (5,10)
step5: P0 performs PHASE2 and proposes P(4,10)
P0 -Propose(4,10)-> A0
P0 -Propose(4,10)-> A1
step6: A0 and A1 "rejects" this proposal as highest N is set to "5" from step 4
step7: P0 performs PHASE1 again and sends "prepare" request" with N=6
step8: A0 and A1 replies with (3,10) and (2,20)
A0 and A1 sets the highest N to be "6"
step9: P1 performs PHASE2 and proposes (5,10)
step10: A0 and A1 "rejects" this proposal of P1 as highest N is set to "6" from step step8.
And this can go on forever.
This is a potential race condition and threatens the "Liveness" guarantee.
Solution:
Elect a "Distinguished Proposer (DP)" i.e. have only one proposer at a time
References:
http://mesos.apache.org/documentation/latest/replicated-log-internals/#use-cases
https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf
http://uchicago-cs.github.io/cmsc23310/pa.html
https://ramcloud.stanford.edu/~ongaro/userstudy/