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(logn) 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(loglogn). |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.jpdc.2021.01.002 | Journal of Parallel and Distributed Computing |
Keywords | DocType | Volume |
Tight renaming,Loose renaming,Distributed algorithm,Shared memory model,Randomized algorithm | Journal | 150 |
ISSN | Citations | PageRank |
0743-7315 | 0 | 0.34 |
References | Authors | |
0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Petra Berenbrink | 1 | 472 | 46.41 |
Andre Brinkmann | 2 | 202 | 27.48 |
Robert Elsässer | 3 | 104 | 13.93 |
Tom Friedetzky | 4 | 0 | 0.34 |
Lars Nagel | 5 | 76 | 13.58 |