Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks

摘要

In the wait-free shared memory model substantial attention has been devoted to understanding the relative power of sub-consensus tasks. Two important sub-consensus families of tasks have been identified: k-set agreement and M-renaming. When 2 ≤ k ≤ n - 1 and n ≤ M ≤ 2n-2, these tasks are more powerful than read/write registers, but not strong enough to solve consensus for two processes.This paper studies the power of renaming with respect to set agreement. It shows that, in a system of n processes, n-renaming is strictly stronger than (n-1)-set agreement, but not stronger than (n -2)-set agreement. Furthermore, (n+1)-renaming cannot solve even (n-1)-set agreement. As a consequence, there are cases where set agreement and renaming are incomparable when looking at their power to implement each other.