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)
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)
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)
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)
7. 7.
Chaudhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Information and Computation 105, 132–158 (1993)
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)
9. 9.
Dolev, D., Reischuk, R., Strong, R.: Early Stopping in Byzantine Agreement. Journal of the ACM 37(4), 720–741 (1990)
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)
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)
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)
17. 17.
Herlihy, M.P., Shavit, N.: The Topological Structure of Asynchronous Computability. Journal of the ACM 46(6), 858–923 (1999)
18. 18.
Keidar, I., Rajsbaum, S.: A Simple Proof of the Uniform Consensus Synchronous Lower Bound. Information Processing Letters 85, 47–52 (2003)
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)
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)
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)
23. 23.
Neiger, G., Toueg, S.: Automatically Increasing the Fault-Tolerance of Distributed Algorithms. Journal of Algorithms 11, 374–419 (1990)
24. 24.
Pease, L., Shostak, R., Lamport, L.: Reaching Agreement in Presence of Faults. Journal of the ACM 27(2), 228–234 (1980)
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)
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)
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)
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)
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)
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)

© 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