The Taub Faculty of Computer Science Events and Talks

In a distributed task, processes of a distributed system start with private input values, communicate each other using a medium and then irrevocably decide an output value. In the M-renaming task each process of the system starts with a distinct input name. and must decide a distinct output name in the range [1, ..., M]. The renaming task is at the core of the theory of distributed computing.

Several papers claimed that, in an asynchronous distributed system in which processes communicate through a shared memory, M = 2n-1 is a tight lower bound for renaming, namely, there is an algorithm that solves M-renaming if and only if M >= 2n-1, where n denotes the number of processes.

In this talk we will see that the renaming lower bound above is incomplete. There are values of n for which indeed M = 2n-1 is a tight lower bound for. However, for the other (infinitely many) values of n, there exists an algorithm that solves M-renaming with M = 2n-2. The solvability of (2n-2)-renaming is closely related with the existence of topological objects in some dimensions.

Bio: Armando Castaneda got his PhD from the National Aunonomous University of Mexico under the supervision of Prof. Sergio Rajsbaum. He joined the Department of Computer Science of the Technion in July of 2012. His research interest lies in the theory of distributed systems, particularly, in understanding the principles of distributed computing.