Failure detectors in loosely named systems

ABSTRACT

This paper explores the power of failure detectors in read write shared memory systems with n processes whose names are drawn from the set {1...m}, m>=2n-1. We do so by making an additional assumption, name obliviousness, on top of the three failure detector assumptions introduced by ZieliDski. We present name non-oblivious failure detectors that are strong enough to wait-free solve the Symmetry Breaking (SB) problem, but not enough to solve the (n-1)-Set Consensus problem. Furthermore a family of weakest such failure detectors is presented. On the other hand we show that any non trivial name oblivious failure detector can wait-free solve (n-1)-Set Consensus, by introducing a simple extension to anti-Omega, the Loose-anti-Omega failure detector, and proving that it is the weakest failure detector that conforms to the four assumptions above.

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: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.147-158, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135451]
• 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: 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]
• 5: Chen W., Chen Y., Zhang J., On failure detectors weaker than ever. Technical Report MSR-TR-2007-50, Microsoft Research, may 2007.
• 6: Gafni E., Rajsbaum S., Herlihy M., Subconsensus tasks: Renaming is weaker than set agreement. In Dolev S., editor, DISC, volume 4167 of Lecture Notes in Computer Science, 329--338. Springer, 2006.
• 7: Gordon D.M., Kuperberg G., Patashnik O., New constructions for covering designs. In J. Combin. Designs 3, 269-284, 1995.
• 8: 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]
• 9: 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]
• 10: 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
• 11: 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]
• 12: Schönheim J., On coverings. Pacific Journal of Mathematics, 1405--1411, 1964.
• 13: Jiong Yang , Gil Neiger , Eli Gafni, Structured derivations of consensus algorithms for failure detectors, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.297-306, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277755]
• 14: Zielinski, P. Automatic Classification of Eventual Failure Detectors. In Proceedings of the 21st International Symposium on Distributed Computing (DISC), Andrzej Pelc, editor, volume 4731 of Lecture Notes on Computer Science, 465-479. Springer 2007.
• 15: 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:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

General Terms:
Algorithms, Theory

Keywords:
anti-omega, failure detectors, loosely named systems, set consensus, symmetry breaking, wait-free