21st IEEE International Conference on Distributed Computing Systems (ICDCS'01) Self-Stabilizing PIF Algorithm in Arbitrary Rooted Networks Mesa, AZ April 16-April 19 ISBN: 0-7695-1077-9
Abstract: We present a deterministic distributed Propagation of Information with Feedback (PIF) protocol in arbitrary rooted networks. The proposed algorithm does not use a pre-constructed spanning tree. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to behave according to its specification. Every PIF wave initiated by the root inherently creates a tree in the graph. So, the tree is dynamically created according to the progress of the PIF wave. This allows our PIF algorithm to take advantage of the relative speed of different components of the network. The proposed algorithm can be easily used to implement any self-stabilizing system which requires a (self-stabilizing) wave protocol running on an arbitrary network.
Index Terms:
Fault-tolerance, propagation of information with feedback, reset, self-stabilization, snapshot, wave algorithms.
Citation:
Alain Cournier, Franck Petit, Vincent Villain, Ajoy K. Datta, "Self-Stabilizing PIF Algorithm in Arbitrary Rooted Networks," icdcs, pp.0091, 21st IEEE International Conference on Distributed Computing Systems (ICDCS'01), 2001 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||