אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.