The
Distributed Consensus problem involves
n processors each of which holds an initial binary vlaue. At most
t of the processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. In this paper we focus on consensus in networks whose degree is bounded, following the work of Dwork, Peleg, Pippenger and Upfal [8]. In such a context, complete consensus among all the correct processors is not possible and some exceptions must be allowed. We first show how to achieve consensus in the butterfly network using
O(
t+log
nloglog
n) one-bit parallel transmission steps, while tolerating the asymptotically optimal number of faulty processors (
O(n/log
n)) and having the asymptotically minimal number of exceptions (
O(tlog
t)). This result considerably improves on the running time of existing butterfly consensus protocols [2, 8]. In particular, it replaces the running time of
O(nlog
nloglog
n) of [2] with an asymptotically optimal one. As in [8], we can then decrease the number of exceptions to
O(t) by using additional links, while maintaining the same running time. The protocol is derived from a consensus protocol for completely connected networks that is interesting in its own right: it achieves Distributed Consensus with optimal number of processors, asymptotically optimal total bit transfer and nearly optimal number of rounds.
Key words Distributed consensus - Bounded-degree network - Network algorithms - Fault tolerance
Piotr Berman was born in 1955 in Warsaw, Poland, where here progressed from day-care to the degree of Master of Mathematics obtained from the University of Warsaw in 1978. He later studied at the Polish Academy of Sciences and MIT. He received a Ph.D. in Mathematics from MIT in 1985. From 1982 he has been teaching at Penn State, where currently he has a permanent position. His research interests are in two areas: fault-tolerant distributed computing and approximation algorithms. His non-professional hobbies include ancient history and mountain hiking.
Juan Alberto Garay is originally from Rosario, Argentina, where he received his degree of Electrical Engineering from the Universidad Nacional de Rosario in 1976, at the age of 21. He then received his Master's degree in Electronic Engineering from the Eindhoven International Institute of the Eindhoven University of Technology (Eindhoven, Holland) in 1981, and his Ph.D. in Computer Science at Penn State University (University Park, PA) in 1989. Between his first and second degrees he worked as a digital design engineer for SOMISA (San Nicola's, Argentina), and between his second and Ph.D. degrees as a systems engineer for IBM Argentina. During the 1989/1990 academic year he was a visiting Assistant Professor at Bucknell University (Lewisburg, PA), and since 1990 he is with IBM's T.J. Watson Research Center (Yorktown Heights, NY). In 1992 he spent 6 months at The Weizmann Institute of Science (Rehovot, Israel) as a postdoctoral fellow. His professional interests include algorithms and lower bounds, distributed computation and fault tolerance. Dr. Garay enjoys tennis, music and philosophy.
Preliminary version appeared in Proc 4th International Workshop on Distributed Algorithms, LNCS 486 (Springer-Verlag), pp 321–333, 1990