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 |

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.