Abstract
Failure detectors of the class denoted \(\mathcal{P}^t\) eventually suspect all crashed processes in a permanent way (completeness) and ensure that, at any time, no more than n – t – 1 alive processes are falsely suspected (accuracy), n being the total number of processes. This paper first shows that a simple combination of such a failure detector with a two-step communication pattern can provide the processes with an interesting intersection property on sets of values. As an example illustrating the benefit and the property that such a combination can provide when designing protocols, a leader-based consensus protocol whose design relies on its systematic use is presented. Then the paper presents a \(\mathcal{P}^t\)-based protocol that builds quorums in systems where up to t processes can crash with t < n.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anceaume, E., Fernandez, A., Mostéfaoui, A., Neiger, G., Raynal, M.: Necessary and Sufficient Condition for Transforming Limited Accuracy Failure Detectors. Journal of Computer and System Science (JCSS) 68, 123–133 (2004)
Attiya, H., Bar-Noy, A., Dolev, D.: Sharing Memory Robustly in Message Passing Systems. Journal of the ACM 42(1), 121–132 (1995)
Bermond, J.-C., Koenig, J.-C., Raynal, M.: Generalized and Efficient Decentralized Consensus Protocols. In: van Leeuwen, J. (ed.) WDAG 1987. LNCS, vol. 312, pp. 41–56. Springer, Heidelberg (1988)
Chandra, T., Hadzilacos, V., Toueg, S.: The Weakest Failure Detector for Solving Consensus. Journal of the ACM 43(4), 685–722 (1996)
Chandra, T.D., Toueg, S.: Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43(2), 225–267 (1996)
Chu, F.: Reducing Ω to \(\diamondsuit\) W. Information Processing Letters 76(6), 293–298 (1998)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: A Realistic Look at Failure Detectors. In: Proc. Int. Conference on Dependable Systems and Networks (DSN 2002), pp. 354–353 (2002)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: Failure Detection Lower Bounds on Registers and Consensus. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 237–251. Springer, Heidelberg (2002)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: Shared Memory vs Message Passing. Technical Report, IC/2003/77, EPFL, Lausanne, Switzerland (2003)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Hadzilacos, V., Kouznetzov, P., Toueg, S.: The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing. In: 23th ACM Int. Symp. on Principles of Distributed Computing, pp. 338–346 (2004)
Fischer, M.J., Lynch, N., Paterson, M.S.: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 374–382 (1985)
Friedman, R., Mostéfaoui, A., Raynal, M.: A Weakest Failure Detector-Based Asynchronous Consensus Protocol for f < n. Information Processing Letters 90(1), 39–46 (2004)
Guerraoui, R.: Non-Blocking Atomic Commit in Asynchronous Distributed Systems with Failure Detectors. Distributed Computing 15, 17–25 (2002)
Guerraoui, R., Kouznetsov, P.: On the Weakest Failure Detector for Non-Blocking Atomic Commit. In: Proc. 2nd Int. IFIP Conf. on Theoretical Computer Science, pp. 461–473 (2002)
Guerraoui, R., Raynal, M.: The Information Structure of Indulgent Consensus. IEEE Transactions on Computers 53(4), 453–466 (2004)
Keidar, I., Dolev, D.: Increasing the Resilience of Distributed and Replicated Database Systems. Journal of Computer and System Sciences 57(3), 309–324 (1998)
Lakshman, T.V., Agrawala, A.K.: Efficient Decentralized Consensus Protocols. IEEE Transactions on Software Engineering SE12(5), 600–607 (1986)
Lamport, L.: The Part-Time Parliament. ACM TOCS 16(2), 133–169 (1998)
Lo, W.-K., Hadzilacos, V.: Using Failure Detectors to Solve Consensus in Asynchronous Shared-Memory Systems. In: Tel, G., Vitányi, P.M.B. (eds.) WDAG 1994. LNCS, vol. 857, pp. 280–295. Springer, Heidelberg (1994)
Mostéfaoui, A., Raynal, M.: Solving Consensus Using Chandra-Toueg’s Unreliable Failure Detectors: a General Quorum-Based Approach. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 49–63. Springer, Heidelberg (1999)
Mostéfaoui, A., Raynal, M.: Leader-Based Consensus. Parallel Processing Letters 11(1), 95–107 (2001)
Skeen, D.: Non-Blocking Commit Protocols. In: Proc. ACM SIGMOD Int. Conference on Management of Data, pp. 133–142. ACM Press, New York (1981)
Thomas, R.H.: A Majority Consensus Approach to Concurrency Control for Multiple Copies Databases. ACM Transactions on Database Systems 4(2), 180–209 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Friedman, R., Mostefaoui, A., Raynal, M. (2005). Building and Using Quorums Despite any Number of Process of Crashes. In: Dal Cin, M., Kaâniche, M., Pataricza, A. (eds) Dependable Computing - EDCC 5. EDCC 2005. Lecture Notes in Computer Science, vol 3463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11408901_2
Download citation
DOI: https://doi.org/10.1007/11408901_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25723-3
Online ISBN: 978-3-540-32019-7
eBook Packages: Computer ScienceComputer Science (R0)