From adaptive renaming to set agreement

The 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≤t2k (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).