Dan Alistarh: A Practical Renaming Algorithm

Renaming is a classic distributed coordination task in which a set of
processes must pick distinct identifiers from a small set of names. It
has been extensively studied from the (theoretical) point of view of
computability and complexity, and is also linked to practical problems
such as concurrent memory management. In this talk, I will present
some of our work on bridging the gap between theoretical and practical
solutions for the renaming problem.
I'll present an algorithm with O(log log n) (individual) step
complexity for renaming in a namespace of size cn, where n is a known
upper bound on contention, and c > 1 is a constant. I will then talk
about making the algorithm adapt to the actual contention in the
execution, and about its practical applications.