Fast, Long-Lived Renaming Improved and Simplified

. In the long-lived M-renaming problem, N processes repeatedly acquire and release names ranging over f0; :::; M \Gamma1g, where M ! N . It is assumed that at most k processes concurrently request or hold names. Efficient solutions to the long-lived renaming problem can be used to improve the performance of applications in which processes repeatedly participate in a computation whose time complexity depends on the size of the name space containing the processes. In this paper, we consider wait-free solutions to the long-lived M-renaming problem that use only read and write instructions in an asynchronous, sharedmemory multiprocessor. A solution to long-lived renaming is fast if the time complexity of acquiring and releasing a name once is independent of N . We present a new fast, long-lived (k(k + 1)=2)-renaming algorithm that significantly improves upon the time and space complexity of similar previous algorithms, while providing a much simpler solution. We also show for the first tim..