×

Approximate agreement under mobile Byzantine faults. (English) Zbl 1410.68029

Summary: In this paper, we address the Approximate Agreement problem in the Mobile Byzantine Fault model. Our contribution is three-fold. First, we refine the problem specification to adapt it to the Mobile Byzantine Fault environment. Then, we propose the first mapping from the existing variants of Mobile Byzantine models to the Mixed-mode Fault model. This mapping further help us to prove the correctness of MSR (Mean-Subsequence-Reduce) algorithms class in our context and it is of independent interest. We also prove lower bounds for solving Approximate Agreement under all existing Mobile Byzantine fault models.

MSC:

68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Banu, N.; Souissi, S.; Izumi, T.; Wada, K., An improved Byzantine agreement algorithm for synchronous systems with mobile faults, Int. J. Comput. Appl., 43, 22, 1-7, (2012)
[2] Berman, P.; Garay, J. A.; Perry, K. J., Towards optimal distributed consensus (extended abstract), (30th Annual Symposium on Foundations of Computer Science. 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October-1 November 1989, (1989)), 410-415
[3] Bonnet, F.; Défago, X.; Nguyen, T. D.; Potop-Butucaru, M., Tight bound on mobile Byzantine agreement, (Distributed Computing - 28th International Symposium. Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014, Proceedings, (2014)), 76-90
[4] Bouzid, Z.; Potop-Butucaru, M. G.; Tixeuil, S., Byzantine convergence in robot networks: the price of asynchrony, (Abdelzaher, T. F.; Raynal, M.; Santoro, N., Principles of Distributed Systems, 13th International Conference. Principles of Distributed Systems, 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009, Proceedings. Principles of Distributed Systems, 13th International Conference. Principles of Distributed Systems, 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5923, (2009), Springer), 54-70
[5] Bouzid, Z.; Potop-Butucaru, M. G.; Tixeuil, S., Optimal Byzantine-resilient convergence in uni-dimensional robot networks, Theoret. Comput. Sci., 411, 34-36, 3154-3168, (2010) · Zbl 1196.68282
[6] Buhrman, H.; Garay, J. A.; Hoepman, J. H., Optimal resiliency against mobile faults, (Proceedings of the 25th International Symposium on Fault-Tolerant Computing. Proceedings of the 25th International Symposium on Fault-Tolerant Computing, FTCS’95, (1995)), 83-88
[7] Charron-Bost, B.; Függer, M.; Nowak, T., Approximate consensus in highly dynamic networks: the role of averaging algorithms, (Automata, Languages, and Programming - 42nd International Colloquium. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, (2015)), 528-539 · Zbl 1417.68012
[8] Dolev, D.; Lynch, N. A.; Pinter, S. S.; Stark, E. W.; Weihl, W. E., Reaching approximate agreement in the presence of faults, J. ACM, 33, 3, 499-516, (1986) · Zbl 0627.68027
[9] Fekete, A. D., Asymptotically optimal algorithms for approximate agreement, Distrib. Comput., 4, 9-29, (1990)
[10] Fekete, A. D., Asynchronous approximate agreement, Inform. and Comput., 115, 1, 95-124, (1994) · Zbl 0938.68944
[11] Fischer, M. J.; Lynch, N. A.; Merritt, M., Easy impossibility proofs for distributed consensus problems, Distrib. Comput., 1, 1, 26-39, (1986) · Zbl 0598.68024
[12] Garay, J. A., Reaching (and maintaining) agreement in the presence of mobile faults, (Proceedings of the 8th International Workshop on Distributed Algorithms, vol. 857, (1994)), 253-264
[13] Kieckhafer, R. M.; Azadmanesh, M. H., Reaching approximate agreement with mixed-mode faults, IEEE Trans. Parallel Distrib. Syst., 5, 1, 53-63, (1994)
[14] Lamport, L.; Shostak, R. E.; Pease, M. C., The Byzantine generals problem, ACM Trans. Program. Lang. Syst., 4, 3, 382-401, (1982) · Zbl 0483.68021
[15] Li, C.; Hurfin, M.; Wang, Y., Approximate Byzantine consensus in sparse, mobile ad-hoc networks, J. Parallel Distrib. Comput., 74, 9, 2860-2871, (2014)
[16] Lynch, N. A., Distributed Algorithms, (1996), Morgan Kaufmann · Zbl 0877.68061
[17] Mendes, H.; Herlihy, M., Multidimensional approximate agreement in Byzantine asynchronous systems, (Symposium on Theory of Computing Conference. Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, (2013)), 391-400 · Zbl 1293.68060
[18] Mendes, H.; Herlihy, M.; Vaidya, N. H.; Garg, V. K., Multidimensional agreement in Byzantine systems, Distrib. Comput., 28, 6, 423-441, (2015) · Zbl 1347.68031
[19] Ostrovsky, R.; Yung, M., How to withstand mobile virus attacks (extended abstract), (Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, PODC’91, (1991)), 51-59 · Zbl 1314.68132
[20] Reischuk, R., A new solution for the Byzantine generals problem, Inf. Control, 64, 1-3, 23-42, (1985) · Zbl 0575.68025
[21] Sasaki, T.; Yamauchi, Y.; Kijima, S.; Yamashita, M., Mobile Byzantine agreement on arbitrary network, (Proceedings of the 17th International Conference on Principles of Distributed Systems. Proceedings of the 17th International Conference on Principles of Distributed Systems, OPODIS’13, (2013)), 236-250
[22] Stolz, D.; Wattenhofer, R., Byzantine approximate agreement with median validity, (Anceaume, E.; Cachin, C.; Potop-Butucaru, M., 19th International Conference on Principles of Distributed Systems (OPODIS 2015). 19th International Conference on Principles of Distributed Systems (OPODIS 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, (2016), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Dagstuhl, Germany), 1-14 · Zbl 1380.68067
[23] Su, L.; Vaidya, N. H., Reaching approximate Byzantine consensus with multi-hop communication, (Stabilization, Safety, and Security of Distributed Systems - 17th International Symposium. Stabilization, Safety, and Security of Distributed Systems - 17th International Symposium, SSS 2015, Edmonton, AB, Canada, August 18-21, 2015, Proceedings, (2015)), 21-35
[24] Tseng, L.; Vaidya, N. H., Iterative approximate Byzantine consensus under a generalized fault model, (Distributed Computing and Networking, 14th International Conference. Distributed Computing and Networking, 14th International Conference, ICDCN 2013, Mumbai, India, January 3-6, 2013, Proceedings, (2013)), 72-86 · Zbl 1352.68024
[25] Tseng, L.; Vaidya, N. H., Asynchronous convex hull consensus in the presence of crash faults, (ACM Symposium on Principles of Distributed Computing. ACM Symposium on Principles of Distributed Computing, PODC’14, Paris, France, July 15-18, 2014, (2014)), 396-405 · Zbl 1321.68094
[26] Tseng, L.; Vaidya, N. H., Iterative approximate consensus in the presence of Byzantine link failures, (Networked Systems - Second International Conference. Networked Systems - Second International Conference, NETYS 2014, Marrakech, Morocco, May 15-17 2014, (2014)), 84-98, Revised Selected Papers
[27] Vaidya, N. H.; Tseng, L.; Liang, G., Iterative approximate Byzantine consensus in arbitrary directed graphs, (ACM Symposium on Principles of Distributed Computing. ACM Symposium on Principles of Distributed Computing, PODC’12, Funchal, Madeira, Portugal, July 16-18, (2012)), 365-374 · Zbl 1301.68168
[28] Yung, M., The mobile adversary paradigm in distributed computation and systems, (Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, (2015), ACM), 171-172
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.