k-set agreement with limited accuracy failure detectors

ABSTRACT

Let the scope of the accuracy property of an unreliable failure detector be the number x of processes that may not suspect a correct process. The scope notion gives rise to new classes of failure detectors among which we consider S_x and ⋄S_x in this paper (Usual failure detectors consider an implicit scope equal to n, the total number of processes).

The k-set agreement problem generalizes the consensus problem: each correct process has to decide a value in such a way that a decided value is a proposed value, and the number of decided values is bounded by k. There exist protocols that solve this problem in asynchronous distributed systems when ƒ < k (where ƒ is the maximum number of processes that may crash). Moreover, it has been shown that there is no solution in those systems when ƒ ≥ k.

The paper considers asynchronous distributed systems equipped with limited scope accuracy failure detectors. It studies conditions on n, ƒ, k and x that allow to solve the k-set agreement problem in those systems and presents two protocols. The first protocol solves the k-set agreement in asynchronous distributed systems augmented with a failure detector of the class S_x. It requires ƒ < k + x - 1. The second protocol works with any failure detector of the class ⋄S_x. It actually defines a family of protocols. This family allows to solve the k-set agreement problem when ƒ < max(k, max_1≤α≤k(min(n - α⌊n/(α + 1)⌋, α +x - 1))). We conjecture that, when ƒ ≥ k, these conditions are necessary to solve the k-set agreement problem in asynchronous distributed systems equipped with failure detectors ε S_x or ⋄S_x, respectively.

References

1. 1.Anceaume E., FernAndez A., Mostefaoui A. and Raynal M., A Necessary and Sufficient Condition for Transforming Limited Accuracy Failure Detectors. Research Report #1287, IRISA, Universit~ de Rennes, 15 pages, 1999 (Submitted to publication).]]
2. 2.Borowsky E. and Gafni E., Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations. Proc. 25th A CM Symposium on Theory of Computation, California (USA), pp. 91-100, 1993.]]
3. 3.Chandra T. and Toueg S., Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the A CM, 43(2):225-267, March 1996.]]
4. 4.Chandra T., Hadzilacos V. and Toueg S., The Weakest Failure Detector for Solving Consensus. Journal of the ACM, 43(4):685-722, July 1996.]]
5. 5.Chaudhuri S., Agreement is Harder than Consensus: Set Consensus Problems in Totally Asynchronous Systems. Proc. 9th A CM Symposium on Principles of Distributed Computing, Qudbec (Canada), pp. 311-324, 1990.]]
6. 6.Fischer M.J., Lynch N. and Paterson M.S., Impossibility of Distributed Consensus with One Faulty Process. Journal of the A CM, 32(2):374-382, April 1985.]]
7. 7.Greve F., Hurfin M., Mac~do R. and Raynal M., Time and Message-Efficient S-Based Consensus. Brief Announcement, Proc. l gth A CM Symposium on Principles of Distributed Computing, This Volume, July 2000. Full version: http://www.irisa, fr/EXTE RNE/bi bli / pi / 1290 / 1290. ht m I.]]
8. 8.Herlihy M. and Shavit N., The Asynchronous Computability Theorem for t-Resilient Tasks. Proc. 25th A CM Symposium on Theory of Computation, California (USA), pp. 111-120, 1993.]]
9. 9.Hurfin M. and Raynal M., A Simple and Fast Asynchronous Consensus Protocol Based on a Weak Failure Detector. Distributed Computing, 12(4):209-223, 1999.]]
10. 10.Mostefaoui A. and Raynal M., Solving Consensus Using Chandra-Toueg's Unreliable Failure Detectors: a Generic Quorum-Based Approach. Proc. 13th Int. Symposium on Distributed Computing (DISC'99), (Formerly WDAG), Springer-Verlag LNCS #1693 (P. Jayanti Ed.), pp. 49-64, Bratislava (Slovakia), 1999.]]
11. 11.Mostefaoui A. and Raynal M., Unreliable Failure Detectors with Limited Scope Accuracy and an Application to Consensus. Proc. 19th Int. Conference on Foundations of Software Technology and Theoretical Computer Science (FSTfATCS'99), Springer-Verlag LNCS #1738 (Raman V. and Ramanujan R Ed.), pp. 329-340, Chennai (India), December 1999.]]
12. 12.Mostefaoui A. and Raynal M., Consensus Based on Failure Detectors with a Perpetual Weak Accuracy Property. To appear in Proc. Int. Parallel and Distributed Processing Symposium (IPDPS'O0), (1Jth IPPS//llth SPDP), Cancun (Mexico), May 2000.]]
13. 13.Raynal M. and Tronel F., Restricted Failure Detectors: Definition and Reduction Protocols. Information Processing Letters, 72:91-97, 1999.]]
14. 14.Saks M. and Zaharoglou F,, Wait-Free k-Set Agreement is Impossible: the Topology of Public Knowledge. Proc. 25th A CM Symposium on Theory of Computation, California (USA), pp. 101-110, 1993.]]
15. 16.Yang J., Neiger G. and Gafni E., Structured Derivations of Consensus Algorithms for Failure Detectors. Proc. 17th A CM Symposium on Principles of Distributed Computing, Puerto Vallarta (Mexico), pp.297-308, 1998.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

    • Software system structures

      • Distributed systems organizing principles