New Combinatorial Topology Bounds for Renaming: The Upper Bound

作者：Castaneda Armando^*; Raj**aum Sergio

来源：Journal of the ACM, 2012, 59(1): 3.

DOI：10.1145/2108242.2108245

• Algorithms
• Theory
• Distributed computing
• shared-memory
• upper bound
• combinatorial topology

In the renaming task, n + 1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, 0, 1, ..., K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process ID. %26lt;br%26gt;Attiya et al. [1990] showed that renaming has a wait-free solution when K %26gt;= 2n. Several algebraic topology proofs of a lower bound stating that no such protocol exists when K %26lt; 2n have been published. In a companion article, we present the first completely combinatorial renaming lower bound proof stating if n + 1 is a primer power, then renaming is not wait-free solvable when K %26lt; 2n. In this article, we show that if n + 1 is not a primer power, then there exists a wait-free renaming protocol for K = 2n - 1. Therefore the renaming lower bound for K %26lt; 2n is incorrect. More precisely, our main theorem states that there exists a wait-free renaming protocol for K %26lt; 2n if and only if n + 1 is not a prime power. We prove this result using the known equivalence of K-renaming for K = 2n - 1 and the weak symmetry breaking task: processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 1 and at least one process decides 0.

• 出版日期2012-2