Dijkstra–Scholten algorithm: Difference between revisions

Content deleted Content added
McoreD (talk | contribs)
No edit summary
McoreD (talk | contribs)
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.)
* In the first step, each node will send signals which reduces the deficit on each incoming edge to zero.
* Similarly, the number of signals received on each outgoing edge should reduce each of their deficits to 0.
* Once steps 1 and 2 are complete, a node informs its parent in the spanning tree about its intention of terminating.
 
[[Category:Algorithms]]