Brief Announcement: There are Plenty of Tasks Weaker than Perfect Renaming and Stronger than Set Agreement

摘要

In the asynchronous wait-free shared memory model, two families of tasks play a central role because of their implications in theory and in practice: κ-set agreement and M-renaming. Let n denote the number of processes in the system. Previous research shows that (n-1)-set agreement can solve (2n-2)-renaming, for any value of n, while (2n-2)-renaming cannot solve (n-1)-set agreement, when n is odd. It is also known that, for every n ≥ 3, n-renaming, also called perfect renaming, is strictly stronger than (n-1)-set agreement. This paper shows that when n ≥ 4, there is a family of tasks that are? strictly stronger than (n-1)-set agreement and strictly weaker than perfect: renaming. This enlarges our view of both the nature and the structure of what are distributed computing tasks.