Asymptotically optimal algorithms for approximate agreement

This paper introduces some algorithms to solve crash-failure, failure-by-omission and Byzantine failure versions of the Byzantine Generals or consensus problem, where non-faulty processors need only arrive at values that are close together rather than identical. For each failure model and each value ofS, we give at-resilient algorithm usingS rounds of communication. IfS=t+1, exact agreement is obtained. In the algorithms for the failure-by-omission and Byzantine failure models, each processor attempts to identify the faulty processors and corrects values transmited by them to reduce the amount of disagreement. We also prove lower bounds for each model, to show that each of our algorithms has a convergence rate that is asymptotic to the best possible in that model as the number of processors increases.Alan Fekete was born in Sydney Australia in 1959. He studied Pure Mathematics and Computer Science at the University of Sydney, obtaining a B.Sc.(Hons) in 1982. He then moved to Cambridge, Massachusetts, where he obtained a distributed Ph.D. degree, awarded by Harvard University's Mathematics department for work supervised by Nancy Lynch in M.I.T.'s Laboratory for Computer Science. He spend the year 1987–1988 at M.I.T. as a postdoctoral Research Associate, and is now Lecturer in Computer Science at the University of Sydney. His research concentrates on understanding the modularity in distributed algorithms, especially those used for concurrency control in distributed databases.A preliminary version of this paper has appeared in the Proceedings of the 5th ACM Symposium on Principles of Distributed Computing (August 1986). This work was begun in the Department of Mathematics, Harvard University, and completed at the Laboratory for Computer Science at Massachusetts Institute of Technology. The work was supported in part (through Professor N. Lynch) by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under contract DAAG29-84-K-0058, by the National Science Foundation under Grants MCS-8306854, DCR-83-02391, and CCR-8611442, and by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125