A topological treatment of early-deciding set-agreement

AbstractThe k-set-agreement problem consists for a set of n processes to agree on less than k among n possibly different values, each initially known to only one process. The problem is at the heart of distributed computing and generalizes the celebrated consensus problem.This paper considers the k-set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. We determine the number of communication rounds needed for all correct processes to reach a decision in a given run, as a function of the degree of coordination k and the number of processes that actually fail in the run, f≤t.We prove that, for any integer 1≤k