New Combinatorial Topology Upper and Lower Bounds for Renaming
Armando
Castañeda
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
acastanedar@uxmcc2.iimas.unam.mx
Sergio
Rajsbaum
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
rajsbaum@math.unam.mx
Abstract
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, namely 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.
Attiya et al. showed in 1990 that renaming has a wait-free solution
when K >= 2n. Several
proofs of a lower bound stating that no such protocol exists when K< 2n have been published.
In this paper we prove that, for certain exceptional values of n, this lower bound is incorrect,
exhibiting a wait-free renaming protocol for K=2n-1. For the other values of n, we present the first completely
combinatorial lower bound proof stating that no such protocol exists
when K< 2n.
More precisely, our main theorem states that there exists a wait-free
renaming protocol for K< 2n
if and only if the set of integers $\{ {n+1 \choose i+1} : 0\leq i\leq
\lfloor\frac{n-1}{2}\rfloor\}$ are relatively prime. Thus, such
protocol exists for six processes, and not for less. Examples of
exceptional numbers, are n = 5, 9, 13.
The proof of the theorem uses combinatorial topology techniques, both
for the lower bound and to derive the renaming protocol.