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
4 months ago
| r29:7ba2c54468af | 170 loc | 4.3 KB | embed / history / annotate / raw / |
|---|
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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 | program leader;
import java.lang.System;
define(progress_timer_start, keys(0), {Long});
progress_timer_start(1000L);
define(last_installed, keys(0), {String, Integer});
define(my_start, {String, Integer});
timer(seconds, physical, 1000, infinity, 0);
define(start, keys(0), {String});
public
my_start(Me, Id) :-
start(),
paxos::parliament(Me, Him, Id),
Me == Him;
/*********** progress_timer block **************/
define(progress_timer, keys(0), {String, Long, Long});
public
progress_timer(Me, -1, Duration) :-
my_start(Me, _),
progress_timer_start(Duration);
progress_timer(Me, Start, NewDuration) :-
preinstall(Me, _),
progress_timer(Me, _, Duration),
Start := System.currentTimeMillis()
{
NewDuration := Duration * 2;
//System.out.println("\tDouble progress timer to " + NewDuration.toString());
};
progress_timer(Me, Start, StartDur) :-
progress_timer(Me, _, Duration),
progress_timer_start(StartDur),
do_election(Me, _, _),
Start := System.currentTimeMillis();
/*********** END progress_timer block **************/
/*********** do_election block **************/
define(do_election, {String, Integer, String});
public
do_election(Me, Id, Me) :-
my_start(Me, Id);
/* safety-critical logic is (perhaps inappropriately)
defined here: do_election carries with it the new View number.
*/
do_election(Me, Id, Me) :-
progress_timer(Me, Start, Duration),
seconds#insert(),
last_attempted(Me, Last),
paxos::priestCnt(Me, Cnt),
Id := Last + Cnt,
Start != -1,
(System.currentTimeMillis() - Start) > Duration;
/* if progress timer isn't set, and View > Last */
do_election(Me, View, Originator) :-
view_change(Me, View, Other, Originator),
last_attempted(Me, Last),
Me != Other,
View > Last;
/* the progress_timer rule doesn't seem to work. relaxing it; may
cause livelock issues
progress_timer(Me, _, StartDuration),
progress_timer_start(StartDuration);
*/
/*********** END do_election block **************/
/*********** last_attempted block **************/
define(last_attempted, keys(0), {String, Integer});
/* define start states! */
public
last_attempted(Me, Id) :-
my_start(Me, Id);
// I think that with bug Z out of the way, we can make this jump
last_attempted(Me, Id) :-
do_election(Me, Id, Me2),
last_attempted(Me, OldId),
paxos::priestCnt(Me, Cnt),
Me == Me2,
OldId < Id
{
New := OldId + Cnt;
//System.out.println(Me.toString() + " = " + Me2.toString() + " -- OUCH: " + OldId.toString() + " to "+ New.toString());
};
/*********** END last_attempted block **************/
/*********** view_change block **************/
define(view_change, keys(0, 1, 2), {String, Integer, String, String});
view_change(@Other, Id, Me, Originator) :-
do_election(@Me, Id, Originator),
paxos::parliament(@Me, Other, _);
define(vc_cnt, keys(0, 1), {String, Integer, Integer});
vc_cnt(Me, View, count<Other>) :-
view_change(Me, View, Other, _);
delete
view_change(Me, Id, Other, Orig) :-
view_change(Me, Id, Other, Orig),
vc_proof(Me, Id, Other2);
/*********** END view_change block **************/
define(preinstall, {String, Integer});
preinstall(Me, View) :-
vc_cnt(Me, View, Cnt),
paxos::priestCnt(Me, Total),
Cnt > (Total / 2);
// paa hack
define(leader, keys(0, 1), {String, String, Integer});
leader(Me, Originator, View) :-
preinstall(Me, View),
view_change(Me, View, _, Originator);
delete
leader(Me, Leader, View) :-
leader(Me, Leader, View),
bump_vc_proof(Me, NV),
NV > View;
public
last_installed(Me, -1) :-
my_start(Me, _);
last_installed(Me, View) :-
last_installed(Me, OldView),
leader#insert(Me, _, View),
View >= OldView;
/** PROOF MESSAGE STUFF ***/
timer(proof_timer, physical, 2000, infinity, 0);
define(proof_doping, {String, Integer, String});
proof_doping(Me, View, Other) :-
proof_timer#insert(),
paxos::parliament(Me, Other),
last_installed(Me, View);
define(vc_proof, {String, Integer, String});
vc_proof(@Other, View, Me) :-
proof_doping(@Me, View, Other);
define(bump_vc_proof, {String, Integer});
bump_vc_proof(Me, View) :-
vc_proof(Me, View, Other),
last_installed(Me, LastI),
View > LastI;
bump_vc_proof(Me, View) :-
vc_proof(Me, View, Other),
notin last_installed(Me, _);
|
