Anti-Ω: the weakest failure detector for set agreement

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.

REFERENCES

• 1: Y. Afek, E. Gafni, S. Rajsbaum, M. Raynal, and C. Travers. Simultaneous consensus tasks: A tighter characterization of set-consensus. In ICDCN 2006, LNCS 4308, pages 331--341. Springer, 2006.
• 2: Yehuda Afek , Gideon Stupp , Dan Touitou, Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.71-80, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343521]
• 3: Hagit Attiya, A direct lower bound for k-set consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.314, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277770]
• 4: Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
• 5: Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164056]
• 6: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 7: Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
• 8: W. Chen, Y. Chen, and J. Zhang. On failure detectors weaker than ever. Technical Report MSR-TR-2007-50, Microsoft Research, May 2007.
• 9: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 10: Eli Gafni , Leslie Lamport, Disk Paxos, Proceedings of the 14th International Conference on Distributed Computing, p.330-344, October 04-06, 2000
• 11: E. Gafni, S. Rajsbaum, and M. Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. In DISC 2006, LNCS 4167, pages 329--338. Springer, 2006.
• 12: Rachid Guerraoui , Maurice Herlihy , Petr Kouznetsov , Nancy Lynch , Calvin Newport, On the weakest failure detector ever, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281135]
• 13: Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343630]
• 14: R. Guerraoui and P. Kouznetsov. Finally the weakest failure detector for Non-Blocking Atomic Commit. Technical Report LPD-2003-005, EPFL, Lausanne, Switzerland, December 2003.
• 15: Rachid Guerraoui , Michel Raynal, The Alpha of Indulgent Consensus, The Computer Journal, v.50 n.1, p.53-67, January 2007 [doi>10.1093/comjnl/bxl046]
• 16: Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999 [doi>10.1145/331524.331529]
• 17: Wai-Kau Lo , Vassos Hadzilacos, Using Failure Detectors to Solve Consensus in Asynchronous Sharde-Memory Systems (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.280-295, September 29-October 01, 1994
• 18: M. Raynal and C. Travers. In search of the holy grail Looking for the weakest failure detector for wait-free set agreement. In OPODIS 2006, LNCS 4305, pages 3--19, Bordeaux, France, December 2006. Springer.
• 19: Michael Saks , Fotios Zaharoglou, Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge, SIAM Journal on Computing, v.29 n.5, p.1449-1483, March 2000 [doi>10.1137/S0097539796307698]
• 20: Piotr Zielinski. Automatic classification of eventual failure detectors. In DISC 2007, Lemesos, Cyprus, September 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Theory

Keywords:
failure detectors, set agreement, wait-free impossibilities, weakest failure detector ever