Technical reports
Anti-Ω: the weakest failure detector for set agreement
July 2007, 24 pages
DOI: 10.48456/tr-694
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-Ω failure detector is both sufficient and necessary to implement set agreement in an asynchronous shared-memory system equipped with registers. Each query to anti-Ω returns a single process id; the specification ensures that there is a correct process whose id is returned only finitely many times.
Full text
PDF (0.3 MB)
BibTeX record
@TechReport{UCAM-CL-TR-694, author = {Zieli{\'n}ski, Piotr}, title = {{Anti-$\Omega$: the weakest failure detector for set agreement}}, year = 2007, month = jul, url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-694.pdf}, institution = {University of Cambridge, Computer Laboratory}, doi = {10.48456/tr-694}, number = {UCAM-CL-TR-694} }