-
Notifications
You must be signed in to change notification settings - Fork 0
/
preempt_paxos.da
122 lines (96 loc) · 4.26 KB
/
preempt_paxos.da
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
import sys
from random import randint
from numpy.random import choice
import copy
import time
TIMEOUT = 1
class Proposer(process):
def setup(acceptors:set, monitor:Monitor, tp:int, nLossRate:float, nDelay: int, nWaitTime: int):
self.n = None # proposal number
self.majority = acceptors # majority of acceptors; all in other papers
def Loss():
modifiedmajority=set()
majorityList = list(majority)
draw = [int(choice((0,1), 1, p= [nLossRate, 1 - nLossRate], replace= False)) for i in range(len(majority))]
for i,j in enumerate(draw):
if j==1:
modifiedmajority.add(majorityList[i])
return modifiedmajority
def to_consent():
n = (0, self) if n == None else (n[0]+1, self) # pick a prop num
modifiedmajority = Loss()
#send(('prepare', n), to= majority)
delayint = int(nDelay)
delay = randint(0, delayint)
time.sleep(delay)
send(('prepare', n), to= modifiedmajority)
if await(len(setof(a, received(('respond', _n, _), from_ =a)))
> len(acceptors)/2):
#print ("proposal responded")
v = anyof(setof(v, received(('respond', _n, (n2, v))),
n2==max(setof(n2, received(('respond', _n, (n2, _))))))
or {randint(1,100)}) # any value, pick in 1..100
#print("values selected", n, v)
responded = setof(a, received(('respond', _n, _), from_ =a))
send(('accept', n, v), to= responded)
send(('PropsedValue', n, v), to= monitor)
#debug('### chose', n, v)
time.sleep(nWaitTime)
elif (some(received(('preempt', n2)), has= n2 > n)):
return
elif timeout(tp):
#print("failed proposal : ", n)
output('failed proposal number', n)
time.sleep(nWaitTime)
def run():
while not received(('done',)):
to_consent()
#output('terminating')
def anyof(s):
return next(iter(s)) if s else None
class Acceptor(process):
def setup(learners:set, monitor:Monitor, nDelay: int): pass
def receive(msg= ('prepare', n), from_= p):
n2 = anyof(setof(n2, received(('respond', n2, _)), n2 > n))
if each(sent(('respond', n2, _)), has= n > n2):
maxprop = anyof(setof((n, v), sent(('accepted', n, v)),
n==max(setof(n, sent(('accepted', n, _))))))
#print ("Phase 1b : responded with maxprop : ", maxprop, " to : ", n);
#delay = randint(0, nDelay)
#time.sleep(delay)
send(('respond', n, maxprop), to =p)
else:
send(('preempt', n2), to =p)
#print ("PREEMPT Phase 1b : acceptor has already promised to greater value i.e : to : ", n)
def receive(msg= ('accept', n, v)):
if not some(sent(('respond', n2, _)), has= n2 > n):
#print("acceptor decided value : ", n, v)
send(('accepted', n, v), to= learners)
else: pass
#print ("Phase 2b : acceptor has already promised to greater value to ", n)
def run():
await(received(('done',)))
#output('terminating')
def anyof(s):
"""return any element of set s if s is not empty or 'None' otherwise"""
return next(iter(s)) if s else None
class Learner(process):
def setup(acceptors:set, monitor:Monitor, tl:int):pass
def learn():
if await(some(received(('accepted', n, v)),
has= len(setof(a, received(('accepted', _n, _v), from_=a)))
> len(acceptors)/2)):
#output('learned', n, v)
#v1 = randint(1,100)
send(('learned', n, v), to= monitor)
elif timeout(tl):
output('failed learning anything')
def run():
learn()
#output('terminating')
send(('learned', ), to=nodeof(self))
# This is an executable specification of the algorithm described in
# Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News
# (Distributed Computing Column), 32(4):51-58, December.
# This code includes setup and termination for running repeated rounds until
# the learners all terminate after learning the consent value or timeout.