Counting-based impossibility proofs for set agreement and renaming

• We consider the wait-free solvability of tasks in shared memory systems.
• Only combinatorial and number-theoretic arguments are used.
• (n−1)(n−1)-set agreement is not wait-free solvable.
• Adaptive (2n−2)(2n−2)-renaming and strong symmetry breaking are not wait-free solvable.
• Nonadaptive (2n−2)(2n−2)-renaming and weak symmetry breaking are not wait-free solvable, when nn is the power of a prime number.

Set agreement and renaming are two tasks that allow processes to coordinate, even when agreement is impossible. In kk-set agreement  , nn processes must decide on at most kk of their input values. While nn-set agreement is trivially wait-free solvable by each process deciding on its input, (n−1)(n−1)-set agreement is not wait-free solvable. In MM-renaming  , processes must decide on distinct names in a range of size MM. For any number nn of processes, (2n−1)(2n−1)-renaming is wait-free solvable, but surprisingly, (2n−2)(2n−2)-renaming is wait-free solvable if and only if nn is not a prime power; the only previous lower bound on the number of names necessary for renaming, when nn is not a prime power, is n+1n+1. In adaptive   renaming, MM decreases when the number pp of participants in the execution decreases. It is known that (2p−1)(2p−1)-adaptive renaming is wait-free solvable, while (2p−⌈pn−1⌉)-adaptive renaming is not.This paper presents counting-based proofs for the above mentioned impossibility results: nn processes can wait-free solve neither (n−1)(n−1)-set agreement nor (2p−⌈pn−1⌉)-adaptive renaming; if nn is a prime power, nn processes cannot wait-free solve (2n−2)(2n−2)-renaming. For an arbitrary number of processes, we give a lower bound for renaming, by reduction from renaming for a different number of processes, and relying on the distribution of prime numbers.Our proofs combine simple operational properties of a restricted set of executions with elementary counting arguments to show the existence of an execution violating the task’s conditions. This makes the proofs easier to understand, verify, and, we hope, extend.