The weakest failure detector for solving k-set agreement

ABSTRACT

A failure detector is a distributed oracle that provides processes in a distributed system with hints about failures. The notion of a weakest failure detector captures the exact amount of synchrony needed for solving a given distributed computing problem.

In this paper, we determine the weakest failure detector for solving k-set agreement among n processes (n > k) using reads and writes in shared memory, regardless of the assumptions on when and where failures might occur. This failure detector is derived directly from the impossibility of wait-free k + 1-process k-set agreement. Our approach can be viewed as an extension of the asynchronous BG-simulation technique to partially synchronous systems.

REFERENCES

• 1: Yehuda Afek, Eli Gafni, Sergio Rajsbaum, Michel Raynal, and Corentin Travers. Simultaneous consensus tasks: A tighter characterization of set-consensus. In ICDCN, pages 331--341, 2006.
• 2: Antonio Fernández Anta, Sergio Rajsbaum, and Corentin Travers. Weakest failure detectors via an egg-laying simulation (brief announcement). In PODC, 2009.
• 3: 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]
• 4: 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]
• 5: E. Borowsky , E. Gafni , N. Lynch , S. Rajsbaum, The BG distributed simulation algorithm, Distributed Computing, v.14 n.3, p.127-146, October, 2001 [doi>10.1007/PL00008933]
• 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: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 8: Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93431]
• 9: Wei Chen, Jialin Zhang, Yu Chen, and Xuezheng Liu. Weakening failure detectors for k-set agreement via the partition approach. In DISC, pages 123--138, 2007.
• 10: Francis Chu, Reducing &OHgr; to ◊W , Information Processing Letters, v.67 n.6, p.289-293, Sept. 30, 1998 [doi>10.1016/S0020-0190(98)00122-7]
• 11: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Andreas Tielmann, The disagreement power of an adversary: extended abstract, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582769]
• 12: 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]
• 13: 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]
• 14: Rachid Guerraoui, Maurice Herlihy, Petr Kuznetsov, Nancy A. Lynch, and Calvin C. Newport. On the weakest failure detector ever. Distributed Computing, 21(5):353--366, February 2009.
• 15: Rachid Guerraoui and Petr Kuznetsov. Failure detectors as type boosters. Distributed Computing, 20(5):343--358, 2008.
• 16: Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
• 17: Prasad Jayanti , Sam Toueg, Every problem has a weakest failure detector, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400763]
• 18: Petr Kuznetsov. Simple CHT: A new derivation of the weakest failure detector for consensus. Technical Report 2009-05, TU Berlin, February 2009. http://www.net.t-labs.tu-berlin.de/∼petr/pubs/chts.pdf.
• 19: 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
• 20: M.C. Loui and H.H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163--183, 1987.
• 21: Michel Raynal. K-anti-Omega, August 2007. Rump session at PODC 2007.
• 22: Michel Raynal and Corentin Travers. In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement. In OPODIS, pages 3--19, 2006.
• 23: Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]
• 24: Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400761]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

General Terms:
Algorithms, Performance, Theory

Keywords:
BG-simulation, failure detectors, k-set agreement, synchrony assumptions, weakest failure detector