Anti-Ω: the weakest failure detector for set agreement

摘要

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