A Tight Lower Bound for Processor Coordination

We prove a tight lower bound on the running time of oblivious solutions to k-set agreement. In k-set agreement, processors start with input values from a given set and choose output values from the same set. In every execution, the set of output values must be contained in the set of input values, and the set of output values must have size at most k. A solution is oblivious if it does not make use of processor identities. We analyze this problem in a synchronous model where processors can fail by just stopping. We prove a lower bound of bf=kc+ 1 rounds of communication for oblivious solutions that tolerate f failures. This shows that there is an inherent trade-o between the running time, the degree of coordination required, and the number of faults tolerated, even in idealized models like ours.