Alistarh, Dan-AdrianIST Austria; Aspnes, James; Giakkoupis, George; Woelfel, Philipp
Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O(log log n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)2), where k is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires O(k log log k) total process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complement the algorithms with an ω(log log n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.
Dan Alistarh - This author was supported by the SNF Postdoctoral Fellows Program, NSF grant CCF-1217921, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations. James Aspnes - Supported in part by NSF grant CCF-0916389. George Giakkoupis - This work was funded in part by INRIA Associate Team RADCON, and ERC Starting Grant GOSSPLE 204742. Philipp Woelfel - This research was undertaken, in part, thanks to funding from the Canada Research Chairs program and the HP Labs Innovation Research Program.
200 - 209
PODC: Principles of Distributed Computing
Alistarh D-A, Aspnes J, Giakkoupis G, Woelfel P. Randomized loose renaming in O(loglogn) time. In: ACM; 2013:200-209. doi:10.1145/2484239.2484240
Alistarh, D.-A., Aspnes, J., Giakkoupis, G., & Woelfel, P. (2013). Randomized loose renaming in O(loglogn) time (pp. 200–209). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2484239.2484240
Alistarh, Dan-Adrian, James Aspnes, George Giakkoupis, and Philipp Woelfel. “Randomized Loose Renaming in O(Loglogn) Time,” 200–209. ACM, 2013. https://doi.org/10.1145/2484239.2484240.
D.-A. Alistarh, J. Aspnes, G. Giakkoupis, and P. Woelfel, “Randomized loose renaming in O(loglogn) time,” presented at the PODC: Principles of Distributed Computing, 2013, pp. 200–209.
Alistarh D-A, Aspnes J, Giakkoupis G, Woelfel P. 2013. Randomized loose renaming in O(loglogn) time. PODC: Principles of Distributed Computing, 200–209.
Alistarh, Dan-Adrian, et al. Randomized Loose Renaming in O(Loglogn) Time. ACM, 2013, pp. 200–09, doi:10.1145/2484239.2484240.