Alistarh, Dan ; Aspnes, James ; Censor-Hillel, Keren ; Gilbert, Seth ; Guerraoui, Rachid
This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of ω(k) process steps for deterministic renaming into any namespace of size subexponential in k, where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of ω(klog(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c = 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.
Journal of the ACM
The work of J. Aspnes was supported in part by NSF grant CCF-0916389. The work of S. Gilbert was supported by Singapore AcRF-2 MOE 2011-T2-2-042. K. Censor-Hillel is a Shalon Fellow. Part of this work was performed while K. Censor-Hillel was a postdoc at MIT, supported by the Simons Postdoctoral Fellowship.
Alistarh D, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. Tight bounds for asynchronous renaming. Journal of the ACM. 2014;61(3). doi:10.1145/2597630
Alistarh, D., Aspnes, J., Censor Hillel, K., Gilbert, S., & Guerraoui, R. (2014). Tight bounds for asynchronous renaming. Journal of the ACM, 61(3). https://doi.org/10.1145/2597630
Alistarh, Dan, James Aspnes, Keren Censor Hillel, Seth Gilbert, and Rachid Guerraoui. “Tight Bounds for Asynchronous Renaming.” Journal of the ACM 61, no. 3 (2014). https://doi.org/10.1145/2597630.
D. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, and R. Guerraoui, “Tight bounds for asynchronous renaming,” Journal of the ACM, vol. 61, no. 3, 2014.
Alistarh D, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. 2014. Tight bounds for asynchronous renaming. Journal of the ACM. 61(3).
Alistarh, Dan, et al. “Tight Bounds for Asynchronous Renaming.” Journal of the ACM, vol. 61, no. 3, ACM, 2014, doi:10.1145/2597630.