From Renaming to Set Agreement.

The M-renaming problem consists in providing the processes with a new name taken from a new name space of size M. A renaming algorithm is adaptive if the size M depends on the number of processes that want to acquire a new name (and not on the total number n of processes). Assuming each process proposes a value, the k-set agreement problem allows each process to decide a proposed value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M = p + t where p is the number of processes that participate in the renaming. In the same setting, the k-set agreement problem cannot be solved for t ≥ k. 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 problem 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 failure detector of the class $\Omega^k_*$ (this last algorithm is a simple adaptation of an existing renaming algorithm). [ABSTRACT FROM AUTHOR]