1 from distalgs import *
2
3
4
5 -class LCR(Synchronous_Algorithm):
6 """The LeLann, Chang and Roberts algorithm for Leader Election in a Synchronous Ring Network
7
8 Each Process sends its identifier around the ring.
9 When a Process receives an incoming identifier, it compares that identifier to its own.
10 If the incoming identifier is greater than its own, it keeps passing the identifier;
11 if it is less than its own, it discards the incoming identifier;
12 if it is equal to its own, the Process declares itself the leader.
13
14 Requires:
15 - Every process knows state['n'], the size of the network
16 Effects:
17 - Every process has state['status'] is 'leader' or 'non-leader'.
18 - Exactly one process has state['status'] is 'leader'
19 """
21 if not self.has(p, "send"):
22 self.set(p, 'send', Message(self, p.UID))
23
24 msg = self.get(p, "send")
25 if msg is None:
26 return
27 self.set(p,"send", None)
28 p.send_msg(msg, p.out_nbrs[-1])
29
31 if len(msgs) == 0:
32 self.set(p,"send", None)
33 else:
34 msg = msgs.pop()
35 if msg.content == p.UID:
36 self.output(p,"status", "leader")
37 elif msg.content > p.UID:
38 self.set(p,"send", msg)
39 self.output(p,"status", "non-leader")
40 else:
41 self.set(p, "send", None)
42 if self.r == p.state['n']: p.terminate(self)
43
45
47 """The LeLann, Chang and Roberts algorithm for Leader Election in an Asynchronous Ring Network
48
49 Each Process sends its identifier around the ring.
50 When a Process receives incoming identifier(s), it compares their largest to its own.
51 If that incoming identifier is greater than its own, it keeps passing that identifier;
52 if it is less than its own, it discards all the incoming identifiers;
53 if it is equal to its own, the Process declares itself the leader.
54 When a Process has declared itself Leader, it sends a Leader Declaration message around the ring, and halts
55 As it goes around the ring, each other Process outputs 'non-leader', and halts.
56
57 Requires:
58 - Every process knows state['n'], the size of the network
59 Effects:
60 - Every process has state['status'] is 'leader' or 'non-leader'.
61 - Exactly one process has state['status'] is 'leader'
62 """
64 - def msgs_i(self, p, verbose=False):
65 if not self.has(p, "sends"):
66 self.set(p, "sends", [Message(self, p.UID)])
67
68 if p.state["status"] == "leader":
69 msg = AsyncLCR.Leader_Declaration(self)
70 p.send_msg(msg, p.out_nbrs[-1])
71 if verbose:
72 print p,"sends",msg
73 p.terminate(self)
74 return
75 while len(self.get(p, "sends")) > 0:
76 msg = self.get(p, "sends").pop()
77 p.send_msg(msg, p.out_nbrs[-1])
78 if verbose:
79 print p,"sends",msg
80
81 - def trans_i(self, p, verbose=False):
82 msgs = p.get_msgs(self)
83 if verbose:
84 print str(p) + " received " + str(p.in_channel)
85 while len(msgs) > 0:
86 msg = msgs.pop()
87 if isinstance(msg, AsyncLCR.Leader_Declaration):
88 p.send_msg(msg, p.out_nbrs[-1])
89 if verbose:
90 print p,"sends",msg
91 p.terminate(self)
92 return
93 elif msg.content == p.UID:
94 self.output(p,"status", "leader")
95 elif msg.content > p.UID:
96 self.get(p, "sends").append(msg)
97 self.output(p,"status", "non-leader")
98
100
101
102
104 """
105 UID flooding algorithm for Leader Election in a general network
106
107 Every process maintains a record of the maximum UID it has seen so far
108 (initially its own). At each round, each process propagates this maximum
109 on all of its outgoing edges. After diam rounds, if the maximum value seen
110 is the process's own UID, the process elects itself the leader; otherwise,
111 it is a non-leader.
112
113 Requires:
114 - Every process, p, has p.state["diam"] >= dist( p, q ), forall q.
115 - Alternatively, a process that does not know state["diam"] will use
116 state["n"], the size of the network, as a fallback upper bound on diam.
117 """
119 if self.r < self.get(p, "diam"):
120 if not self.has(p, "send"):
121 self.set(p, "send", Message(self, p.UID))
122 p.send_msg(self.get(p, "send"))
123
124 - def trans_i(self, p, msgs, verbose=False):
125 if verbose:
126 print p, "received", p.in_channel
127 seen_uids = msgs + [self.get(p, "send")]
128 self.set(p, "send", max(seen_uids, key = lambda m: m.content))
129
130 if self.r == self.get(p, 'diam'):
131 if self.get(p, "send").content == p.UID:
132 self.output(p,"status", "leader")
133 p.terminate(self)
134 else:
135 self.output(p,"status", "non-leader")
136 p.terminate(self)
137
139
140
141
143 """Constructs a BFS tree with the 'leader' Process at its root
144
145 At any point during execution, there is some set of processes that is
146 "marked," initially just i0. Process i0 sends out a search message at
147 round 1, to all of its outgoing neighbors. At any round, if an unmarked
148 process receives a search message, it marks itself and chooses one of the
149 processes from which the search has arrived as its parent. At the first
150 round after a process gets marked, it sends a search message to all of its
151 outgoing neighbors.
152
153 Requires:
154 - testLeaderElection
155 Effects:
156 - every Process has state['parent']. Leader has state['parent'] = None
157 """
159 """Search for children"""
160 pass
161
162 - def is_i0(self, p): return p.state["status"] == "leader"
163
172 if len(msgs)> 0:
173 if "parent" not in p.state:
174 self.output(p,"parent", msgs[0].content)
175 self.set(p, "recently_marked", True)
176 return
177 if "parent" in p.state:
178 if self.has(p, "recently_marked"): self.delete(p, "recently_marked")
179 p.terminate(self)
180
182 """Constructs a BFS tree with children pointers and the 'leader' Process at its root
183
184 Algorithm (Informal):
185 At any point during execution, there is some set of processes that is
186 "marked," initially just i0. Process i0 sends out a search message at
187 round 1, to all of its outgoing neighbors. At any round, if an unmarked
188 process receives a search message, it marks itself and chooses one of the
189 processes from which the search arrived as its parent. At the first
190 round after a process gets marked, it sends a search message to all of its
191 outgoing neighbors, and an acknowledgement to its parent, so that nodes
192 will also know their children.
193
194 Requires:
195 - testLeaderElection
196 Effects:
197 - Every process knows:
198 - state['parent']. Leader has state['parent'] = None
199 - state['childen']. Leaves have state['children'] = []
200 """
202 """Search for children"""
203 pass
205 """Acknowledge Parent"""
206 pass
207
208 - def is_i0(self, p): return p.state["status"] == "leader"
209
211 if self.is_i0(p) and self.r == 1:
212 self.output(p, "parent", None)
213 self.set(p, "recently_marked", True)
214 p.send_msg(SynchBFSAck.Search(self, p))
215 elif self.has(p, "recently_marked"):
216 p.send_msg(SynchBFSAck.Search(self, p))
217 p.send_msg(SynchBFSAck.AckParent(self, p), p.state['parent'] )
218 if self.params["verbosity"]>=Algorithm.VERBOSE:
219 print p,"ack", p.state['parent']
221 search_msgs = [m.content for m in msgs if isinstance(m, SynchBFSAck.Search)]
222 ack_msgs = [m.content for m in msgs if isinstance(m, SynchBFSAck.AckParent)]
223
224 if 'parent' not in p.state:
225 if len(search_msgs)> 0:
226 self.output(p, "parent", search_msgs[0])
227 self.set(p, "recently_marked", True)
228 if self.params["verbosity"]>=Algorithm.VERBOSE:
229 print str(p), "chooses parent"
230 else:
231 if self.has(p, "recently_marked"):
232 self.delete(p, "recently_marked")
233 elif "children" not in p.state:
234 self.output(p,"children", ack_msgs)
235 p.terminate(self)
236 if self.params["verbosity"]>=Algorithm.VERBOSE:
237 print p,"knows children"
238
239
240
242 """The abstract superclass of a class of Synchronous Algorithms that
243 propagate information from the leaves of a BFS tree to its root.
244
245 Requires:
246 - Every Process knows state['parent']
247 """
248
275
277 """The abstract superclass of a class of Asynchronous Algorithms that
278 propagate information from the leaves of a BFS tree to its root.
279
280 Requires:
281 - Every Process knows state['parent'] and state['children']"""
292
304
308
310 """Determines the state transition the root node should undergo
311 when it receives messages
312
313 @param p: the root Process
314 @param msgs: the messages received by the root Process, from its BFS children
315 """
316 pass
318 """Determines the output action, if any, that the root should perform
319 at the end of the Convergecast.
320 """
321 pass
323 """Defines the initial message sent from a leaf process to its parent at the
324 beginning of the Convergecast
325
326 @param p: A Process at a leaf of the BFS tree
327 @return: the Message p should send to its state['parent']
328 """
329 return
331 """Defines the message a non-leaf, non-root Process should send to its parent
332 when it has received all its children's messages
333
334 @param p: a Process that has both p.state['parent'] != null, and p.state['children'] not empty
335 @param msgs: A list of messages from every child of p (in p.state['children'])
336 @return: the Message p should send to its state['parent']
337 """
338 return
339
341 class _ConvergeHeight(Convergecast):
342 """
343 A Convergecast Algorithm that results in the root node, p, knowing
344 p.state['height'], the height of the tree rooted at p.
345
346 Requires:
347 - BFS Tree
348 Effects:
349 - Root Process knows height of tree in state["height"]
350 """
351 def trans_root(self, p, msgs):
352 self.set(p, 'height', max(msgs))
353 def output_root(self, p):
354 self.output(p,'height', self.get(p, 'height'))
355 def initial_msg_to_parent(self, p):
356 return Message(self, 1)
357 def trans_msg_to_parent(self, p, msgs):
358 return Message(self, 1 + max(msgs))
359 def cleanup_i(self, p):
360 Convergecast.cleanup_i(self,p)
361 self.delete(p, 'height')
362 return _ConvergeHeight
363
364 SynchConvergeHeight = _converge_height(SynchConvergecast)
365 AsynchConvergeHeight = _converge_height(AsynchConvergecast)
366
367
369 """Broadcasts a value stored in Process, p, to the BFS tree rooted at p
370
371 Requires:
372 - The attribute to be broadcasted must be specified in self.params['attr']
373 - BFS Tree with children pointers, where root node has state[self.params['attr']]
374 Effects:
375 - All Processes have state[self.params['attr']] := the original value of in
376 state[self.params['attr']] of the root Process.
377
378 For example: If the root Process, p, knows p.state['min_UID'] = 4. Then after the
379 execution, all Processes q in the Network know q.state['min_UID'].
380 """
392 msgs = [m.content for m in msgs]
393 attr = self.params['attr']
394 if p.state['parent'] is None:
395 p.terminate(self)
396 else:
397 if len (msgs) == 1:
398 self.output(p,attr, msgs[0])
399 if len(p.state['children']) > 0:
400 self.set(p, 'send', msgs[0])
401 else:
402 p.terminate(self)
404
405
407 """A randomized algorithm that constructs a Maximal Independent Set
408
409 The algorithm works in stages, each consisting of three rounds.
410
411 - Round 1: In the first round of a stage, the processes choose their
412 respective vals and send them to their neighbors. By the end of round
413 1, when all the val messages have been received, the winners--that is,
414 the processes in F--know who they are.
415 - Round 2: In the second round, the winners notify their neighbors. By
416 the end of round 2, the losers--that is, the processes having neighbors
417 in F--know who they are.
418 - Round 3: In the third round, each loser notifies its neighbors. Then
419 all the involved processes--the winners, the losers, and the losers'
420 neighbors-- remove the appropriate nodes and edges from the graph. More
421 precisely, this means the winners and losers discontinue participation
422 after this stage, and the losers' neighbors remove all the edges that
423 are incident on the newly removed nodes.
424
425 Requires:
426 - Every process knows state['n'], the size of the network
427 Effect:
428 - Every process knows state['MIS']. A boolean representing whether it
429 is a member of the Maximal Independent Set found by Luby's algorithm.
430 """
432 if self.r == 1:
433 self.set(p, 'rem_nbrs', p.out_nbrs[:])
434 self.set(p, 'status', 'unknown')
435
436 if self.r%3 == 1:
437 self.set(p, 'val', random.randint(0,p.state['n'] **4 ))
438 p.send_msg( Message(self, self.get(p, 'val')), self.get(p, 'rem_nbrs') )
439 if self.r%3 == 2:
440 if self.get(p, 'status') == 'winner':
441 p.send_msg( Message(self, 'winner') , self.get(p, 'rem_nbrs') )
442 if self.r%3 == 0:
443 if self.get(p, 'status') == 'loser':
444 p.send_msg( Message(self, 'loser') , self.get(p, 'rem_nbrs') )
446 values = [m.content for m in msgs]
447 if self.r%3 ==1:
448 if len(values) == 0 or self.get(p, 'val') > max(values):
449 self.set(p, 'status', 'winner')
450 self.output(p, 'MIS', True)
451 if self.r%3 ==2:
452 if 'winner' in values:
453 self.set(p, 'status', 'loser')
454 self.output(p,'MIS', False)
455 if self.r%3 == 0:
456 rem_nbrs = self.get(p, 'rem_nbrs')
457 for m in msgs:
458 if m.content == 'loser':
459 rem_nbrs.remove(m.author)
460 self.set(p, 'rem_nbrs', rem_nbrs)
461 if self.get(p, 'status') in ['winner', 'loser']:
462 p.terminate(self)
463