Byzantine-tolerant reliable broadcast in the presence of silent churn. (English) Zbl 1521.68017
Johnen, Colette (ed.) et al., Stabilization, safety, and security of distributed systems. 23rd international symposium, SSS 2021, virtual event, November 17–20, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13046, 21-33 (2021).
Summary: This paper introduces a new reliable broadcast communication abstraction suited to \(n\)-process asynchronous message-passing systems in which up to \(t\) processes may behave arbitrarily (Byzantine processes) and where (due to transient disconnections or message losses) up to \(d\) correct processes may not receive a message broadcast by a correct (i.e., not Byzantine) process. Then the paper presents and proves correct an algorithm implementing such a communication abstraction where the system parameters \(n\), \(t\), and \(d\) are such that \(n>3t +2d\).
For the entire collection see [Zbl 1509.68014].
For the entire collection see [Zbl 1509.68014].
MSC:
| 68M14 | Distributed systems |
| 68M10 | Network design and communication in computer systems |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
asynchronous system; Byzantine processes; churn; message adversary; message losses; message-passing; reliable broadcast; transient disconnectionReferences:
| [1] | Afek, Y.; Gafni, E.; Frey, D.; Raynal, M.; Sarkar, S.; Shyamasundar, RK; Sinha, P., Asynchrony from synchrony, Distributed Computing and Networking, 225-239 (2013), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-35668-1_16 |
| [2] | Bracha, G., Asynchronous Byzantine agreement protocols, Inf. Comput., 75, 2, 130-143 (1987) · Zbl 0622.68032 · doi:10.1016/0890-5401(87)90054-X |
| [3] | Bracha, G.; Toueg, S., Asynchronous consensus and broadcast protocols, J. ACM, 32, 4, 824-840 (1985) · Zbl 0628.68024 · doi:10.1145/4221.214134 |
| [4] | Cachin, Ch., Guerraoui, R., Rodrigues, L.: Reliable and Secure Distributed Programming, p. 367. Springer, Heidelberg (2011). doi:10.1007/978-3-642-15260-3. ISBN 978-3-642-15259-7 · Zbl 1208.68001 |
| [5] | Charron-Bost, B.; Schiper, A., The heard-of model: computing in distributed systems with benign faults, Distrib. Comput., 22, 1, 49-71 (2009) · Zbl 1267.68151 · doi:10.1007/s00446-009-0084-6 |
| [6] | Guerraoui, G., Komatovic, J., Kuznetsov, P., Pignolet, P.A., Seredinschi, D.-A., Tonkikh A.: Dynamic Byzantine reliable broadcast. In: Proceedings of 24th International Conference on Principles of Distributed Systems (OPODIS’20), LIPIcs, vol. 184, Article 23, 18 p. (2020) |
| [7] | Guerraoui, G., Kuznetsov, P., Monti, M., Pavlovic, M., Seredinschi, D.-A.: Scalable Byzantine reliable broadcast. In: Proceedings of 33rd International Symposium on Distributed Computing (DISC’19), LIPIcs, vol. 146, Article 22, 16 p. (2019) · Zbl 1515.68066 |
| [8] | Hirt, M., Kastrato, A., Liu-Zhang, C.-D.: Multi-threshold asynchronous reliable broadcast and consensus. In: Proceedings of 24th International Conference on Principles of Distributed Systems (OPODIS’20), LIPICs, vol. 184, Article 6, 16 p. (2020) |
| [9] | Imbs, D.; Raynal, M., Trading \(t\)-resilience for efficiency in asynchronous Byzantine reliable broadcast, Parallel Process. Lett., 26, 4, 8 (2016) · Zbl 1376.68027 · doi:10.1142/S0129626416500171 |
| [10] | Lamport, L.; Shostack, 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 |
| [11] | Nayak, K., Ren, L., Shi, E., Vaidya, N.H., Xiang, Z.: Improved extension protocols for Byzantine broadcast and agreement. In: Proceedings of 34rd Int’l Symposium on Distributed Computing (DISC’20), LIPIcs, vol. 179, Article 28, 16 p. (2020) · Zbl 1540.68042 |
| [12] | Pease, M.; Shostak, R.; Lamport, L., Reaching agreement in the presence of faults, J. ACM, 27, 228-234 (1980) · Zbl 0434.68031 · doi:10.1145/322186.322188 |
| [13] | Raynal, M.; Kao, M-Y, Message adversaries, Encyclopedia of Algorithms, 1272-1276 (2015), Heidelberg: Springer, Heidelberg · doi:10.1007/978-1-4939-2864-4 |
| [14] | Raynal, M.: Fault-Tolerant Message-passing Distributed Systems: An Algorithmic Approach, p. 480. Springer, Heidelberg (2018). doi:10.1007/978-3-319-94141-7. ISBN 978-3-319-94140-0 · Zbl 1423.68011 |
| [15] | Raynal, M., On the versatility of Bracha’s Byzantine reliable broadcast algorithm, Parallel Process. Lett., 31, 3, 2150006 (2021) · Zbl 1490.68052 · doi:10.1142/S0129626421500067 |
| [16] | Raynal, M., Stainer, J.: Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. In: Proceedings of 32nd ACM Symposium on Principles of Distributed Computing (PODC ’13), pp. 166-175. ACM Press (2013) · Zbl 1323.68046 |
| [17] | Santoro, N.; Widmayer, P.; Monien, B.; Cori, R., Time is not a healer, STACS 89, 304-313 (1989), Heidelberg: Springer, Heidelberg · Zbl 1492.68037 · doi:10.1007/BFb0028994 |
| [18] | Santoro, N.; Widmayer, P., Agreement in synchronous networks with ubiquitous faults, Theoret. Comput. Sci., 384, 2-3, 232-249 (2007) · Zbl 1125.68012 · doi:10.1016/j.tcs.2007.04.036 |
| [19] | Srikanth, TK; Toueg, S., Simulating authenticated broadcasts to derive simple fault-tolerant algorithms, Distrib. Comput., 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.
