An optimal algorithm for distributed system level diagnosis

A. Bagchi, S. L. Hakimi

2002 · 69 citations · 13 references

Concepts

Abstract

A system consisting of n identical processors connected by links in which some processors could be faulty is considered. Initially each unit knows only its own i.d. and the i.d.'s of its immediate neighbors; no unit has any global knowledge about the system. An optimal algorithm for system level diagnosis in such a system that is based on the transmission of packets by fault-free units is presented. The algorithm requires at most 3n log p+O(n+pt) message transmissions by fault-free units, where p fault-free units simultaneously start the algorithm and there are t faulty units. The correctness of the algorithm is argued.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

References

13