Renaming and the weakest family of failure detectors

We address the question of the weakest failure detector to circumvent the impossibility of (2n-2) -renaming in a system of up to n participating processes. We derive that in a restricted class of eventual failure detectors there does not exist a single weakest oracle, but a weakest family of oracles ζ _n: every two oracles in ζ _n are incomparable, and every oracle that allows for solving renaming provides at least as much information about failures as one of the oracles in ζ _n. As a by product, we obtain one more evidence that renaming is strictly easier to solve than set agreement.