Abstract
Ensuring reliable communication despite possibly malicious participants is a primary objective in any distributed system or network. In this paper, we investigate the possibility of reliable broadcast in a dynamic network whose topology may evolve while the broadcast is in progress. In particular, we adapt the Certified Propagation Algorithm (CPA) to make it work on dynamic networks and we present conditions (on the underlying dynamic graph) to enable safety and liveness properties of the reliable broadcast. We furthermore explore the complexity of assessing these conditions for various classes of dynamic networks.
This work was performed within Project ESTATE (Ref. ANR-16-CE25-0009-03), supported by French state funds managed by the ANR (Agence Nationale de la Recherche), and it has has been partially supported by the INOCS Sapienza Ateneo 2017 Project (protocol number RM11715C816CE4CB). Giovanni Farina thanks the Université Franco-Italienne/Universitá Italo-Francese (UFI/UIF) for supporting his mobility through the Vinci grant 2018.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note the assumption of a possibly faulty source leads to a more general problem, the Byzantine Agreement [5].
- 2.
For the sake of simplicity, we consider the channel delay always equal to 1 in the example.
- 3.
Class 1 TVG according to Casteigts et al. [3].
- 4.
Class 6 TVG in Casteigts et al. [3].
- 5.
Class 7 TVG in Casteigts et al. [3].
References
Augustine, J., Pandurangan, G., Robinson, P.: Fast Byzantine agreement in dynamic networks. In: Fatourou, P., Taubenfeld, G. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2013, 22–24 July 2013, Montreal, QC, Canada, pp. 74–83. ACM (2013)
Bhandari, V., Vaidya, N.H.: Reliable broadcast in radio networks with locally bounded failures. IEEE Trans. Parallel Distrib. Syst. 21(6), 801–811 (2010)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012)
Castro, M., Liskov, B., et al.: Practical Byzantine fault tolerance. In: OSDI, vol. 99, pp. 173–186 (1999)
Dolev, D.: Unanimity in an unknown and unreliable environment. In: 1981 22nd Annual Symposium on Foundations of Computer Science, SFCS 1981, pp. 159–168. IEEE (1981)
Drabkin, V., Friedman, R., Segal, M.: Efficient Byzantine broadcast in wireless ad-hoc networks. In: 2005 Proceedings of International Conference on Dependable Systems and Networks, DSN 2005, pp. 160–169. IEEE (2005)
Gómez-Calzado, C., Casteigts, A., Lafuente, A., Larrea, M.: A connectivity model for agreement in dynamic systems. In: Träff, J.L., Hunold, S., Versaci, F. (eds.) Euro-Par 2015. LNCS, vol. 9233, pp. 333–345. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48096-0_26
Guerraoui, R., Huc, F., Kermarrec, A.: Highly dynamic distributed computing with Byzantine failures. In: Fatourou, P., Taubenfeld, G. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2013, 22–24 July 2013, Montreal, QC, Canada, pp. 176–183. ACM (2013)
Ichimura, A., Shigeno, M.: A new parameter for a broadcast algorithm with locally bounded Byzantine faults. Inf. Process. Lett. 110(12–13), 514–517 (2010)
Koo, C.Y.: Broadcast in radio networks tolerating Byzantine adversarial behavior. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 275–282. ACM (2004)
Litsas, C., Pagourtzis, A., Sakavalas, D.: A graph parameter that matches the resilience of the certified propagation algorithm. In: Cichoń, J., Gȩbala, M., Klonowski, M. (eds.) ADHOC-NOW 2013. LNCS, vol. 7960, pp. 269–280. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39247-4_23
Maurer, A., Tixeuil, S.: Byzantine broadcast with fixed disjoint paths. J. Parallel Distrib. Comput. 74(11), 3153–3160 (2014)
Maurer, A., Tixeuil, S.: Containing Byzantine failures with control zones. IEEE Trans. Parallel Distrib. Syst. 26(2), 362–370 (2015)
Maurer, A., Tixeuil, S.: Tolerating random Byzantine failures in an unbounded network. Parallel Process. Lett. 26(1) (2016)
Maurer, A., Tixeuil, S., Defago, X.: Communicating reliably in multihop dynamic networks despite Byzantine failures. In: 2015 IEEE 34th Symposium on Reliable Distributed Systems (SRDS), pp. 238–245. IEEE (2015)
Pelc, A., Peleg, D.: Broadcasting with locally bounded Byzantine faults. Inf. Process. Lett. 93(3), 109–115 (2005)
Raynal, M., Stainer, J., Cao, J., Wu, W.: A simple broadcast algorithm for recurrent dynamic systems. In: 28th IEEE International Conference on Advanced Information Networking and Applications, AINA 2014, 13–16 May 2014, Victoria, BC, Canada, pp. 933–939 (2014)
Tseng, L., Vaidya, N.H., Bhandari, V.: Broadcast using certified propagation algorithm in presence of Byzantine faults. Inf. Process. Lett. 115(4), 512–514 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Bonomi, S., Farina, G., Tixeuil, S. (2018). Reliable Broadcast in Dynamic Networks with Locally Bounded Byzantine Failures. In: Izumi, T., Kuznetsov, P. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2018. Lecture Notes in Computer Science(), vol 11201. Springer, Cham. https://doi.org/10.1007/978-3-030-03232-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-03232-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03231-9
Online ISBN: 978-3-030-03232-6
eBook Packages: Computer ScienceComputer Science (R0)