The adaptive renaming problem consists in designing an algorithm that allows p processes (in a set of n processes) to obtain new names despite asynchrony and process crashes, in such a way that the size of the new renaming space M be as small as possible. It has been shown that M = 2p- 1 is a lower bound for that problem in asynchronous atomic read/write register systems. This paper is an attempt to circumvent that lower bound. To that end, considering first that the system is provided with κ-set object, the paper presents a surprisingly simple adaptive M-renaming wait-free algorithm where M = 2p - [p/κ|. To attain this goal, the paper visits what we call Gafni's reduction land, namely, a set of reductions from one object to another object as advocated and investigated by Gafni. Then, the paper shows how a κ-set object can be implemented from a leader oracle (failure detector) of a class denoted Ω~κ. To our knowledge, this is the first time that the failure detector approach is investigated to circumvent the M = 2p- 1 lower bound associated with the adaptive renaming problem. In that sense, the paper establishes a connection between renaming and failure detectors.
展开▼
