Premium
Reliable distributed diagnosis for multiprocessor systems with random faults
Author(s) -
Berman Piotr,
Pelc Andrzej
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240803
Subject(s) - hypercube , correctness , computer science , multiprocessing , probabilistic logic , parallel computing , graph , fault tolerance , algorithm , theoretical computer science , distributed computing , artificial intelligence
We study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability p . They test their neighbors, and a fault‐free processor has probability 1 − q of discovering a fault of a failed neighbor in an individual test. Subsequently, fault‐free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every p ≤ ½, q ≤ 1, we construct systems with O ( n log n ) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 − n −1 . We also show that for some small fixed p and q a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small k , for a system with n processors and kn log n links, the probability of achieving correct diagnosis cannot exceed n −0.5 . © 1994 by John Wiley & Sons, Inc.