6533b833fe1ef96bd129b826

RESEARCH PRODUCT

Randomized renaming in shared memory systems.

subject

description

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 ) l ) ⋅ n = ( 1 + o ( 1 ) ) ⋅ n performing O ( l ⋅ ( log log n ) 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.