Content deleted Content added
No edit summary |
|||
Line 34:
* The spanning-tree is created in the following way. A variable ''First_Edge'' is added to each node. When a node receives a message for the first time, it initializes ''First_Edge'' with the edge through which it received the message. ''First_Edge'' is never changed afterwards. Note that, the spanning tree is not unique and it depends on the order of messages in the system.
* Termination is handled by each node in three steps :
*# Send signals on all incoming edges except the first edge. (Each node will send signals which reduces the deficit on each incoming edge to zero.)
*# Wait for signals from all outgoing edges. (The number of signals received on each outgoing edge should reduce each of their deficits to zero.)
*# Send signals on ''First_Edge''. (Once steps 1 and 2 are complete, a node informs its parent in the spanning tree about its intention of terminating.)
[[Category:Algorithms]]
|