Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
The consensus is a central problem of fault-tolerant distributed computing. Unfortunately, solving such a problem is impossible in asynchronous distributed systems prone to process failures. To circumvent this impossibility (known as FLP impossibility result) in a deterministic way, on top of asynchronous distributed systems enriched with additional assumptions, several protocols have been proposed. Actually, to solve the Byzantine Consensus problem, with a deterministic manner, in systems where at most t processes may exhibit a Byzantine behavior, two approaches have been investigated. The first relies on the addition of synchrony, called Timer-Based, while the second, called Time-Free, is based on the pattern of message exchange. This paper shows that both types of assumptions are not antagonist and can be combined to solve authenticated Byzantine consensus. The combined assumption considers a correct process pi, called ⋄〈t + 1〉-BW, and a set X of t+1 correct processes (including pi itself) such that, eventually, for each query broadcasted by a correct process pj of X, pj receives a response from pi ∈ X among the (n – t) first responses to that query or both links connecting pi and pj are timely. Based on this combination, a simple hybrid authenticated Byzantine consensus protocol benefiting from the best of both worlds is proposed. As a matter of fact, although numerous hybrid protocols have been designed for the consensus problem in the crash model, this is, to our knowledge, the first hybrid deterministic solution to the Byzantine consensus problem.
Wydawca
Czasopismo
Rocznik
Tom
Strony
73--89
Opis fizyczny
Bibliogr. 31 poz., tab.
Twórcy
autor
- Department of Computer Science, University of Bejaia, Bejaia 06000, Algeria
autor
- Department of Computer Science, University of Batna 2, Batna, Algeria
autor
- Department of Computer Science, University of Batna 2, Batna, Algeria
autor
- Department of Mathematics, University of Bejaia, Bejaia 06000, Algeria
Bibliografia
- [1] Fischer MJ, Lynch N, Paterson MS. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 1985. 32(2):374-382. doi:10.1145/3149.214121.
- [2] Dwork C, Lynch NA, Stockmeyer L. Consensus in the presence of partial synchrony. Journal of the ACM, 1988. 35(2):288-323. doi:10.1145/42282.42283.
- [3] Rabin M. Randomized Byzantine generals. ISBN 0-8186-0508-1, 1983 pp. 403-409. doi:10.1109/SFCS.1983.48.
- [4] Ben-Or M. Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. In: acm press (ed.), Proc. 2nd ACM Symposium on Principles of Distributed Computing. 1983 pp. pp. 27-30.
- [5] Mostefaoui A, Moumen H, Raynal M. Signature-free asynchronous binary Byzantine consensus with t¡ n/3, O(n2) messages, and O(1) expected time. Journal of the ACM, 2015. 62(4):21-31. doi:10.1145/2785953.
- [6] Chandra TD, Toueg S. Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, 1996. 43(2):255-267. doi:10.1145/226643.226647.
- [7] Mostefaoui A, Rajsbaum S, Raynal M. Conditions on input vectors for consensus solvability in asynchronous distributed systems. volume 50. 2001 pp. 153-162. doi:10.1145/950620.950624.
- [8] Lamport L, Shostack R, Pease M. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982. 4(3):382-401. doi:10.1145/357172.357176.
- [9] Pease M, Shostak R, Lamport L. Reaching Agreement in the Presence of Faults. J. ACM, 1980. 27:228-234. doi:10.1145/322186.322188.
- [10] Toueg S. Randomized Byzantine Agreements. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B. C., Canada, August 27-29, 1984. 1984 pp. 163-178. doi:10.1145/800222.806744.
- [11] Aguilera M, Delporte-Gallet C, Fauconnier H, Toueg S. Communication-efficient leader election and consensus with limited link synchrony. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, volume PODC 04. acm press, 2004 pp. 328-337. doi:10.1145/1011767.1011816.
- [12] Aguilera M, Delporte-Gallet C, Fauconnier H, Toueg S. Consensus with Byzantine Failures and Little System Synchrony. volume 2006. Philadelphia. ISBN 0-7695-2607-1, 2006 pp. 147-155. doi:10.1109/DSN.2006.22.
- [13] Castro M, Liskov B. Practical Byzantine fault tolerance. In: Proc. of the 3rd Symposium on Operating Systems Design and Implementation. New Orleans, USA, 1999.
- [14] 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 pp. 24-50. doi:10.1007/3-540-48046-3_3.
- [15] Dutta P, Guerraoui R, Vukolic M. Best-case complexity of asynchronous byzantine consensus. Epfl/ic/200499, EPFL, 2005.
- [16] Kursawe K. Optimistic Byzantine agreement. In: Proc. of the 21st IEEE Symposium on Reliable Distributed Systems. 2002.
- [17] Kihlstrom K, Moser L, Melliar-Smith P. Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector. 1997 pp. 61-75.
- [18] Lamport L. Lower bounds for asynchronous consensus. Distributed Computing, 2006. 19(2):104-125. doi:10.1007/s00446-006-0155-x.
- [19] Martin JP, Alvisi L. Fast Byzantine paxos. Yokohama, Japan, 2005 pp. 402-411.
- [20] Friedman R, Mostefaoui A, Raynal M. Simple and efficient oracle-based consensus protocols for asynchronous byzantine systems. IEEE Transactions on Dependable and Secure Computing, 2005. 2(1):46-56. doi:10.1109/TDSC.2005.13.
- [21] Friedman R, Mostefaoui A, Raynal M. Consensus for Asynchronous Byzantine Systems. Parallel Processing Letters, 2005. 15(1-2):169-182. doi:10.1142/S0129626405002131.
- [22] Bouzid Z, Mostéfaoui A, Raynal M. Minimal synchrony for Byzantine consensus. In: press A (ed.), Proc. 34th ACM Symposium on Principles of Distributed Computing. 2015 pp. PP. 461-470. doi:10.1145/2767386.2767418.
- [23] Moumen H, Mostefaoui A. Time-Free Authenticated Byzantine Consensus. In: Proc. on the Ninth IEEE International Symposium on Network Computing and Applications. Cambridge, USA, 2010 pp. 140-146. doi:10.1109/NCA.2010.25.
- [24] Moumen H, Mostefaoui A, Tredan G. Byzantine Consensus with Few Synchronous Links. In: Proc. of the Int. Conference on Principles of Distributed Systems. 2007 pp. 76-89. doi:10.1007/978-3-540-77096-1_6.
- [25] Baldellon O, Mostéfaoui A, Raynal M. A necessary and sufficient synchrony condition for solving Byzantine consensus in symmetric networks. In: Springer (ed.), Proc. 12th International Conference on Distributed Computing and Networks, volume LNCS. 2011 pp. pp. 215-226. doi:10.1007/978-3-642-17679-1_19.
- [26] Rivest R, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM, 1978. 21:120-126. doi:10.1145/357980.358017.
- [27] Mostefaoui A, Mourgaya E, Raynal M. Asynchronous Implementation of Failure Detectors. In: Proc. Int’l IEEE Conf. Dependable Systems and Networks. 2003 pp. 351-360. doi:10.1109/DSN.2003.1209946.
- [28] Mostefaoui A, Mourgaya E, Raynal M, Travers C. A Time-free Assumption to Implement Eventual Leadership. Parallel Processing Letters, 2006. 16(2):189-208. URL https://doi.org/10.1142/S0129626406002575.
- [29] Mostefaoui A, Powell D, Raynal M, et al. A Hybrid Approach for Building Eventually Accurate Failure Detectors. In: Dependable Computing. ISBN 0-7695-2076-6, 2004 pp. 57-65. doi:10.1109/PRDC.2004.1276553.
- [30] Mostfaoui A, Raynal M, Travers C. Time-free and timer-based assumptions can be combined to obtain eventual leadership. Parallel and Distributed Systems, IEEE Transactions on, 2006. 17:656-666. doi:10.1109/TPDS.2006.95.
- [31] Hutle M, Malkhi D, Schmid U, Zhou L. Chasing the Weakest System Model for Implementing. Technische Universität Wien, Institut für Technische Informatik, 2006.
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-4a26e845-c2f9-4b2f-a212-cea367a4dee9