Snap-Stabilizing PIF Algorithm in Tree Networks Without Sense of Direction

A snap-stabilizing protocol, starting from any arbitrary initial system configuration, always behaves according to its specification. In other words, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in 0 steps. In this paper, we propose a snap-stabilizing PIF algorithm for tree networks without any sense of direction. This algorithm allows us to maintain only one (instead of one per processor) spanning tree of an arbitrary network in any global computation, regardless of the number of global computations and the corresponding initiators. Keywords Fault-tolerance, PIF, self-stabilization, snap-stabilization, synchronization. 1 Introduction Fault-tolerance is one of the most important requirements of modern distributed systems. Various types of faults are likely to occur at various parts of the system. The distributed systems go through the transient faults because they are exposed to constant change of their environment. The concept of self-stabilization [..