Long-lived renaming made fast
Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman, Mark J. Moir · 1995
In the long-lived renaming problem --- a generalization of the classical one-time renaming problem --- n processors with unique names ranging over a source name space f0; : : : ; S \\Gamma 1g repeatedly acquire and release unique names from a (smaller) destination name space f0; : : : ; D \\Gamma 1g. It is assumed that at most k out of n processors concurrently request or hold names. An efficient renaming protocol provides a useful front-end for protocols whose time complexity depends on the size of the name space containing the participating processes. We consider long-lived renaming in the context of asynchronous, shared-memory multiprocessing systems that provide only read and write operations. A renaming protocol is fast iff the time complexity of acquiring and releasing a name is polynomial in k and independent of n and S. We present a wait-free, read/write protocol for long-lived renaming that achieves a destination name space of size O(k 2 ) with time complexity O(k 3 ). If ...