CONSENSUS ALGORITHMS WITH ONE-BIT MESSAGES

Three main parameters characterize the efficiency of algorithms that solve the Consensus Problem: the ratio between the total number of procesors 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 = t(l/k). The family includes algorithms where the number of processors is less than 5t((k+1)/k) = 5.s.t, and the number of rounds is less than t+3t(k-1/k) = 1+(3/s). 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.