### New combinatorial topology bounds for renaming: The upper boundNew combinatorial topology bounds for renaming: The upper bound

Access Restriction
Subscribed

 Author Castaeda, Armando ♦ Rajsbaum, Sergio Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2012 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Distributed computing ♦ Combinatorial topology ♦ Shared-memory ♦ Upper bound Abstract In the $\textit{renaming}$ task, $\textit{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,…, $\textit{K}.$ To rule out trivial solutions, a protocol must be $\textit{anonymous}:$ the value chosen by a process can depend on its input name and on the execution, but not on the specific process ID. Attiya et al. [1990] showed that renaming has a wait-free solution when $\textit{K}≥$ $2\textit{n}.$ Several algebraic topology proofs of a lower bound stating that no such protocol exists when $\textit{K}$ < $2\textit{n}$ have been published. In a companion article, we present the first completely combinatorial renaming lower bound proof stating if $\textit{n}$ + 1 is a primer power, then renaming is not wait-free solvable when $\textit{K}$ < $2\textit{n}.$ In this article, we show that if $\textit{n}$ + 1 is not a primer power, then there exists a wait-free renaming protocol for $\textit{K}$ = $2\textit{n}™1.$ Therefore the renaming lower bound for $\textit{K}$ < $2\textit{n}$ is incorrect. More precisely, our main theorem states that there exists a wait-free renaming protocol for $\textit{K}$ < $2\textit{n}$ if and only if $\textit{n}$ + 1 is not a prime power. We prove this result using the known equivalence of $\textit{K}-renaming$ for $\textit{K}$ = $2\textit{n}$ ™ 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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2012-03-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 59 Issue Number 1 Page Count 49 Starting Page 1 Ending Page 49

#### Open content in new tab

Source: ACM Digital Library