Asynchronous exclusive selection
Bogdan S. Chlebus, Dariusz Rafal Kowalski · 2008
The distributed setting of this paper is an asynchronous system consisting of n processes prone to crashes and a number of shared read-write registers. We consider problems regarding assigning integer values to processes in an exclusive way, in the sense that no integer is assigned to two distinct processes. In the problem of renaming, any k ≤ n processes, that hold original names from a range [N]={1,...,N}, contend to acquire unique integers as new names in a smaller range [M] using some r shared registers. When k and N are known, our wait-free solution operates in O(log k (log N + log k log log N)) local steps, for M=O(k), and with r=O(k log(N/k)) auxiliary shared registers. Processes obtain new names by exploring their neighbors in bipartite graphs of suitable expansion properties, with nodes representing names and processes competing for the name of each visited node. We show that 1+min{k-2,log2r(N/2M)} local steps are required in the worst case to wait-free solve renaming, when k and N are known and r and M are given constraints. We give a fully adaptive solution, with neither k nor N known, having M=8k-lg k-1 as a bound on the range of new names, operating in O(k) steps and using O(n2) registers. We apply renaming algorithms to obtain solutions to the Store&Collect problem. When both k and N are known, then storing can be performed in O(log k (log N + log k log log N)) steps and collecting in O(k) steps, for r=O(k log(N/k)) registers.