The disagreement power of an adversary: extended abstract

ABSTRACT

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t+1. In other words, an adversary that can crash any subset of size at most t can prevent the processes from agreeing on t values. But what about the rest (2²ⁿ − n) adversaries that might crash certain combination of processes and not others?

This paper presents a precise way to characterize such adversaries by introducing the notion of disagreement power: the biggest integer k for which the adversary can prevent processes from agreeing on k values. We show how to compute the disagreement power of an adversary and how this notion enables to derive n classes of adversaries.

We use our characterization to also close the question of the weakest failure detector for k-set agreement. So far, the result has been obtained for two extreme cases: consensus and n−1-set agreement. We answer this question for any k.

REFERENCES

• 1: A. F. Anta, S. Rajsbaum, and C. Travers. Weakest failure detectors via an egg-laying simulation (preliminary version). Tech Report 2, Systems and Communications, Jan. 2009. Also appears as a brief announcement in PODC 2009.
• 2: 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]
• 3: 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]
• 4: Ashwinkumar B.V , Arpita Patra , Ashish Choudhary , Kannan Srinathan , Chandrasekharan Pandu Rangan, On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400768]
• 5: Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus, SIAM Journal on Computing, v.34 n.2, p.333-357, 2005 [doi>10.1137/S0097539798344367]
• 6: 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]
• 7: Matthias Fitzi , Ueli M. Maurer, Efficient Byzantine Agreement Secure Against General Adversaries, Proceedings of the 12th International Symposium on Distributed Computing, p.134-148, September 24-26, 1998
• 8: 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]
• 9: 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]
• 10: Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258652]
• 11: 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]
• 12: F. P. Junqueira and K. Marzullo. Designing algorithms for dependent process failures. In Future Directions in Distributed Computing, pages 24--28, 2003.
• 13: 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
• 14: 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]
• 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, Reliability, Theory

Keywords:
adversaries, failure-detectors, fault-tolerance