Unified Approach to Synchronous & Asynchronous roximate Agreement in the Presence of
M. Kieckhafer · 1995
Summary & Conclusions - An important problem in faulttolerant distributed systems is maintaining agreement between nonfaulty processes in the presence of undiagnosed faults. Approximde Agreement defines a condition in which it is not necessary for the agreed values to be numerically identical. Rather, processes need only agree with each other to within a predefined numerid tolerance. Convergent voting algorithms which achieve Approximate Agreement have been studied in the context of two classes of systems, Synchronous & Asynchronous. Studies have also addressed both Completely Connected and Pu&y Connected system. Together, the two properties of synchrony & connectivity yield 4 different voting domains. In all studies to date, each voting domain has been treated as a separate problem. This paper: 0 Shows that for at least one broad family of voting algorithms, the 4 domains are special cases of a more general convergent voting problem. 0 Analyzes convergent voting under the 3-mode hybrid fault model of Thambidutrai & Park. * Presents a set of unifying relations applicable to all 4 voting domains. These relations are used to specify voting algorithms which optimize fault-tolerance, convergence rate, or computational overhead in any given voting domain. The task of designing a voting algorithm for a particular fault-tolerant system is thus greatly simplified.