Optimal PIF in Tree Networks.
Alain Bui, Ajoy K. Datta, Franck Petit, Vincent Villain · 1999
In this paper, we consider rooted tree networks, as well as trees without sense of direction. We propose a new PIF scheme, called Propagation of Information with Feedback and Cleaning (PF C ). We present both selfstabilizing and snap-stabilizing PF C algorithms. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behavior in finite time. A snap-stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in 0 steps. All the proposed algorithms are optimal PIF schemes in terms of the number of states and/or stabilization time. Keywords Fault-tolerance, optimality, PIF, self-stabilization, snap-stabilization, synchronization. 1 Introduction Fault-tolerance is one of the most important requirements of modern ...