Advertisement

Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures

  • Philippe Raïpin Parvédy
  • Michel Raynal
  • Corentin Travers
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

Abstract

The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, in the crash failure model, min\((\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)\) is a lower bound on the number of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f, 0 ≤ft, the actual number of crashes).

This paper considers the k-set agreement problem in synchronous systems where up to t < n /2 processes can experience general omission failures (i.e., a process can crash or omit sending or receiving messages). It first introduces a new property, called strong termination. This property is on the processes that decide. It is satisfied if, not only every non-faulty process, but any process that neither crashes nor commits receive omission failures decides. The paper then presents a k-set agreement protocol that enjoys the following features. First, it is strongly terminating (to our knowledge, it is the first agreement protocol to satisfy this property, whatever the failure model considered). Then, it is early deciding and stopping in the sense that a process that either is non-faulty or commits only send omission failures decides and halts by round min\((\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)\). To our knowledge, this is the first early deciding k-set agreement protocol for the general omission failure model. Moreover, the protocol provides also the following additional early stopping property: a process that commits receive omission failures (and does not crash) executes at most min\((\lceil \frac{f}{k} \rceil +2,\lfloor \frac{t}{k} \rfloor +1)\) rounds. It is worth noticing that the protocol allows each property (strong termination vs early deciding/stopping vs early stopping) not to be obtained at the detriment of the two others.

The combination of the fact that min\((\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)\) is lower bound on the number of rounds in the crash failure model, and the very existence of the proposed protocol has two very interesting consequences. First, it shows that, although general omission failure model is more severe than the crash failure model, both models have the same lower bound for the non-faulty processes to decide. Second, it shows that, in the general omission failure model, that bound applies also the processes that commit only send omission failures.

Keywords

Agreement problem Crash failure Strong Termination Early decision Early stopping Efficiency k-set agreement Message-passing system Receive omission failure Round-based computation Send omission failure Synchronous system 

References

  1. 1.
    Aguilera, M.K., Toueg, S.: A Simple Bivalency Proof that t-Resilient Consensus Requires t + 1 Rounds. Information Processing Letters 71, 155–178 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Attiya, H., Welch, J.: Distributed Computing, Fundamentals, Simulation and Advanced Topics, 2nd edn. Wiley Series on Parallel and Distributed Computing, pages 414 (2004)Google Scholar
  3. 3.
    Biran, O., Moran, S., Zaks, S.: A Combinatorial Characterization of the Distributed 1-Solvable Tasks. Journal of Algorithms 11(3), 420–440 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Biran, O., Moran, S., Zaks, S.: Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks. Theoretical Computer Science 145(1-2), 271–290 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Borowsky, E., Gafni, E., Generalized, F.L.P.: Impossibility Results for t-Resilient Asynchronous Computations. In: Proc. 25th ACM Symposium on Theory of Computation (STOC 1993), California (USA), pp. 91–100 (1993)Google Scholar
  6. 6.
    Charron-Bost, B., Schiper, A.: Uniform Consensus is Harder than Consensus. Journal of Algorithms 51(1), 15–37 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Chaudhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Information and Computation 105, 132–158 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Chaudhuri, S., Herlihy, M., Lynch, N., Tuttle, M.: Tight Bounds for k-Set Agreement. Journal of the ACM 47(5), 912–943 (2000)CrossRefMathSciNetGoogle Scholar
  9. 9.
    Dolev, D., Reischuk, R., Strong, R.: Early Stopping in Byzantine Agreement. Journal of the ACM 37(4), 720–741 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  10. 10.
    Fischer, M.J., Lynch, N.A.: A Lower Bound on the Time to Assure Interactive Consistency. Information Processing Letters 14(4), 183–186 (1982)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 374–382 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Gafni, E., Guerraoui, R., Pochon, B.: >From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement. In: Proc. 37th ACM Symposium on Theory of Computing (STOC 2005), Baltimore (MD), pp. 714–722 (May 2005)Google Scholar
  13. 13.
    Guerraoui, R., Pochon, B.: The Complexity of Early Deciding Set Agreement: how Topology Can Help? In: Proc. 4th Workshop in Geometry and Topology in Concurrency and Distributed Computing (GETCO 2004), BRICS Notes Series, NS-04-2, Amsterdam (NL), pp. 26-31 (2004)Google Scholar
  14. 14.
    Hadzilacos, V.: Issues of Fault Tolerance in Concurrent Computations. PhD Thesis, Tech Report 11-84, Harvard University, Cambridge (MA) (1985)Google Scholar
  15. 15.
    Hadzilacos, V., Toueg, S.: Reliable Broadcast and Related Problems. In: Mullender, S. (ed.) Distributed Systems, pp. 97–145. ACM Press, New York (1993)Google Scholar
  16. 16.
    Herlihy, M.P., Penso, L.D.: Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors. Distributed Computing 18(2), 157–166 (2005)CrossRefGoogle Scholar
  17. 17.
    Herlihy, M.P., Shavit, N.: The Topological Structure of Asynchronous Computability. Journal of the ACM 46(6), 858–923 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Keidar, I., Rajsbaum, S.: A Simple Proof of the Uniform Consensus Synchronous Lower Bound. Information Processing Letters 85, 47–52 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Lamport, L., Fischer, M.: Byzantine Generals and Transaction Commit Protocols, p. 16 (April 1982) (unpublished manuscript)Google Scholar
  20. 20.
    Lynch, N.A.: Distributed Algorithms, p. 872. Morgan Kaufmann, San Fransisco (CA) (1996)zbMATHGoogle Scholar
  21. 21.
    Mostéfaoui, A., Raynal, M.: k-Set Agreement with Limited Accuracy Failure Detectors. In: Proc. 19th ACM Symposium on Principles of Distributed Computing (PODC 2000), pp. 143–152. ACM Press, Portland, OR (2000)CrossRefGoogle Scholar
  22. 22.
    Mostéfaoui, A., Raynal, M.: Randomized Set Agreement. In: Proc. 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Hersonissos (Crete), pp. 291–297. ACM Press, New York (2001)CrossRefGoogle Scholar
  23. 23.
    Neiger, G., Toueg, S.: Automatically Increasing the Fault-Tolerance of Distributed Algorithms. Journal of Algorithms 11, 374–419 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  24. 24.
    Pease, L., Shostak, R., Lamport, L.: Reaching Agreement in Presence of Faults. Journal of the ACM 27(2), 228–234 (1980)zbMATHCrossRefMathSciNetGoogle Scholar
  25. 25.
    Perry, K.J., Toueg, S.: Distributed Agreement in the Presence of Processor and Communication Faults. IEEE Transactions on Software Eng. SE-12(3), 477–482 (1986)Google Scholar
  26. 26.
    Raípin Parvédy, P., Raynal, M.: Optimal Early Stopping Uniform Consensus in Synchronous Systems with Process Omission Failures. In: Proc. 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA 2004), Barcelona (Spain), pp. 302–310. ACM Press, New York (2004)CrossRefGoogle Scholar
  27. 27.
    Raïpin Parvédy, P., Raynal, M., Travers, C.: Early-Stopping k-Set Agreement in Synchronous Systems Prone to Any Number of Process Crashes. In: Malyshkin, V.E. (ed.) PaCT 2005. LNCS, vol. 3606, pp. 49–58. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  28. 28.
    Raípin Parvédy, P., Raynal, M., Travers, C.: Decision Optimal Early-Stopping k-set Agreement in Synchronous Systems Prone to Send Omission Failures. In: Proc. 11th IEEE Pacific Rim Int. Symposium on Dependable Computing (PRDC 2005), Changsa (China), pp. 23–30. IEEE Computer Press, Los Alamitos (2005)CrossRefGoogle Scholar
  29. 29.
    Raïpin Parvédy P., Raynal M., Travers C.: Strongly Terminating Early-Stopping k-set Agreement in Synchronous Systems with General Omission Failures. Tech Report #1711, IRISA, Université de Rennes (France), pages 22 (2005), ftp://ftp.irisa.fr/techreports/2005/PI-1711.ps.gz
  30. 30.
    Raynal, M.: Consensus in Synchronous Systems: a Concise Guided Tour. In: Proc. 9th IEEE Pacific Rim Int. Symposium on Dependable Computing (PRDC 2002), pp. 221–228. IEEE Computer Press, Tsukuba (Japan) (2002)CrossRefGoogle Scholar
  31. 31.
    Saks, M., Zaharoglou, F.: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM Journal on Computing 29(5), 1449–1483 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  32. 32.
    Yang, J., Neiger, G., Gafni, E.: Structured Derivations of Consensus Algorithms for Failure Detectors. In: Proc. 17th Int. ACM Symposium on Principles of Distributed Computing (PODC 1998), Puerto Vallarta (Mexico), July 1998, pp. 297–308. ACM Press, New York (1998)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Philippe Raïpin Parvédy
    • 1
  • Michel Raynal
    • 1
  • Corentin Travers
    • 1
  1. 1.IRISA, Université de Rennes 1RennesFrance

Personalised recommendations