Consensus algorithms with one-bit messages

Abstract

Three main parameters characterize the efficiency of algorithms that solve the Consensus Problem: the ratio between the total number of processors and the maximum number of faulty processors (n and t, respectively), the number of rounds, and the upper bound on the size of any message. In this paper we present a trade-off between the number of faulty processors and the number of rounds by exhibiting a family of algorithms in which processors communicate by one-bit messages. Let k be a positive integer and let s=t1/k. The family includes algorithms where the number of processors is less than {Mathematical expression}, and the number of rounds is less than {Mathematical expression}. This family is based on a very simple algorithm with the following complexity: (2t+1)(t+1) processors, t+1 rounds, and one-bit message size. © 1991 Springer-Verlag.