From adaptive renaming to set agreement

AbstractThe adaptive M-renaming problem consists of providing processes with a new name taken from a name space whose size M depends only on the number p of processes that participate in the renaming (and not on the total number n of processes that could ask for a new name). The k-set agreement problem allows each process that proposes a value 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. In the same setting, the k-set agreement problem cannot be solved when t≥k.This paper focuses on the way a solution to the adaptive renaming problem can help in solving the k-set agreement problem when t≥k. It has two contributions. Considering the case k=t (1≤t<n), the first contribution is a t-resilient algorithm that solves the k-set agreement problem from any adaptive (p+k−1)-renaming algorithm. The second contribution considers the case k<t. It shows that there is no such wait-free algorithm when k<n/2 (wait-free means t=n−1). So, while a solution to the adaptive (p+k−1)-renaming problem allows t-resiliently solving the k-set agreement problem despite t=k failures, when k<t such an additional power becomes useless for the values of n>2k (i.e. adaptive (p+k−1)-renaming allows progressing from k>t to k=t, but does not allow bypassing the “k=t” frontier when n>2k)