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 11: | e0e2ae1e4582 |
| parent 10: | e2653b46ca8c |
| branch: | default |
Code cleanup.
Neil Conway
8 months ago
Changed (Δ84 bytes):
raw changeset »
src/olg/election.olg (5 lines added, 9 lines removed)
src/olg/prepare.olg (1 lines added, 1 lines removed)
src/olg/propose.olg (16 lines added, 17 lines removed)
Up to file-list src/olg/election.olg:
| … | … | @@ -9,8 +9,6 @@ progress_timer_start(2000L); |
9 |
9 |
define(last_installed, keys(0), {String, Integer}); |
10 |
10 |
define(my_start, {String, Integer}); |
11 |
11 |
|
12 |
||
13 |
//timer(start, logical, 1, 1, 0); |
|
14 |
12 |
timer(seconds, physical, 1000, infinity, 0); |
15 |
13 |
|
16 |
14 |
define(start, keys(0), {String}); |
| … | … | @@ -30,14 +28,14 @@ progress_timer(Me, -1, Duration) :- |
30 |
28 |
progress_timer_start(Duration); |
31 |
29 |
|
32 |
30 |
progress_timer(Me, Start, Dur) :- |
33 |
preinstall(Me, |
|
31 |
preinstall(Me, _), |
|
34 |
32 |
progress_timer(Me, _, Duration), |
35 |
33 |
Dur := Duration * 2, |
36 |
34 |
Start := System.currentTimeMillis(); |
37 |
35 |
|
38 |
36 |
progress_timer(Me, Start, Dur) :- |
39 |
37 |
progress_timer(Me, _, Dur), |
40 |
do_election(Me, _, |
|
38 |
do_election(Me, _, _), |
|
41 |
39 |
Start := System.currentTimeMillis(); |
42 |
40 |
/*********** END progress_timer block **************/ |
43 |
41 |
|
| … | … | @@ -62,14 +60,12 @@ do_election(Me, Id, Me) :- |
62 |
60 |
do_election(Me, View, Other) :- |
63 |
61 |
view_change(Me, View, Other), |
64 |
62 |
last_attempted(Me, Last), |
65 |
View > Last |
|
63 |
View > Last; |
|
66 |
64 |
/* the progress_timer rule doesn't seem to work. relaxing it; may |
67 |
65 |
cause livelock issues |
68 |
66 |
*/ |
69 |
67 |
//progress_timer(Me, _, StartDuration), |
70 |
68 |
//progress_timer_start(StartDuration); |
71 |
true; |
|
72 |
||
73 |
69 |
|
74 |
70 |
|
75 |
71 |
/*********** END do_election block **************/ |
| … | … | @@ -104,13 +100,13 @@ last_attempted(Me, View) :- |
104 |
100 |
|
105 |
101 |
|
106 |
102 |
/*********** view_change block **************/ |
107 |
define(view_change, keys(0, |
|
103 |
define(view_change, keys(0, 1, 2), {String, Integer, String, String}); |
|
108 |
104 |
view_change(@Other, Id, Me, Originator) :- |
109 |
105 |
do_election(@Me, Id, Originator), |
110 |
106 |
paxos::parliament(@Me, Other, _); |
111 |
107 |
|
112 |
108 |
|
113 |
define(vc_cnt, keys(0, |
|
109 |
define(vc_cnt, keys(0, 1), {String, Integer, Integer}); |
|
114 |
110 |
vc_cnt(Me, View, count<Other>) :- |
115 |
111 |
view_change(Me, View, Other, _); |
116 |
112 |
Up to file-list src/olg/prepare.olg:
| … | … | @@ -131,7 +131,7 @@ quorum(Master, View) :- |
131 |
131 |
|
132 |
132 |
|
133 |
133 |
// agent, master, view, seqno, update |
134 |
define(accept, keys(0, |
|
134 |
define(accept, keys(0, 1), {String, String, Integer, Integer, String}); |
|
135 |
135 |
|
136 |
136 |
define(global_history, keys(0, 1), {String, Integer, String, String}); |
137 |
137 |
global_history(Agent, SeqNo, Requestor, Update) :- |
Up to file-list src/olg/propose.olg:
| … | … | @@ -6,12 +6,13 @@ import java.lang.System; |
6 |
6 |
define(max_proposal, keys(0, 1), {String, Integer, Integer}); |
7 |
7 |
public |
8 |
8 |
max_proposal(Master, SeqNo, max<View>) :- |
9 |
paxos_stub::prepare_oklist(Master, View, SeqNo, Update, Type, Len, Agent), |
|
10 |
Type == "Proposed"; |
|
9 |
paxos_stub::prepare_oklist(Master, View, SeqNo, _, "Proposed", _, _); |
|
11 |
10 |
|
12 |
11 |
|
13 |
12 |
/******** send_propose block *********************/ |
14 |
13 |
define(send_propose, keys(0, 1, 2), {String, String, Integer, Integer, String, String}); |
14 |
||
15 |
// Constrained update |
|
15 |
16 |
public |
16 |
17 |
send_propose(@Agent, Master, MyView, Aru, Update, "r1") :- |
17 |
18 |
paxos::parliament(@Master, Agent), |
| … | … | @@ -26,19 +27,19 @@ send_propose(@Agent, Master, MyView, Aru |
26 |
27 |
// down to a duty cycle event, we trigger on local_aru#insert and see BOTH the old and new values. |
27 |
28 |
timer(t, physical, 1000, infinity, 0); |
28 |
29 |
define(dope, {String}); |
29 |
dope(M) :- |
|
30 |
paxos::parliament(M, A, _), |
|
31 |
M == A, |
|
30 |
dope(Me) :- |
|
31 |
paxos::self(Me), |
|
32 |
32 |
t#insert(); |
33 |
33 |
|
34 |
send_propose(@Agent, Master, MyView, Aru, Update, Name) :- |
|
34 |
// Unconstrained update |
|
35 |
send_propose(@Agent, Master, View, Aru, Update, Name) :- |
|
35 |
36 |
dope#insert(@Master), |
36 |
37 |
paxos::parliament(@Master, Agent), |
37 |
notin paxos_stub::prepare_oklist(@Master, _, SeqNo, _, "Proposed", _, _), |
|
38 |
paxos_stub::quorum(@Master, MyView), |
|
39 |
|
|
38 |
notin paxos_stub::prepare_oklist(@Master, View, _, _, "Proposed", _, _), |
|
39 |
paxos_stub::quorum(@Master, View), |
|
40 |
leader::last_installed(@Master, View), |
|
40 |
41 |
paxos_stub::local_aru(@Master, Aru), |
41 |
q(@Master, Update, |
|
42 |
q(@Master, Update, _, Id), |
|
42 |
43 |
top_q(@Master, Id) |
43 |
44 |
{ |
44 |
45 |
Name := "r2 " + Id.toString(); |
| … | … | @@ -66,15 +67,15 @@ q(Me, Update, Sender, Id) :- |
66 |
67 |
/********* accept block **************/ |
67 |
68 |
public |
68 |
69 |
paxos_stub::accept(@Other, Agent, View, SeqNo, Update) :- |
69 |
send_propose(@Agent, Master, View, SeqNo, Update), |
|
70 |
notin paxos_stub::global_history(@Agent, SeqNo, Requestor, Update), |
|
70 |
send_propose(@Agent, _, View, SeqNo, Update), |
|
71 |
notin paxos_stub::global_history(@Agent, SeqNo, _, Update), |
|
71 |
72 |
paxos::parliament(@Agent, Other, _); |
72 |
73 |
|
73 |
74 |
public |
74 |
75 |
delete |
75 |
76 |
paxos_stub::accept(Agent, Master, View, SeqNo, Update) :- |
76 |
77 |
paxos_stub::accept(Agent, Master, View, SeqNo, Update), |
77 |
paxos_stub::accept(Agent, |
|
78 |
paxos_stub::accept(Agent, _, View2, SeqNo, _), |
|
78 |
79 |
View2 > View; |
79 |
80 |
|
80 |
81 |
|
| … | … | @@ -95,7 +96,7 @@ globally_ordered(Me, View, SeqNo, Update |
95 |
96 |
/* actions taken on tables defined in earlier programs: */ |
96 |
97 |
|
97 |
98 |
leader::progress_timer(Me, Start, Duration) :- |
98 |
leader::progress_timer(Me, |
|
99 |
leader::progress_timer(Me, _, Duration), |
|
99 |
100 |
Start := System.currentTimeMillis(); |
100 |
101 |
|
101 |
102 |
public |
| … | … | @@ -108,11 +109,9 @@ paxos_stub::global_history(Agent, SeqNo, |
108 |
109 |
globally_ordered(Agent, View, SeqNo, Update), |
109 |
110 |
Requestor := "?"; |
110 |
111 |
|
112 |
// XXX: fix this |
|
111 |
113 |
public |
112 |
114 |
delete |
113 |
115 |
paxos_stub::prepare_oklist(Master, View, SeqNo, Update, Type, Len, Agent) :- |
114 |
116 |
paxos_stub::prepare_oklist(Master, View, SeqNo, Update, Type, Len, Agent), |
115 |
117 |
globally_ordered(Master, GView, GSeqNo, Update); |
116 |
||
117 |
||
118 |