Department of Computer Science and Technology

Technical reports

Anti-Ω: the weakest failure detector for set agreement

Piotr Zieliński

July 2007, 24 pages

DOIhttps://doi.org/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}
}