A Hybrid Protocol to Solve Authenticated Byzantine Consensus

• Autorzy: Tioura Abdelhamid , Moumen Hamouma , Kalla Hamoudi , Ait Saidi Ahmed

Identyfikatory

DOI

10.3233/FI-2020-1916

• Języki publikacji: EN

Abstrakty

EN

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 p_i, called ⋄〈t + 1〉-BW, and a set X of t+1 correct processes (including p_i itself) such that, eventually, for each query broadcasted by a correct process p_j of X, p_j receives a response from p_i ∈ X among the (n – t) first responses to that query or both links connecting p_i and p_j 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.

Słowa kluczowe

EN

asynchronous distributed systems; byzantine process; consensus; distributed algorithms; fault tolerance; hybrid protocol; time-free assumption; timer-based assumption

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 173, nr 1
• Strony: 73--89
• Opis fizyczny: Bibliogr. 31 poz., tab.

Twórcy

autor

Tioura Abdelhamid

• Department of Computer Science, University of Bejaia, Bejaia 06000, Algeria

autor

Moumen Hamouma

• Department of Computer Science, University of Batna 2, Batna, Algeria

autor

Kalla Hamoudi

• Department of Computer Science, University of Batna 2, Batna, Algeria

autor

Ait Saidi Ahmed

• 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).