# American Institute of Mathematical Sciences

September  2019, 9(3): 269-281. doi: 10.3934/naco.2019018

## A resilient convex combination for consensus-based distributed algorithms

 1 School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN, USA 2 School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA

* Corresponding author: Shaoshuai Mou, mous@purdue.edu

Received  April 2018 Revised  April 2019 Published  May 2019

Fund Project: This work is supported by a seed grant from Purdue Center for Resilient Infrastructures, Systems, and Processes (CRISP). The research of Xuan Wang and Shaoshuai Mou is supported by fundings from Northrop Grumman Corporation. The research of Shreyas Sundaram is supported by the National Science Foundation CAREER award 1653648

Consider a set of vectors in $\mathbb{R}^n$, partitioned into two classes: normal vectors and malicious vectors, for which the number of malicious vectors is bounded but their identities are unknown. The paper provides an efficient way for achieving a resilient convex combination, which is a convex combination of only normal vectors. Compared with existing approaches based on Tverberg points, the proposed method based on the intersection of convex hulls has lower computational complexity. Simulations suggest that the proposed method can be applied to achieve resilience of consensus-based distributed algorithms against Byzantine attacks based only on agents' locally available information.

Citation: Xuan Wang, Shaoshuai Mou, Shreyas Sundaram. A resilient convex combination for consensus-based distributed algorithms. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 269-281. doi: 10.3934/naco.2019018
##### References:
 [1] P. K. Agarwal, M. Sharir and E. Welzl, Algorithms for center and tverberg points, ACM Transactions on Algorithms (TALG), 5 (2008), 5. doi: 10.1145/997817.997830. Google Scholar [2] B. D. O. Anderson, S. Mou, U. R. Helmke and A. S. Morse, Decentralized gradient algorithm for solution of a linear equation, Numerical Algebra, Control and Optimization, 6 (2016), 319-328. doi: 10.3934/naco.2016014. Google Scholar [3] C. B. Barber, D. P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), 22 (1996), 469-483. doi: 10.1145/235815.235821. Google Scholar [4] Z. Bouzid, M. G. Potop-Butucaru and S. Tixeuil, Optimal byzantine resilient convergence in uni-dimensional robot networks, Theoretical Computer Science, 411 (2010), 3154-3168. doi: 10.1016/j.tcs.2010.05.006. Google Scholar [5] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004. doi: 10.1017/CBO9780511804441. Google Scholar [6] M. Cao, A. S. Morse and B. D. O. Anderson, Agree asychronously, IEEE Transactions on Automatic Control, 53 (2008), 1826-1838. doi: 10.1109/TAC.2008.929387. Google Scholar [7] M. Cao, A. S. Morse and B. D. O. Anderson, Reaching a consensus in a dynamically changing enviornment: A graphical approach, SIAM Jounal on Control and Optimization, 47 (2008), 575-600. doi: 10.1137/060657005. Google Scholar [8] T. Chang, A. Nedic and A. Scaglione, Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Transactions on Automatic Control, 59 (2014), 1524-1538. doi: 10.1109/TAC.2014.2308612. Google Scholar [9] X. Chen, M. A. Belabbas and T. Basar, Distributed averaging with linear objective maps, Automatica, 70 (2016), 179-188. doi: 10.1016/j.automatica.2016.03.023. Google Scholar [10] A. Jadbabaie, J. Lin and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, 48 (2003), 988–1001, Also in Proc. 41st IEEE CDC, (2002), 2953–2958. doi: 10.1109/TAC.2003.812781. Google Scholar [11] L. Lamport, R. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4 (1982), 382-401. Google Scholar [12] H. J. LeBlane, H. Zhang, X. Koutsoukos and S. Sundaram, Resilient asymptotic consensus in robust networks, IEEE Journal on Selected Areas in Communications, 31 (2013), 766-781. Google Scholar [13] J. Lin, A. S. Morse and B. D. Anderson, The multi-agent rendezvous problem. part 2: The asynchronous case, SIAM Journal on Control and Optimization, 46 (2007), 2120-2147. doi: 10.1137/040620564. Google Scholar [14] J. Liu, S. Mou, A. S. Morse, B. D. O. Anderson and C. Yu, Deterministic gossiping, Proceedings of the IEEE, 99 (2011), 1505-1524. Google Scholar [15] Q. Liu, S. Yang and Y. Hong, Constrained consensus algorithms with fixed step size for distributed convex optimizations over multiagent networks, IEEE Transactions on Automatic Control, 62 (2017), 4259-4265. doi: 10.1109/TAC.2017.2681200. Google Scholar [16] H. Mendes, M. Herlihy, N. Vaidya and V. Garg, Multidimensional agreement in byzantine systems, Distributed Computing, 28 (2015), 423-441. doi: 10.1007/s00446-014-0240-5. Google Scholar [17] S. Mou and M. Cao, Distributed averaging using compensation, IEEE Communication Letters, 17 (2013), 1672-1675. Google Scholar [18] S. Mou, Z. Lin, L. Wang, D. Fullmer and A. S. Morse, A distributed algorithm for efficiently solving linear equations and its applications (special issue jcw), Systems & Control Letters, 91 (2016), 21-27. doi: 10.1016/j.sysconle.2016.02.010. Google Scholar [19] S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation, IEEE Transactions on Automatic Control, 60 (2015), 2863-2878. doi: 10.1109/TAC.2015.2414771. Google Scholar [20] W. Mulzer and D. Werner, Approximating tverberg points in linear time for any fixed dimension, Discrete & Computational Geometry, 50 (2013), 520-535. doi: 10.1007/s00454-013-9528-7. Google Scholar [21] A. Nedic and A. Ozdaglar, Distributed sub-gradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54 (2009), 48-61. doi: 10.1109/TAC.2008.2009515. Google Scholar [22] A. Nedic, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 55 (2010), 922-938. doi: 10.1109/TAC.2010.2041686. Google Scholar [23] H. Park and S. Hutchinson, A distributed robust convergence algorithm for multi-robot systems in the presence of faulty robots, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), (2015), 2980–2985.Google Scholar [24] H. Park and S. Hutchinson, An efficient algorithm for fault-tolerant rendezvous of multi-robot systems with controllable sensing range, in IEEE International Conference on Robotics and Automation (ICRA), (2016), 358–365.Google Scholar [25] H. Park and S. A. Hutchinson, Fault-tolerant rendezvous of multirobot systems, IEEE Transactions on Robotics, 33 (2017), 565-582. Google Scholar [26] F. Pasqualetti, A. Bicchi and F. Bullo, Consensus computation in unreliable networks: A system theoretic approach, IEEE Transactions on Automatic Control, 57 (2012), 90-104. doi: 10.1109/TAC.2011.2158130. Google Scholar [27] F. Pasqualetti, F. Dorfler and F. Bullo, Attack detection and identification in cyber physical systems, IEEE Transactions on Automatic Control, 58 (2013), 2715-2719. doi: 10.1109/TAC.2013.2266831. Google Scholar [28] L. A. Rademacher, Approximating the centroid is hard, in Proceedings of the twenty-third annual symposium on Computational geometry, (2007), 302–305.Google Scholar [29] W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control, Springer, 2008.Google Scholar [30] G. Shi, B. D. O. Anderson and U. Helmke, Network flows that solve linear equations, IEEE Transactions on Automatic Control, 62 (2017), 2659-2674. doi: 10.1109/TAC.2016.2612819. Google Scholar [31] S. Sundaram and C. N. Hadjicostis, Finite-time distributed consensus in graphs with time-invarient topologies, in Proceedings of American Control Conference, (2007), 711–716.Google Scholar [32] S. Sundaram and C. N. Hadjicostis, Distributed function calculation via linear iterative strategies in the presence of malicious agents, IEEE Transactions on Automatic Control, 56 (2011), 1495-1508. doi: 10.1109/TAC.2010.2088690. Google Scholar [33] S. Sundaram and B. Gharesifard, Distributed optimization under adversarial nodes, IEEE Transactions on Automatic Control, DOI: 10.1109/TAC.2018.2836919 doi: 10.1109/TAC.2018.2836919. Google Scholar [34] L. Tseng and N. H. Vaidya, Asynchronous convex hull consensus in the presence of crash faults, in ACM symposium on Principles of distributed computing, (2014), 396–405.Google Scholar [35] H. Tverberg, A generalization of radon's theorem, Journal of the London Mathematical Society, 41 (1966), 123-128. doi: 10.1112/jlms/s1-41.1.123. Google Scholar [36] N. H. Vaidya, Iterative byzantine vector consensus in incomplete graphs, in International Conference on Distributed Computing and Networking, (2014), 14–28.Google Scholar [37] N. H. Vaidya, L. Tseng and G. Liang, Iterative approximate byzantine consensus in arbitrary directed graphs, in Proceedings of ACM Symposium on Principles of Distributed Computing, (2012), 365–374.Google Scholar [38] X. Wang, S. Mou and D. Sun, Improvement of a distributed algorithm for solving linear equations, IEEE Transactions on Industrial Electronics, 64 (2017), 3113-3117. Google Scholar

show all references

##### References:
 [1] P. K. Agarwal, M. Sharir and E. Welzl, Algorithms for center and tverberg points, ACM Transactions on Algorithms (TALG), 5 (2008), 5. doi: 10.1145/997817.997830. Google Scholar [2] B. D. O. Anderson, S. Mou, U. R. Helmke and A. S. Morse, Decentralized gradient algorithm for solution of a linear equation, Numerical Algebra, Control and Optimization, 6 (2016), 319-328. doi: 10.3934/naco.2016014. Google Scholar [3] C. B. Barber, D. P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), 22 (1996), 469-483. doi: 10.1145/235815.235821. Google Scholar [4] Z. Bouzid, M. G. Potop-Butucaru and S. Tixeuil, Optimal byzantine resilient convergence in uni-dimensional robot networks, Theoretical Computer Science, 411 (2010), 3154-3168. doi: 10.1016/j.tcs.2010.05.006. Google Scholar [5] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004. doi: 10.1017/CBO9780511804441. Google Scholar [6] M. Cao, A. S. Morse and B. D. O. Anderson, Agree asychronously, IEEE Transactions on Automatic Control, 53 (2008), 1826-1838. doi: 10.1109/TAC.2008.929387. Google Scholar [7] M. Cao, A. S. Morse and B. D. O. Anderson, Reaching a consensus in a dynamically changing enviornment: A graphical approach, SIAM Jounal on Control and Optimization, 47 (2008), 575-600. doi: 10.1137/060657005. Google Scholar [8] T. Chang, A. Nedic and A. Scaglione, Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Transactions on Automatic Control, 59 (2014), 1524-1538. doi: 10.1109/TAC.2014.2308612. Google Scholar [9] X. Chen, M. A. Belabbas and T. Basar, Distributed averaging with linear objective maps, Automatica, 70 (2016), 179-188. doi: 10.1016/j.automatica.2016.03.023. Google Scholar [10] A. Jadbabaie, J. Lin and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, 48 (2003), 988–1001, Also in Proc. 41st IEEE CDC, (2002), 2953–2958. doi: 10.1109/TAC.2003.812781. Google Scholar [11] L. Lamport, R. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4 (1982), 382-401. Google Scholar [12] H. J. LeBlane, H. Zhang, X. Koutsoukos and S. Sundaram, Resilient asymptotic consensus in robust networks, IEEE Journal on Selected Areas in Communications, 31 (2013), 766-781. Google Scholar [13] J. Lin, A. S. Morse and B. D. Anderson, The multi-agent rendezvous problem. part 2: The asynchronous case, SIAM Journal on Control and Optimization, 46 (2007), 2120-2147. doi: 10.1137/040620564. Google Scholar [14] J. Liu, S. Mou, A. S. Morse, B. D. O. Anderson and C. Yu, Deterministic gossiping, Proceedings of the IEEE, 99 (2011), 1505-1524. Google Scholar [15] Q. Liu, S. Yang and Y. Hong, Constrained consensus algorithms with fixed step size for distributed convex optimizations over multiagent networks, IEEE Transactions on Automatic Control, 62 (2017), 4259-4265. doi: 10.1109/TAC.2017.2681200. Google Scholar [16] H. Mendes, M. Herlihy, N. Vaidya and V. Garg, Multidimensional agreement in byzantine systems, Distributed Computing, 28 (2015), 423-441. doi: 10.1007/s00446-014-0240-5. Google Scholar [17] S. Mou and M. Cao, Distributed averaging using compensation, IEEE Communication Letters, 17 (2013), 1672-1675. Google Scholar [18] S. Mou, Z. Lin, L. Wang, D. Fullmer and A. S. Morse, A distributed algorithm for efficiently solving linear equations and its applications (special issue jcw), Systems & Control Letters, 91 (2016), 21-27. doi: 10.1016/j.sysconle.2016.02.010. Google Scholar [19] S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation, IEEE Transactions on Automatic Control, 60 (2015), 2863-2878. doi: 10.1109/TAC.2015.2414771. Google Scholar [20] W. Mulzer and D. Werner, Approximating tverberg points in linear time for any fixed dimension, Discrete & Computational Geometry, 50 (2013), 520-535. doi: 10.1007/s00454-013-9528-7. Google Scholar [21] A. Nedic and A. Ozdaglar, Distributed sub-gradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54 (2009), 48-61. doi: 10.1109/TAC.2008.2009515. Google Scholar [22] A. Nedic, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 55 (2010), 922-938. doi: 10.1109/TAC.2010.2041686. Google Scholar [23] H. Park and S. Hutchinson, A distributed robust convergence algorithm for multi-robot systems in the presence of faulty robots, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), (2015), 2980–2985.Google Scholar [24] H. Park and S. Hutchinson, An efficient algorithm for fault-tolerant rendezvous of multi-robot systems with controllable sensing range, in IEEE International Conference on Robotics and Automation (ICRA), (2016), 358–365.Google Scholar [25] H. Park and S. A. Hutchinson, Fault-tolerant rendezvous of multirobot systems, IEEE Transactions on Robotics, 33 (2017), 565-582. Google Scholar [26] F. Pasqualetti, A. Bicchi and F. Bullo, Consensus computation in unreliable networks: A system theoretic approach, IEEE Transactions on Automatic Control, 57 (2012), 90-104. doi: 10.1109/TAC.2011.2158130. Google Scholar [27] F. Pasqualetti, F. Dorfler and F. Bullo, Attack detection and identification in cyber physical systems, IEEE Transactions on Automatic Control, 58 (2013), 2715-2719. doi: 10.1109/TAC.2013.2266831. Google Scholar [28] L. A. Rademacher, Approximating the centroid is hard, in Proceedings of the twenty-third annual symposium on Computational geometry, (2007), 302–305.Google Scholar [29] W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control, Springer, 2008.Google Scholar [30] G. Shi, B. D. O. Anderson and U. Helmke, Network flows that solve linear equations, IEEE Transactions on Automatic Control, 62 (2017), 2659-2674. doi: 10.1109/TAC.2016.2612819. Google Scholar [31] S. Sundaram and C. N. Hadjicostis, Finite-time distributed consensus in graphs with time-invarient topologies, in Proceedings of American Control Conference, (2007), 711–716.Google Scholar [32] S. Sundaram and C. N. Hadjicostis, Distributed function calculation via linear iterative strategies in the presence of malicious agents, IEEE Transactions on Automatic Control, 56 (2011), 1495-1508. doi: 10.1109/TAC.2010.2088690. Google Scholar [33] S. Sundaram and B. Gharesifard, Distributed optimization under adversarial nodes, IEEE Transactions on Automatic Control, DOI: 10.1109/TAC.2018.2836919 doi: 10.1109/TAC.2018.2836919. Google Scholar [34] L. Tseng and N. H. Vaidya, Asynchronous convex hull consensus in the presence of crash faults, in ACM symposium on Principles of distributed computing, (2014), 396–405.Google Scholar [35] H. Tverberg, A generalization of radon's theorem, Journal of the London Mathematical Society, 41 (1966), 123-128. doi: 10.1112/jlms/s1-41.1.123. Google Scholar [36] N. H. Vaidya, Iterative byzantine vector consensus in incomplete graphs, in International Conference on Distributed Computing and Networking, (2014), 14–28.Google Scholar [37] N. H. Vaidya, L. Tseng and G. Liang, Iterative approximate byzantine consensus in arbitrary directed graphs, in Proceedings of ACM Symposium on Principles of Distributed Computing, (2012), 365–374.Google Scholar [38] X. Wang, S. Mou and D. Sun, Improvement of a distributed algorithm for solving linear equations, IEEE Transactions on Industrial Electronics, 64 (2017), 3113-3117. Google Scholar
Finding Tverberg point $\mathcal{T}$ (yellow) and $\mathcal{R}$ (red) in a 2-D space, with $\bar{\mathcal{A}} = \{1\}$
A network of 11 agents with malicious agents marked in red
Simulations of normal agents under the consensus update (20) without malicious agents (blank line) and with malicious agents $10$ and $11$ (red line)
Consensus is reached by introducing $u_i(t)$ as Tverberg points (indicated by the dashed line) or as the resilient convex combination (17) (indicated by the solid line)
Simulations by using the resilient convex combination $u_i(t)$ of (17) into (22)
Simulation results under the update (23) with no malicious agents (indicated by the black line) or with malicious agents (indicated by the red line)
Simulations by using the resilient convex combination $u_i(t)$ of (17) in (23)
 [1] Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020 [2] Rui Li, Yingjing Shi. Finite-time optimal consensus control for second-order multi-agent systems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 929-943. doi: 10.3934/jimo.2014.10.929 [3] Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489 [4] Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022 [5] Giulia Cavagnari, Antonio Marigonda, Benedetto Piccoli. Optimal synchronization problem for a multi-agent system. Networks & Heterogeneous Media, 2017, 12 (2) : 277-295. doi: 10.3934/nhm.2017012 [6] Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623 [7] Tyrone E. Duncan. Some partially observed multi-agent linear exponential quadratic stochastic differential games. Evolution Equations & Control Theory, 2018, 7 (4) : 587-597. doi: 10.3934/eect.2018028 [8] Hong Man, Yibin Yu, Yuebang He, Hui Huang. Design of one type of linear network prediction controller for multi-agent system. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 727-734. doi: 10.3934/dcdss.2019047 [9] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [10] Yejuan Wang, Tomás Caraballo. Morse decomposition for gradient-like multi-valued autonomous and nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-24. doi: 10.3934/dcdss.2020092 [11] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 [12] Viktor Levandovskyy, Gerhard Pfister, Valery G. Romanovski. Evaluating cyclicity of cubic systems with algorithms of computational algebra. Communications on Pure & Applied Analysis, 2012, 11 (5) : 2023-2035. doi: 10.3934/cpaa.2012.11.2023 [13] Alexandre N. Carvalho, José A. Langa, James C. Robinson. Non-autonomous dynamical systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (3) : 703-747. doi: 10.3934/dcdsb.2015.20.703 [14] Brooke L. Hollingsworth, R.E. Showalter. Semilinear degenerate parabolic systems and distributed capacitance models. Discrete & Continuous Dynamical Systems - A, 1995, 1 (1) : 59-76. doi: 10.3934/dcds.1995.1.59 [15] Getachew K. Befekadu, Eduardo L. Pasiliao. On the hierarchical optimal control of a chain of distributed systems. Journal of Dynamics & Games, 2015, 2 (2) : 187-199. doi: 10.3934/jdg.2015.2.187 [16] K. Tintarev. Critical values and minimal periods for autonomous Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 389-400. doi: 10.3934/dcds.1995.1.389 [17] Zhanyuan Hou, Stephen Baigent. Global stability and repulsion in autonomous Kolmogorov systems. Communications on Pure & Applied Analysis, 2015, 14 (3) : 1205-1238. doi: 10.3934/cpaa.2015.14.1205 [18] Jinlong Bai, Xuewei Ju, Desheng Li, Xiulian Wang. On the eventual stability of asymptotically autonomous systems with constraints. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 4457-4473. doi: 10.3934/dcdsb.2019127 [19] Xiaoming Wang. Numerical algorithms for stationary statistical properties of dissipative dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4599-4618. doi: 10.3934/dcds.2016.36.4599 [20] Harry L. Johnson, David Russell. Transfer function approach to output specification in certain linear distributed parameter systems. Conference Publications, 2003, 2003 (Special) : 449-458. doi: 10.3934/proc.2003.2003.449

Impact Factor:

## Metrics

• PDF downloads (29)
• HTML views (235)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]