Agreement is harder than consensus: set consensus problems in totally asynchronous systems
S.K. Chaudhuri · 1990
We define the k-set consensus problem as an extension of the consensus problem, where each processor decides on a single value such that the set of decided values in any run is of size at most k.We study variations of this problem by adding the agreement condition, which requires that any decided value must be an initial value of some processor, and the uncertainty condition, which requires that there must be some initial configuration from which all possible input values can be decided.While the basic set consensus problem has an (n -1) -resilient protocol, adding the agreement condition only yields a (k-1)-resilient protocol.We prove using a combinatorial argument that any k-resilient protocol for the latter problem would satisfy the uncertainty condition, while this is not true for a (k -I)-resilient pro+ col.This seems to strengthen the conjecture that there is no k-resilient protocol for this problem.Our motivation for studying this class of problems is to test whether the number of choices allowed to the processors is related to the number of faults.We hope that this will provide intuition towards achieving better bounds for more practical problems that arise in distributed comput-+Supported by NSF grant rto.