neilconway / overlog-paxos

A clean implementation of the Paxos consensus protocol in Overlog, a language for distributed computing.

commit 29: 7ba2c54468af
parent 28: 8e5f83fc7ce8
branch: default
tags: tip
comments for source and sink
Peter Alvaro
5 months ago
overlog-paxos / src / olg / core / election.olg
    #   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