World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

formula-BASED CONSENSUS for ASYNCHRONOUS BYZANTINE SYSTEMS

    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. CrossrefGoogle Scholar
    • P. Berman and J. A. Garay, Mathematical System Theory 26(1), 3 (1993). CrossrefGoogle 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. CrossrefGoogle Scholar
    • F. Cristian and C. Fetzer, IEEE Transactions on Parallel and Distributed Systems 10(6), 642 (1999). Crossref, ISIGoogle Scholar
    • T. D. Chandra and S. Toueg, Journal of the ACM 43(2), 225 (1996). Crossref, ISIGoogle 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. Doudouet al., Proc. 3rd European Dependable Computing Conference (EDCC'99), LNCS #1667 (Springer-Verlag, 1999) pp. 71–87. Google Scholar
    • A. 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. CrossrefGoogle Scholar
    • M. J. Fischer, N. Lynch and M. S. Paterson, Journal of the ACM 32(2), 374 (1985). Crossref, ISIGoogle 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
    • L. Pease, R. Shostak and L. Lamport, Journal of the ACM 27(2), 228 (1980). Crossref, ISIGoogle 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
    • F. B. Schneider, ACM Computing Surveys 22(4), 299 (1990). Crossref, ISIGoogle Scholar
    • S. Toueg, Proc. 3th ACM Symposium on Principles of Distributed Computing (PODC'84) (ACM Press, Vancouver (Canada), 1984) pp. 163–178. CrossrefGoogle Scholar