×

Analysis of a realistic fault model for large distributed systems. (English) Zbl 0867.90058

Summary: In contrast to the classic form of distributed agreement, called Byzantine agreement, approximate agreement does not require non-faulty processes to achieve exact agreement. Rather, non-faulty processes need only agree on values within a predefined tolerance. Recent research has revealed simple expressions for the convergence rate and fault tolerance of a broad family of convergent voting algorithms called mean-subsequence-reduced (MSR) algorithms. The analysis was done for simultaneous presence of asymmetric, symmetric, and benign fault modes. This paper introduces a new fault-model, omission-MSR (OMSR). The new model broadens the applicability of hybrid fault-models by introducing an additional fault-mode, omissive faults. It will be shown that OMSR has a number of advantages over the MSR model. Also, the results of the two models will be transformed into a singular set of relations and tables so that their convergence rate and fault tolerance can be compared. In the context of this paper, these relations and tables provide the means to easily determine the convergent properties of different voting algorithms for completely and partially connected networks.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
93A15 Large-scale systems
PDFBibTeX XMLCite