Brief announcement: weakest failure detectors via an egg-laying simulation

ABSTRACT

In the k-set agreement task, n processes propose values, and have to decide on at most k of these values. In particular, consensus is 1-set agreement. In PODC 2008 Zieliński showed that the anti-Ω failure detector is necessary and sufficient to solve (n − 1)-set agreement in an asynchronous read/write shared memory system where at most n − 1 processes can fail by crashing.

This paper generalizes Zieliński's result: it shows that anti-Ω^t is the weakest failure detector to solve t-set agreement in a t-resilient asynchronous distributed system. Each query to antiΩ^t returns a set S of process ids, |S| = n − t, such that some correct process eventually never appears in any such set S; thus, anti-Ωⁿ⁻¹ = anti-Ω, and anti-Ω¹ = Ω. Actually, the paper shows a stronger result: Any failure detector that can be used to solve T is at least as strong as anti-Ω^t, for any agreement task T that has no t-resilient solution.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011818]
• 6: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Andreas Tielmann, The Weakest Failure Detector for Message Passing Set-Agreement, Proceedings of the 22nd international symposium on Distributed Computing, September 22-24, 2008, Arcachon, France [doi>10.1007/978-3-540-87779-0_8]
• 7: 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]
• 8: Antonio Fernández Anta, Sergio Rajsbaum, Corentin Travers: Weakest Failure Detectors via an Egg-laying Simulation (Preliminary Version). Reports on Systems and Communications, vol IX, no 2, Jan 2009. http://gsyc.es/tr-docs/RoSaC-2009-2.pdf
• 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 , Petr Kuznetsov, The weakest failure detector for solving k-set agreement, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582735]
• 11: 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]
• 12: Maurice Herlihy , Lucia Draque Penso, Tight bounds for k-set agreement with limited-scope failure detectors, Distributed Computing, v.18 n.2, p.157-166, December 2005 [doi>10.1007/s00446-005-0141-8]
• 13: 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]
• 14: Michel Raynal, Corentin Travers: In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-Free Set Agreement. OPODIS 2006
• 15: 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]
• 16: Piotr Zieliński. Automatic Classification of Eventual Failure Detectors. DISC 2007: 465--479.
• 17: 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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Reliability, Theory

Keywords:
distributed computing, failure detectors, lower bounds, shared memory, wait-free