Byzantine agreement using partial authentication. (English) Zbl 1350.68033
Peleg, David (ed.), Distributed computing. 25th international symposium, DISC 2011, Rome, Italy, September 20–22, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24099-7/pbk). Lecture Notes in Computer Science 6950, 389-403 (2011).
Summary: Three decades ago, M. Pease et al. introduced the problem of Byzantine Agreement [J. ACM 27, 228–234 (1980; Zbl 0434.68031)] where nodes need to maintain a consistent view of the world in spite of the challenge posed by Byzantine faults. Subsequently, it is well known that Byzantine agreement over a completely connected synchronous network of \(n\) nodes tolerating up to \(t\) faults is (efficiently) possible if and only if \(t < n/3\). Pease et al. further empowered the nodes with the ability to authenticate themselves and their messages and proved that agreement in this new model (popularly known as authenticated Byzantine agreement (ABA)) is possible if and only if \(t < n\). (which is a huge improvement over the bound of \(t < n/3\) in the absence of authentication for the same functionality).
To understand the utility, potential and limitations of using authentication in distributed protocols for agreement, A. Gupta et al. [Lect. Notes Comput. Sci. 5935, 79–91 (2010; Zbl 1350.68035)] studied ABA in new light. They generalize the existing models and thus, attempt to give a unified theory of agreements over the authenticated and non-authenticated domains. In this paper we extend their results to synchronous (undirected) networks and give a complete characterization of agreement protocols.
As a corollary, we show that agreement can be strictly easier than all-pair point-to-point communication. It is well known that in a synchronous network over \(n\) nodes of which up to any \(t\) are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [D. Dolev et al., J. Algorithms 3, 14–30 (1982; Zbl 0495.68093); J. ACM 40, No. 1, 17–47 (1993; Zbl 0774.68017)]. Thus, a folklore in the area is that maintaining global consistency (agreement) is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete networks exist only if it is possible to simulate an overlay-ed complete network. Surprisingly, we show that the folklore is not always true. Thus, it seems that agreement protocols may be more fundamental to distributed computing than reliable communication.
For the entire collection see [Zbl 1225.68024].
To understand the utility, potential and limitations of using authentication in distributed protocols for agreement, A. Gupta et al. [Lect. Notes Comput. Sci. 5935, 79–91 (2010; Zbl 1350.68035)] studied ABA in new light. They generalize the existing models and thus, attempt to give a unified theory of agreements over the authenticated and non-authenticated domains. In this paper we extend their results to synchronous (undirected) networks and give a complete characterization of agreement protocols.
As a corollary, we show that agreement can be strictly easier than all-pair point-to-point communication. It is well known that in a synchronous network over \(n\) nodes of which up to any \(t\) are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [D. Dolev et al., J. Algorithms 3, 14–30 (1982; Zbl 0495.68093); J. ACM 40, No. 1, 17–47 (1993; Zbl 0774.68017)]. Thus, a folklore in the area is that maintaining global consistency (agreement) is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete networks exist only if it is possible to simulate an overlay-ed complete network. Surprisingly, we show that the folklore is not always true. Thus, it seems that agreement protocols may be more fundamental to distributed computing than reliable communication.
For the entire collection see [Zbl 1225.68024].
MSC:
| 68M12 | Network protocols |
| 68M14 | Distributed systems |
| 68W15 | Distributed algorithms |
| 94A62 | Authentication, digital signatures and secret sharing |
References:
| [1] | Altmann, B., Fitzi, M., Maurer, U.M.: Byzantine agreement secure against general adversaries in the dual failure model. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 123–139. Springer, Heidelberg (1999) · doi:10.1007/3-540-48169-9_9 |
| [2] | Bansal, P., Gopal, P., Gupta, A., Srinathan, K., Vasishta, P.K.: Byzantine agreement using partial authentication. Technical report, http://people.csail.mit.edu/prasant/agreement.pdf · Zbl 1350.68033 |
| [3] | Borcherding, M.: On the number of authenticated rounds in byzantine agreement. In: Helary, J.-M., Raynal, M. (eds.) WDAG 1995. LNCS, vol. 972, pp. 230–241. Springer, Heidelberg (1995) · doi:10.1007/BFb0022150 |
| [4] | Borcherding, M.: Levels of authentication in distributed agreement. In: Babaoğlu, Ö., Marzullo, K. (eds.) WDAG 1996. LNCS, vol. 1151, pp. 40–55. Springer, Heidelberg (1996) · doi:10.1007/3-540-61769-8_4 |
| [5] | Borcherding, M.: Partially authenticated algorithms for byzantine agreement. In: ISCA: Proceedings of the 9th International Conference on Parallel and Distributed Computing Systems, pp. 8–11 (1996) |
| [6] | Dolev, D., Dwork, C., Stockmeyer, L.: On the minimal synchronism needed for distributed consensus. J. ACM 34(1), 77–97 (1987) · Zbl 0631.68022 · doi:10.1145/7531.7533 |
| [7] | Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly Secure Message Transmission. Journal of the Association for Computing Machinery (JACM) 40(1), 17–47 (1993) · Zbl 0774.68017 · doi:10.1145/138027.138036 |
| [8] | Dolev, D.: The Byzantine Generals Strike Again. Journal of Algorithms 3(1), 14–30 (1982) · Zbl 0495.68093 · doi:10.1016/0196-6774(82)90004-9 |
| [9] | Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM Journal on Computing 12(4), 656–666 (1983) · Zbl 0524.68021 · doi:10.1137/0212045 |
| [10] | Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985) · Zbl 0629.68027 · doi:10.1145/3149.214121 |
| [11] | Fitzi, M., Maurer, U.M.: Efficient byzantine agreement secure against general adversaries. In: Kutten, S. (ed.) DISC 1998. LNCS, vol. 1499, pp. 134–148. Springer, Heidelberg (1998) · doi:10.1007/BFb0056479 |
| [12] | Gupta, A., Gopal, P., Bansal, P., Srinathan, K.: Authenticated Byzantine Generals in Dual Failure Model. In: Kant, K., Pemmaraju, S.V., Sivalingam, K.M., Wu, J. (eds.) ICDCN 2010. LNCS, vol. 5935, pp. 79–91. Springer, Heidelberg (2010) · Zbl 1350.68035 · doi:10.1007/978-3-642-11322-2_12 |
| [13] | Gong, L., Lincoln, P., Rushby, J.: Byzantine agreement with authentication: Observations and applications in tolerating hybrid and link faults (1995) |
| [14] | Hirt, M., Maurer, U.: Complete Characterization of Adversaries Tolerable in Secure Multi-party Computation. In: Proceedings of the 16th Symposium on Principles of Distributed Computing (PODC), August 1997, pp. 25–34. ACM Press, New York (1997) · Zbl 1374.68070 |
| [15] | Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J. Cryptology 13(1), 31–60 (2000) · Zbl 0988.94019 · doi:10.1007/s001459910003 |
| [16] | Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982) · Zbl 0483.68021 · doi:10.1145/357172.357176 |
| [17] | Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Mateo (1996) · Zbl 0877.68061 |
| [18] | Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980) · Zbl 0434.68031 · doi:10.1145/322186.322188 |
| [19] | Srikanth, T.K., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing 2(2), 80–94 (1987) · doi:10.1007/BF01667080 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
