TY - JOUR

T1 - Reliable distributed diagnosis for multiprocessor systems with random faults

AU - Berman, Piotr

AU - Pelc, Andrzej

N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 1994/12

Y1 - 1994/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21844526607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844526607&partnerID=8YFLogxK

U2 - 10.1002/net.3230240803

DO - 10.1002/net.3230240803

M3 - Article

AN - SCOPUS:21844526607

SN - 0028-3045

VL - 24

SP - 417

EP - 427

JO - Networks

JF - Networks

IS - 8

ER -