Anti-Ω

Abstract

In the set agreement problem, n processes have to decide on at most n-1 of the proposed values. This paper shows that the anti-Omega failure detector is both sufficient and necessary to solve set agreement in an asynchronous shared-memory system. Each query to anti-Omega returns a single process id; the specification ensures that there is a correct process whose id is returned only finitely many times.