Distributed Algorithms for Fault Diagnosis of Processors.

This paper considers distributed algorithms for solving the problem π^p to test whether for any processor in a network, any one of the adjacent processors is faulty. First, we show that it is not solvable when processors are asynchronous or when there is no upper limit in the transmission delay along the link. Next, we define a network (PL-synchronized network) which assumes a certain kind of synchronicity in processors and their communication. Whether or not π^p is solvable in a PL-synchronized network depends on knowledge of the network topology (for example, identifiers of adjacent processors, the number of processors in a network, and edge connectivity of a network) initially available at each processor. This paper examines how the knowledge available at each processor affects the conditions that π^p is solvable (situation of faults of processors and links in the overall network). [ABSTRACT FROM AUTHOR]