-BASED CONSENSUS for ASYNCHRONOUS BYZANTINE SYSTEMS
Abstract
This paper presents a consensus protocol for asynchronous distributed systems made up of n processes, where up to f<n/4 processes can behave arbitrarily (Byzantine processes). The protocol assumes that the underlying system is equipped with an unreliable failure detector of the class
. The failure detectors of the class
ensure that (1) all mute processes are detected (a mute process is a process that, after some time, stops sending protocol messages), and (2) after some unknown but finite time, no correct process is suspected (mute processes are a subset of the Byzantine processes). The proposed protocol enjoys the following properties. It is based on the round coordinator paradigm and its design principle is particularly simple. Its message complexity is O(n2) per round. In addition to a round number, the message size is O(1), except for one message per round (sent by the round coordinator) whose size is O(n). The protocol does not use message "proofs", certificates, or application level signatures. When no process is faulty, all processes propose the same value, and the failure detector makes no mistake, the processes decide in one round (4 communication steps). Finally, when a process decides, it only needs a simple unreliable broadcast mechanism to prevent the other processes from deadlocking. All these features make the protocol attractive to cope with the net effect of Byzantine failures and asynchrony.
References
- The JazzEnsemble home page. www.cs.technion.ac.il/Labs/dsl/projects/JazzEnsemble/index.html . Google Scholar
M. Ben-Or , Proc. 2nd ACM Symposium on Principles of Distributed Computing (PODC'83) (ACM Press, Montral (Canada), 1983) pp. 27–30. Crossref, Google Scholar- Mathematical System Theory 26(1), 3 (1993). Crossref, Google Scholar
- Berman P. and Garay J. A., Randomized Distributed Agreement Revisited, Proc. Int'l Conference on Fault-Tolerant Computing (FTCS-23), pp. 412-419, 1993 . Google Scholar
G. Bracha , Proc. 3rd ACM Symposium on Principles of Distributed Computing (PODC'84) (ACM Press, Vancouver (Canada), 1984) pp. 154–162. Crossref, Google Scholar- IEEE Transactions on Parallel and Distributed Systems 10(6), 642 (1999). Crossref, ISI, Google Scholar
- Journal of the ACM 43(2), 225 (1996). Crossref, ISI, Google Scholar
- Doudou A., Garbinato B. and Guerraoui R., Encapsulating Failure Detection: from Crash to Byzantine Failures. Proc. Int'l Conference on Reliable Software Technologies, Vienna (Austria), 2002 . Google Scholar
A. Doudou , Proc. 3rd European Dependable Computing Conference (EDCC'99),LNCS #1667 (Springer-Verlag, 1999) pp. 71–87. Google ScholarA. Doudou and A. Schiper , Brief Announcement in Proc. 17th ACM Symposium on Principles of Distributed Computing (PODC'98) (ACM Press, Puerto Vallarta (MX), 1998) p. 315. Crossref, Google Scholar- Journal of the ACM 32(2), 374 (1985). Crossref, ISI, Google Scholar
R. Friedman , A. Mostefaoui and M. Raynal , Proc. 23th IEEE Symposium on Reliable Distributed Systems (SRDS'04) (IEEE Computer Society Press, Florianpolis (Brazil), 2004) pp. 228–237. Google Scholar- Gallenni A. and Powell D., Consensus and Membership in Synchronous and Asynchronous Distributed Systems, LAAS Report 96104, 1996 . Google Scholar
- Kihlstrom K. P., Moser L. E., and Melliar-Smith P. M., Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector, Proc. of the Int. Conference on Principles of Distributed Systems (OPODIS), pp. 61-75, 1997 . Google Scholar
- Journal of the ACM 27(2), 228 (1980). Crossref, ISI, Google Scholar
M. Rabin , Proc. 24th IEEE Symposium on Foundations of Computer Science (FOCS'83) (IEEE Computer Society Prass, Tucson (AZ), 1983) pp. 403–409. Google Scholar- ACM Computing Surveys 22(4), 299 (1990). Crossref, ISI, Google Scholar
S. Toueg , Proc. 3th ACM Symposium on Principles of Distributed Computing (PODC'84) (ACM Press, Vancouver (Canada), 1984) pp. 163–178. Crossref, Google Scholar


