Distributed Consensus Revisited

Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors. This problem is closely related to other problems, such as Byzantine Generals, Approximate Agreement, and k-Set Agreement. This paper examines a variant of Distributed Consensus that considers agreement on a value that is more than a single bit and requires that the agreed upon value be one of the correct processors' input values. It shows that, for this problem to be solved in a system with arbitrary failures, it is necessary that more processors remain correct than for solutions to Distributed Consensus and for cases where agreement is only a single bit. Specifically, the number of processors that must be correct is a function of the size of the domain of values used. Two existing consensus algorithms are modified to solve this stronger variant