| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
The Information Structure of Indulgent Consensus
April 2004 (vol. 53 no. 4)
pp. 453-466
To solve consensus, distributed systems have to be equipped with oracles such as a failure detector, a leader capability, or a random number generator. For each oracle, various consensus algorithms have been devised. Some of these algorithms are indulgent toward their oracle in the sense that they never violate consensus safety, no matter how the underlying oracle behaves. This paper presents a simple and generic indulgent consensus algorithm that can be instantiated with any specific oracle and be as efficient as any ad hoc consensus algorithm initially devised with that oracle in mind. The key to combining genericity and efficiency is to factor out the information structure of indulgent consensus executions within a new distributed abstraction, which we call "Lambda.” Interestingly, identifying this information structure also promotes a fine-grained study of the inherent complexity of indulgent consensus. We show that instantiations of our generic algorithm with specific oracles, or combinations of them, match lower bounds on oracle-efficiency, zero-degradation, and one-step-decision. We show, however, that no leader or failure detector-based consensus algorithm can be, at the same time, zero-degrading and configuration-efficient. Moreover, we show that leader-based consensus algorithms that are oracle-efficient are inherently zero-degrading, but some failure detector-based consensus algorithms can be both oracle-efficient and configuration-efficient. These results highlight some of the fundamental trade offs underlying each oracle,
[1] 453 M.K. Aguilera and S. Toueg, Failure Detection and Randomization: A Hybrid Approach to Solve Consensus SIAM J. Computing, vol. 28, no. 3, pp. 890-903, 1998.[2] H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, 1998.[3] M. Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols Proc. Second ACM Symp. Principles of Distributed Computing (PODC '83), pp. 27-30, 1983.[4] R. Boichat, P. Dutta, S. Frolund, and R. Guerraoui, Deconstructing Paxos SIGACT News, Distributed Computing Column, 2003.[5] F. Brasileiro, F. Greve, A. Mostefaoui, and M. Raynal, Consensus in One Communication Step Proc. Sixth Int'l Conf. Parallel Computing Technologies (PaCT '01), pp. 42-50, 2001.[6] J. Brzezinsky, J.-M. Hélary, M. Raynal, and M. Singhal, Deadlock Models and a General Algorithm for Distributed Deadlock Detection J. Parallel and Distributed Computing, vol. 31, no. 2, pp. 112-125, 1995.[7] T. Chandra and S. Toueg, Unreliable Failure Detectors for Reliable Distributed Systems J. ACM, vol. 43, no. 2, pp. 225-267, 1996.[8] T. Chandra, V. Hadzilacos, and S. Toueg, The Weakest Failure Detector for Solving Consensus J. ACM, vol. 43, no. 4, pp. 685-722, 1996.[9] B. Chor and L. Nelson, Solvability in Asynchronous Environments: Finite Interactive Tasks SIAM J. Computing, vol. 29, no. 2, pp. 351-377, 1999.[10] F. Chu, Reducing$\Omega$to$\diamondsuit W$ Information Processing Letters, vol. 67, no. 6, pp. 289-293, 1998.[11] P. Dutta and R. Guerraoui, Fast Indulgent Consensus with Zero Degradation Proc. Fourth European Dependable Computing Conf. (EDCC '02), pp. 191-208, 2002.[12] C. Dwork, N. Lynch, and L. Stockmeyer, Consensus in the Presence of Partial Synchrony J. ACM, vol. 35, no. 2, pp. 288-323, 1988.[13] M.J. Fischer, N. Lynch, and M.S. Paterson, Impossibility of Distributed Consensus with One Faulty Process J. ACM, vol. 32, no. 2, pp. 374-382, 1985.[14] E. Gafni, A Round-by-Round Failure Detector: Unifying Synchrony and Asynchrony Proc. 17th ACM Symp. Principles of Distributed Computing (PODC '98), pp. 143-152, 1998.[15] R. Guerraoui, Indulgent Algorithms Proc. 19th ACM Symp. Principles of Distributed Computing (PODC '00), pp. 289-298, 2000.[16] V. Hadzilacos and S. Toueg, Reliable Broadcast and Related Problems Distributed Systems, S. Mullender, ed., pp. 97-145, New-York: ACM Press, 1993.[17] J. Helary, A. Mostefaoui, and M. Raynal, “A General Scheme for Token- and Tree-Based Distributed Mutual Exclusion Algorithms,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 11, pp. 1185-1196, Nov. 1994.[18] M. Hurfin, A. Mostéfaoui, and M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors IEEE Trans. Computers, vol. 51, no. 4, pp, 395-408, Apr. 2002.[19] I. Keidar and S. Rajsbaum, On the Cost of Fault-Tolerant Consensus when There Are No Faults: A Tutorial SIGACT News, Distributed Computing Column, vol. 32, no. 2, pp. 45-63, 2001.[20] A.D. Kshemkalyani and M. Singhal, On the Characterization and Correctness of Distributed Deadlock Detection J. Parallel and Distributed Computing, vol. 22, no. 1, pp. 44-59, 1994.[21] L. Lamport, The Part-Time Parliament ACM Trans. Computer Systems, vol. 16, no. 2, pp. 133-169, 1998.[22] L. Lamport, R. Shostak, and L. Pease, The Byzantine General Problem ACM Trans. Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, 1982.[23] N. Lynch, Distributed Algorithms. San Francisco: Morgan Kaufmann, 1996.[24] A. Mostéfaoui, S. Rajsbaum, and M. Raynal, Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems Proc. 33rd ACM Symp. Theory of Computing (STOC '01), pp. 153-162, 2001.[25] A. Mostéfaoui, S. Rajsbaum, and M. Raynal, A Versatile and Modular Consensus Protocol Proc. Int'l IEEE Conf. Dependable Systems&Networks (DSN '02), pp. 364-373, 2002.[26] A. Mostéfaoui and M. Raynal, Solving Consensus Using Chandra-Toueg's Unreliable Failure Detectors: A General Quorum-Based Approach Proc. 13th Int'l Symp. Distributed Computing (DISC '99), pp. 49-63, 1999.[27] A. Mostéfaoui and M. Raynal, Leader-Based Consensus Parallel Processing Letters, vol. 11, no. 1, pp. 95-107, 2001.[28] A. Mostéfaoui, M. Raynal, and F. Tronel, “The Best of Both Worlds: a Hybrid Approach to Solve Consensus,” Proc. Int'l Conf. Dependable Systems and Networks (DSN '00, previously FTCS), pp. 513-522, June 2000.[29] L. Rodrigues and P. Verissimo, Topology-Aware Algorithms for Large Scale Communications Advances in Distributed Systems, pp. 127-156, Springer-Verlag, 2000.[30] B. Sanders, The Information Structure of Distributed Mutual Exclusion Algorithms ACM Trans. Computer Systems, vol. 5, no. 3, pp. 284-299, 1987.[31] A. Schiper, Early Consensus in an Asynchronous System with a Weak Failure Detector Distributed Computing, vol. 10, pp. 149-157, 1997.
Index Terms:
Asynchronous distributed system, consensus, crash failure, fault tolerance, indulgent algorithm, information structure, leader oracle, modularity, random oracle, unreliable failure detector.
Citation:
Rachid Guerraoui, Michel Raynal, "The Information Structure of Indulgent Consensus," IEEE Transactions on Computers, vol. 53, no. 4, pp. 453-466, Apr. 2004, doi:10.1109/TC.2004.1268403
