Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound

International audienceThe k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires t/k+1 rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after min(f/k+2, t/k+1) rounds, where f is the number of actual crashes in a run (