2003 · 17 citations · 17 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsFault-tolerant ComputingDiagnosisDistributed AlgorithmsDistributed ComputingFault DetectionFault DiagnosisReliable Distributed SystemsByzantine FaultsDistributed DiagnosticsDistributed Fault DetectionDistributed Fault DiagnosisSystem Fault Diagnosis
The problem of correctly identifying the faulty processors and links in a distributed system where faulty behavior is unrestricted (Byzantine) is examined. A very general class of algorithms called evidence-based diagnosis algorithms is proposed that encompasses all past approaches to the diagnosis problem. An algorithm is presented which is proven optimal in this class. It is further shown that, in the worst case, no evidence-based diagnosis algorithm can guarantee that its diagnosis is both correct and complete, when evidence can be false. It is argued both analytically and from experimental data that in systems of N processors of which t can be faulty, the complexity of this algorithm is O(max(2 to the power of t/sup 2/, N/sup 2/)).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
17
Reaching Agreement in the Presence of Faults
Marshall C. Pease, Robert E. Shostak, Leslie Lamport · Journal of the ACM · 1980 · 2.4K citations · Full text