The Taub Faculty of Computer Science Events and Talks
Armando Castaneda (CS, Technion)
Wednesday, 12.06.2013, 12:30
The M-renaming task requires n+1 processes, each starting with a unique input name (from an arbitrary large range), to coordinate the choice of new output names from a range of size M. This talk presents the first upper bound on the complexity of 2n-renaming, when n + 1 is not a prime power.
It is known that 2n-renaming can be solved if and only if n+1 is not a prime power; however, the previous proof of the ``if" part was non-constructive, involving an approximation theorem; in particular, it did not yield a concrete upper bound on the complexity of the resulting protocol.