Randomized Renaming in Shared Memory Systems

Berenbrink, Petra; Brinkmann, André; Elsässer, Robert; Friedetzky, Tom; Nagel, Lars

Abstract

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + ϵ) · n and constant ϵ, they achieve a step complexity of O(log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1+2/(log n)ℓ)·n = (1+o(1))·n performing O(ℓ · (log logn)2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(log n), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well.

Citation

Berenbrink, P., Brinkmann, A., Elsässer, R., Friedetzky, T., & Nagel, L. (2015, May). Randomized Renaming in Shared Memory Systems. Presented at 2015 IEEE 29th International Parallel and Distributed Processing Symposium., Hyderabad, India

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2015 IEEE 29th International Parallel and Distributed Processing Symposium.
• Start Date: May 25, 2015
• End Date: May 29, 2015
• Acceptance Date: Dec 11, 2014
• Publication Date: May 29, 2015
• Deposit Date: Dec 16, 2015
• Publicly Available Date: Mar 18, 2016
• Pages: 542-549
• Series Title: Parallel and Distributed Processing Symposium (IPDPS)
• Series ISSN: 1530-2075
• Book Title: 2015 IEEE 29th International Parallel and Distributed Processing Symposium (IPDPS 2015), 25–29 May 2015, Hyderabad, India ; proceedings.
• DOI: https://doi.org/10.1109/ipdps.2015.77
• Public URL: https://durham-repository.worktribe.com/output/1151971
• Additional Information: Date: 25-29 May 2015