From Renaming to Set AgreementSet Agreement • April 7th, 2007
This paper focuses on the way a solution to the renaming problem can help solving the k-set agreement problem when k t. It has several contributions. The first is a t-resilient algorithm (1 t < n) that solves the k-set agreement problem from any adaptive (n + k 1)-renaming algorithm, when k = t. The second contribution is a lower bound that shows that there is no wait-free k-set algorithm based on an (n + k 1)- renaming algorithm that works for any value of n, when k < t. This bound shows that, while a solution to the (n + k 1)-renaming prob- lem allows solving the k-set agreement problem despite t = k failures, such an additional power is useless when k < t. In that sense, in an asynchronous system made up of atomic registers, (n + k 1)-renaming allows progressing from k > t to k = t, but does not allow bypassing that frontier. The last contribution of the paper is a wait-free algorithm that constructs an adaptive (n + k 1)-renaming algorithm, for any value of the pair (t, k), from a
