Abstract
This paper tackles the consensus problem in asynchronous systems prone to byzantine failures. One way to circumvent the FLP impossibility result consists in adding synchrony assumptions (deterministic solution). In the context of crash failures (at most t processes may crash), the weakest partially synchronous system model assumes at least one correct process with outgoing links that eventually permit a bounded transmission delay with at least t neighbors (the set of neighbors may change over time).
Aguilera et al. provided the main result for systems where at most t processes may exhibit a byzantine behavior. They assume a correct process with all its outgoing and incoming links eventually timely. This paper considers a system model with at least one correct process connected with x privileged neighbors with eventually timely outgoing and incoming links. In this system model, a byzantine consensus protocol is proposed. It uses authentication and assumes x ≥ 2t.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aguilera, M.K., Chen, W., Toueg, S.: Heartbeat: a timeout-free failure detector for quiescent reliable communication. In: Mavronicolas, M. (ed.) WDAG 1997. LNCS, vol. 1320, pp. 126–140. Springer, Heidelberg (1997)
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Communication-efficient leader election and consensus with limited link synchrony. In: PODC 2004. Proc. 23nd ACM Symposium on Principles of Distributed Computing, ACM Press, New York (2004)
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Consensus with byzantine failures and little system synchrony. In: DSN 2006. Proc. International Conference on Dependable Systems and Networks, Philadelphia (2006)
Basu, A., Charron-Bost, B., Toueg, T.: Crash failures vs. crash + link failures. In: PODC 1996. Proc 15th ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania (1996)
Ben-Or, M.: Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. In: PODC 1983. Proc. 2nd ACM Symposium on Principles of Distributed Computing, pp. 27–30. ACM Press, New York (1983)
Boichat, B., Dutta, P., Frölund, S., Guerraoui, G.: Deconstructing paxos. SIGACT News in Distributed Computing 34(1), 47–67 (2003)
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proc. of the 3rd Symposium on Operating Systems Design and Implementation, New Orleans, USA (February 1999)
Chandra, T.D., Toueg, S.: Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43(2), 225–267 (1996)
Correia, M., Neves, N.F., Lung, L.C., Verissimo, P.: Low Complexity Byzantine-Resilient Consensus. Distributed Computing 17, 13 (2004)
Doudou, A., Garbinato, B., Guerraoui, R.: Encapsulating Failure Detection: from Crash to Byzantine Failures. In: Proc. International Conference on Reliable Software Technologies, Vienna (Austria) (2002)
Dutta, P., Guerraoui, R., Vukolic, M.: Best-case complexity of asynchronous byzantine consensus. Technical Report EPFL/IC/200499, EPFL (February 2005)
Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. Journal of the ACM 35(2), 288–323 (1988)
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., Mostefaoui, A., Raynal, M.: Simple and efficient oracle-based consensus protocols for asynchronous byzantine systems. IEEE Transactions on Dependable and Secure Computing 2(1), 46–56 (2005)
Hutle, M., Malkhi, D., Schmid, U., Zhou, L.: Chasing the Weakest System Model for Implementing Omega and Consensus. Research Report 74/2005, Technische Universität Wien, Institut für Technische Informatik (July 2006)
Kihlstrom, K.P., Moser, L.E., Melliar-Smith, P.M.: Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector. In: OPODIS 1997. Proc. of the Int. Conference on Principles of Distributed Systems, pp. 61–75 (1997)
Kursawe, K.: Optimistic Byzantine agreement. In: SRDS 2002 Workshops. Proc. of the 21st IEEE Symposium on Reliable Distributed Systems (2002)
Lamport, L.: Lower bounds for asynchronous consensus. Distributed Computing 19(2), 104–125 (2006)
Malkhi, D., Oprea, F., Zhou, L.: Ω meets paxos: Leader election and stability without eventual timely links. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 26–29. Springer, Heidelberg (2005)
Martin, J.P., Alvisi, L.: Fast Byzantine paxos. In: DSN 2005. Proc. International Conference on Dependable Systems and Networks, Yokohama, Japan, pp. 402–411 (2005)
Pease, L., Shostak, R., Lamport, L.: Reaching Agreement in Presence of Faults. Journal of the ACM 27(2), 228–234 (1980)
Rabin, M.: Randomized Byzantine Generals. In: FOCS 1983. Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 403–409. IEEE Computer Society Press, Los Alamitos (1983)
Schneider, F.B.: Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys 22(4), 299–319 (1990)
Srikanth, T.K., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing 2(2), 380–394 (1987)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hamouma, M., Mostefaoui, A., Trédan, G. (2007). Byzantine Consensus with Few Synchronous Links. In: Tovar, E., Tsigas, P., Fouchal, H. (eds) Principles of Distributed Systems. OPODIS 2007. Lecture Notes in Computer Science, vol 4878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77096-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-77096-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77095-4
Online ISBN: 978-3-540-77096-1
eBook Packages: Computer ScienceComputer Science (R0)