neilconway / overlog-paxos
A clean implementation of the Paxos consensus protocol in Overlog, a language for distributed computing.
Clone this repository (size: 4.5 MB): HTTPS / SSH
$ hg clone http://bitbucket.org/neilconway/overlog-paxos/
| commit 29: | 7ba2c54468af |
| parent 28: | 8e5f83fc7ce8 |
| branch: | default |
| tags: | tip |
comments for source and sink
5 months ago
| # Introduced |
|---|
1 |
0a66742d2525 |
program leader; |
2 |
0a66742d2525 |
|
3 |
0a66742d2525 |
import java.lang.System; |
4 |
0a66742d2525 |
|
5 |
0a66742d2525 |
define(progress_timer_start, keys(0), {Long}); |
6 |
0a66742d2525 |
progress_timer_start(1000L); |
7 |
0a66742d2525 |
|
8 |
0a66742d2525 |
define(last_installed, keys(0), {String, Integer}); |
9 |
0a66742d2525 |
define(my_start, {String, Integer}); |
10 |
0a66742d2525 |
|
11 |
0a66742d2525 |
timer(seconds, physical, 1000, infinity, 0); |
12 |
0a66742d2525 |
|
13 |
0a66742d2525 |
define(start, keys(0), {String}); |
14 |
0a66742d2525 |
|
15 |
0a66742d2525 |
public |
16 |
0a66742d2525 |
my_start(Me, Id) :- |
17 |
0a66742d2525 |
start(), |
18 |
0a66742d2525 |
paxos::parliament(Me, Him, Id), |
19 |
0a66742d2525 |
Me == Him; |
20 |
0a66742d2525 |
|
21 |
0a66742d2525 |
/*********** progress_timer block **************/ |
22 |
0a66742d2525 |
define(progress_timer, keys(0), {String, Long, Long}); |
23 |
0a66742d2525 |
|
24 |
0a66742d2525 |
public |
25 |
0a66742d2525 |
progress_timer(Me, -1, Duration) :- |
26 |
0a66742d2525 |
my_start(Me, _), |
27 |
0a66742d2525 |
progress_timer_start(Duration); |
28 |
0a66742d2525 |
|
29 |
0a66742d2525 |
progress_timer(Me, Start, NewDuration) :- |
30 |
0a66742d2525 |
preinstall(Me, _), |
31 |
0a66742d2525 |
progress_timer(Me, _, Duration), |
32 |
0a66742d2525 |
Start := System.currentTimeMillis() |
33 |
0a66742d2525 |
{ |
34 |
0a66742d2525 |
NewDuration := Duration * 2; |
35 |
0a66742d2525 |
//System.out.println("\tDouble progress timer to " + NewDuration.toString()); |
36 |
0a66742d2525 |
}; |
37 |
0a66742d2525 |
|
38 |
0a66742d2525 |
progress_timer(Me, Start, StartDur) :- |
39 |
0a66742d2525 |
progress_timer(Me, _, Duration), |
40 |
0a66742d2525 |
progress_timer_start(StartDur), |
41 |
0a66742d2525 |
do_election(Me, _, _), |
42 |
0a66742d2525 |
Start := System.currentTimeMillis(); |
43 |
0a66742d2525 |
/*********** END progress_timer block **************/ |
44 |
0a66742d2525 |
|
45 |
0a66742d2525 |
/*********** do_election block **************/ |
46 |
0a66742d2525 |
define(do_election, {String, Integer, String}); |
47 |
0a66742d2525 |
|
48 |
0a66742d2525 |
public |
49 |
0a66742d2525 |
do_election(Me, Id, Me) :- |
50 |
0a66742d2525 |
my_start(Me, Id); |
51 |
0a66742d2525 |
|
52 |
0a66742d2525 |
/* safety-critical logic is (perhaps inappropriately) |
53 |
0a66742d2525 |
defined here: do_election carries with it the new View number. |
54 |
0a66742d2525 |
*/ |
55 |
0a66742d2525 |
do_election(Me, Id, Me) :- |
56 |
0a66742d2525 |
progress_timer(Me, Start, Duration), |
57 |
0a66742d2525 |
seconds#insert(), |
58 |
0a66742d2525 |
last_attempted(Me, Last), |
59 |
0a66742d2525 |
paxos::priestCnt(Me, Cnt), |
60 |
0a66742d2525 |
Id := Last + Cnt, |
61 |
0a66742d2525 |
Start != -1, |
62 |
0a66742d2525 |
(System.currentTimeMillis() - Start) > Duration; |
63 |
0a66742d2525 |
|
64 |
0a66742d2525 |
|
65 |
0a66742d2525 |
/* if progress timer isn't set, and View > Last */ |
66 |
0a66742d2525 |
do_election(Me, View, Originator) :- |
67 |
0a66742d2525 |
view_change(Me, View, Other, Originator), |
68 |
0a66742d2525 |
last_attempted(Me, Last), |
69 |
0a66742d2525 |
Me != Other, |
70 |
0a66742d2525 |
View > Last; |
71 |
0a66742d2525 |
/* the progress_timer rule doesn't seem to work. relaxing it; may |
72 |
0a66742d2525 |
cause livelock issues |
73 |
0a66742d2525 |
progress_timer(Me, _, StartDuration), |
74 |
0a66742d2525 |
progress_timer_start(StartDuration); |
75 |
0a66742d2525 |
*/ |
76 |
0a66742d2525 |
|
77 |
0a66742d2525 |
|
78 |
0a66742d2525 |
/*********** END do_election block **************/ |
79 |
0a66742d2525 |
|
80 |
0a66742d2525 |
|
81 |
0a66742d2525 |
/*********** last_attempted block **************/ |
82 |
0a66742d2525 |
define(last_attempted, keys(0), {String, Integer}); |
83 |
0a66742d2525 |
|
84 |
0a66742d2525 |
/* define start states! */ |
85 |
0a66742d2525 |
public |
86 |
0a66742d2525 |
last_attempted(Me, Id) :- |
87 |
0a66742d2525 |
my_start(Me, Id); |
88 |
0a66742d2525 |
|
89 |
0a66742d2525 |
// I think that with bug Z out of the way, we can make this jump |
90 |
0a66742d2525 |
last_attempted(Me, Id) :- |
91 |
0a66742d2525 |
do_election(Me, Id, Me2), |
92 |
0a66742d2525 |
last_attempted(Me, OldId), |
93 |
0a66742d2525 |
paxos::priestCnt(Me, Cnt), |
94 |
0a66742d2525 |
Me == Me2, |
95 |
0a66742d2525 |
OldId < Id |
96 |
0a66742d2525 |
{ |
97 |
0a66742d2525 |
New := OldId + Cnt; |
98 |
0a66742d2525 |
//System.out.println(Me.toString() + " = " + Me2.toString() + " -- OUCH: " + OldId.toString() + " to "+ New.toString()); |
99 |
0a66742d2525 |
}; |
100 |
0a66742d2525 |
|
101 |
0a66742d2525 |
/*********** END last_attempted block **************/ |
102 |
0a66742d2525 |
|
103 |
0a66742d2525 |
|
104 |
0a66742d2525 |
/*********** view_change block **************/ |
105 |
0a66742d2525 |
define(view_change, keys(0, 1, 2), {String, Integer, String, String}); |
106 |
0a66742d2525 |
view_change(@Other, Id, Me, Originator) :- |
107 |
0a66742d2525 |
do_election(@Me, Id, Originator), |
108 |
0a66742d2525 |
paxos::parliament(@Me, Other, _); |
109 |
0a66742d2525 |
|
110 |
0a66742d2525 |
|
111 |
0a66742d2525 |
define(vc_cnt, keys(0, 1), {String, Integer, Integer}); |
112 |
0a66742d2525 |
vc_cnt(Me, View, count<Other>) :- |
113 |
0a66742d2525 |
view_change(Me, View, Other, _); |
114 |
0a66742d2525 |
|
115 |
0a66742d2525 |
delete |
116 |
0a66742d2525 |
view_change(Me, Id, Other, Orig) :- |
117 |
0a66742d2525 |
view_change(Me, Id, Other, Orig), |
118 |
0a66742d2525 |
vc_proof(Me, Id, Other2); |
119 |
0a66742d2525 |
|
120 |
0a66742d2525 |
/*********** END view_change block **************/ |
121 |
0a66742d2525 |
define(preinstall, {String, Integer}); |
122 |
0a66742d2525 |
preinstall(Me, View) :- |
123 |
0a66742d2525 |
vc_cnt(Me, View, Cnt), |
124 |
0a66742d2525 |
paxos::priestCnt(Me, Total), |
125 |
0a66742d2525 |
Cnt > (Total / 2); |
126 |
0a66742d2525 |
|
127 |
0a66742d2525 |
// paa hack |
128 |
0a66742d2525 |
define(leader, keys(0, 1), {String, String, Integer}); |
129 |
0a66742d2525 |
leader(Me, Originator, View) :- |
130 |
0a66742d2525 |
preinstall(Me, View), |
131 |
0a66742d2525 |
view_change(Me, View, _, Originator); |
132 |
0a66742d2525 |
|
133 |
0a66742d2525 |
delete |
134 |
0a66742d2525 |
leader(Me, Leader, View) :- |
135 |
0a66742d2525 |
leader(Me, Leader, View), |
136 |
0a66742d2525 |
bump_vc_proof(Me, NV), |
137 |
0a66742d2525 |
NV > View; |
138 |
0a66742d2525 |
|
139 |
0a66742d2525 |
public |
140 |
0a66742d2525 |
last_installed(Me, -1) :- |
141 |
0a66742d2525 |
my_start(Me, _); |
142 |
0a66742d2525 |
|
143 |
0a66742d2525 |
last_installed(Me, View) :- |
144 |
0a66742d2525 |
last_installed(Me, OldView), |
145 |
0a66742d2525 |
leader#insert(Me, _, View), |
146 |
0a66742d2525 |
View >= OldView; |
147 |
0a66742d2525 |
|
148 |
0a66742d2525 |
/** PROOF MESSAGE STUFF ***/ |
149 |
0a66742d2525 |
timer(proof_timer, physical, 2000, infinity, 0); |
150 |
0a66742d2525 |
define(proof_doping, {String, Integer, String}); |
151 |
0a66742d2525 |
|
152 |
0a66742d2525 |
proof_doping(Me, View, Other) :- |
153 |
0a66742d2525 |
proof_timer#insert(), |
154 |
0a66742d2525 |
paxos::parliament(Me, Other), |
155 |
0a66742d2525 |
last_installed(Me, View); |
156 |
0a66742d2525 |
|
157 |
0a66742d2525 |
define(vc_proof, {String, Integer, String}); |
158 |
0a66742d2525 |
vc_proof(@Other, View, Me) :- |
159 |
0a66742d2525 |
proof_doping(@Me, View, Other); |
160 |
0a66742d2525 |
|
161 |
0a66742d2525 |
define(bump_vc_proof, {String, Integer}); |
162 |
0a66742d2525 |
bump_vc_proof(Me, View) :- |
163 |
0a66742d2525 |
vc_proof(Me, View, Other), |
164 |
0a66742d2525 |
last_installed(Me, LastI), |
165 |
0a66742d2525 |
View > LastI; |
166 |
0a66742d2525 |
|
167 |
0a66742d2525 |
bump_vc_proof(Me, View) :- |
168 |
0a66742d2525 |
vc_proof(Me, View, Other), |
169 |
0a66742d2525 |
notin last_installed(Me, _); |
170 |
0a66742d2525 |
