Optimal-Time Adaptive Strong Renaming, with Applications to Counting

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of $n$ processes with step complexity $O(\log^3 n)$. The second transforms any sorting network into a tight adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a tight adaptive renaming algorithm with step complexity $O(\log k)$, where $k$ is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such tight renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).