The Complexity of Renaming

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our individual bound with a global lower bound of Omega(k log(k/c)) on the total step complexity of renaming into a namespace of size c k, for any c >= 1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.

Published in:
Presented at:
Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, Palm Springs, CA, USA, 22-25 Oct. 2011
Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa

 Record created 2011-08-24, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)