## 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.