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 and 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.

[2]

B. D. O. AndersonS. MouU. 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.

[3]

C. B. BarberD. 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.

[4]

Z. BouzidM. 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.

[5] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.  doi: 10.1017/CBO9780511804441.
[6]

M. CaoA. S. Morse and B. D. O. Anderson, Agree asychronously, IEEE Transactions on Automatic Control, 53 (2008), 1826-1838.  doi: 10.1109/TAC.2008.929387.

[7]

M. CaoA. 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.

[8]

T. ChangA. 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.

[9]

X. ChenM. A. Belabbas and T. Basar, Distributed averaging with linear objective maps, Automatica, 70 (2016), 179-188.  doi: 10.1016/j.automatica.2016.03.023.

[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.

[11]

L. LamportR. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4 (1982), 382-401. 

[12]

H. J. LeBlaneH. ZhangX. Koutsoukos and S. Sundaram, Resilient asymptotic consensus in robust networks, IEEE Journal on Selected Areas in Communications, 31 (2013), 766-781. 

[13]

J. LinA. 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.

[14]

J. LiuS. MouA. S. MorseB. D. O. Anderson and C. Yu, Deterministic gossiping, Proceedings of the IEEE, 99 (2011), 1505-1524. 

[15]

Q. LiuS. 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.

[16]

H. MendesM. HerlihyN. Vaidya and V. Garg, Multidimensional agreement in byzantine systems, Distributed Computing, 28 (2015), 423-441.  doi: 10.1007/s00446-014-0240-5.

[17]

S. Mou and M. Cao, Distributed averaging using compensation, IEEE Communication Letters, 17 (2013), 1672-1675. 

[18]

S. MouZ. LinL. WangD. 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.

[19]

S. MouJ. 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.

[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.

[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.

[22]

A. NedicA. 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.

[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.

[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.

[25]

H. Park and S. A. Hutchinson, Fault-tolerant rendezvous of multirobot systems, IEEE Transactions on Robotics, 33 (2017), 565-582. 

[26]

F. PasqualettiA. 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.

[27]

F. PasqualettiF. 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.

[28]

L. A. Rademacher, Approximating the centroid is hard, in Proceedings of the twenty-third annual symposium on Computational geometry, (2007), 302–305.

[29]

W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control, Springer, 2008.

[30]

G. ShiB. 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.

[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.

[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.

[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.

[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.

[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.

[36]

N. H. Vaidya, Iterative byzantine vector consensus in incomplete graphs, in International Conference on Distributed Computing and Networking, (2014), 14–28.

[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.

[38]

X. WangS. Mou and D. Sun, Improvement of a distributed algorithm for solving linear equations, IEEE Transactions on Industrial Electronics, 64 (2017), 3113-3117. 

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.

[2]

B. D. O. AndersonS. MouU. 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.

[3]

C. B. BarberD. 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.

[4]

Z. BouzidM. 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.

[5] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.  doi: 10.1017/CBO9780511804441.
[6]

M. CaoA. S. Morse and B. D. O. Anderson, Agree asychronously, IEEE Transactions on Automatic Control, 53 (2008), 1826-1838.  doi: 10.1109/TAC.2008.929387.

[7]

M. CaoA. 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.

[8]

T. ChangA. 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.

[9]

X. ChenM. A. Belabbas and T. Basar, Distributed averaging with linear objective maps, Automatica, 70 (2016), 179-188.  doi: 10.1016/j.automatica.2016.03.023.

[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.

[11]

L. LamportR. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4 (1982), 382-401. 

[12]

H. J. LeBlaneH. ZhangX. Koutsoukos and S. Sundaram, Resilient asymptotic consensus in robust networks, IEEE Journal on Selected Areas in Communications, 31 (2013), 766-781. 

[13]

J. LinA. 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.

[14]

J. LiuS. MouA. S. MorseB. D. O. Anderson and C. Yu, Deterministic gossiping, Proceedings of the IEEE, 99 (2011), 1505-1524. 

[15]

Q. LiuS. 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.

[16]

H. MendesM. HerlihyN. Vaidya and V. Garg, Multidimensional agreement in byzantine systems, Distributed Computing, 28 (2015), 423-441.  doi: 10.1007/s00446-014-0240-5.

[17]

S. Mou and M. Cao, Distributed averaging using compensation, IEEE Communication Letters, 17 (2013), 1672-1675. 

[18]

S. MouZ. LinL. WangD. 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.

[19]

S. MouJ. 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.

[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.

[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.

[22]

A. NedicA. 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.

[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.

[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.

[25]

H. Park and S. A. Hutchinson, Fault-tolerant rendezvous of multirobot systems, IEEE Transactions on Robotics, 33 (2017), 565-582. 

[26]

F. PasqualettiA. 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.

[27]

F. PasqualettiF. 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.

[28]

L. A. Rademacher, Approximating the centroid is hard, in Proceedings of the twenty-third annual symposium on Computational geometry, (2007), 302–305.

[29]

W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control, Springer, 2008.

[30]

G. ShiB. 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.

[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.

[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.

[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.

[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.

[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.

[36]

N. H. Vaidya, Iterative byzantine vector consensus in incomplete graphs, in International Conference on Distributed Computing and Networking, (2014), 14–28.

[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.

[38]

X. WangS. Mou and D. Sun, Improvement of a distributed algorithm for solving linear equations, IEEE Transactions on Industrial Electronics, 64 (2017), 3113-3117. 

Figure 1.  Finding Tverberg point $ \mathcal{T} $ (yellow) and $ \mathcal{R} $ (red) in a 2-D space, with $ \bar{\mathcal{A}} = \{1\} $
Figure 2.  A network of 11 agents with malicious agents marked in red
Figure 3.  Simulations of normal agents under the consensus update (20) without malicious agents (blank line) and with malicious agents $ 10 $ and $ 11 $ (red line)
Figure 4.  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)
Figure 5.  Simulations by using the resilient convex combination $ u_i(t) $ of (17) into (22)
Figure 6.  Simulation results under the update (23) with no malicious agents (indicated by the black line) or with malicious agents (indicated by the red line)
Figure 7.  Simulations by using the resilient convex combination $ u_i(t) $ of (17) in (23)
[1]

Richard Carney, Monique Chyba, Chris Gray, George Wilkens, Corey Shanbrom. Multi-agent systems for quadcopters. Journal of Geometric Mechanics, 2022, 14 (1) : 1-28. doi: 10.3934/jgm.2021005

[2]

Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020

[3]

Ke Yang, Wencheng Zou, Zhengrong Xiang, Ronghao Wang. Fully distributed consensus for higher-order nonlinear multi-agent systems with unmatched disturbances. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1535-1551. doi: 10.3934/dcdss.2020396

[4]

Nadia Loy, Andrea Tosin. Boltzmann-type equations for multi-agent systems with label switching. Kinetic and Related Models, 2021, 14 (5) : 867-894. doi: 10.3934/krm.2021027

[5]

Mei Luo, Jinrong Wang, Yumei Liao. Bounded consensus of double-integrator stochastic multi-agent systems. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022088

[6]

Rui Li, Yingjing Shi. Finite-time optimal consensus control for second-order multi-agent systems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 929-943. doi: 10.3934/jimo.2014.10.929

[7]

Xi Zhu, Meixia Li, Chunfa Li. Consensus in discrete-time multi-agent systems with uncertain topologies and random delays governed by a Markov chain. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4535-4551. doi: 10.3934/dcdsb.2020111

[8]

Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489

[9]

Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022

[10]

Hongru Ren, Shubo Li, Changxin Lu. Event-triggered adaptive fault-tolerant control for multi-agent systems with unknown disturbances. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1395-1414. doi: 10.3934/dcdss.2020379

[11]

Xiaojin Huang, Hongfu Yang, Jianhua Huang. Consensus stability analysis for stochastic multi-agent systems with multiplicative measurement noises and Markovian switching topologies. Numerical Algebra, Control and Optimization, 2022, 12 (3) : 601-610. doi: 10.3934/naco.2021024

[12]

Giulia Cavagnari, Antonio Marigonda, Benedetto Piccoli. Optimal synchronization problem for a multi-agent system. Networks and Heterogeneous Media, 2017, 12 (2) : 277-295. doi: 10.3934/nhm.2017012

[13]

Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022001

[14]

Seung-Yeal Ha, Dohyun Kim, Jaeseung Lee, Se Eun Noh. Emergent dynamics of an orientation flocking model for multi-agent system. Discrete and Continuous Dynamical Systems, 2020, 40 (4) : 2037-2060. doi: 10.3934/dcds.2020105

[15]

Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623

[16]

Tyrone E. Duncan. Some partially observed multi-agent linear exponential quadratic stochastic differential games. Evolution Equations and Control Theory, 2018, 7 (4) : 587-597. doi: 10.3934/eect.2018028

[17]

Hong Man, Yibin Yu, Yuebang He, Hui Huang. Design of one type of linear network prediction controller for multi-agent system. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 727-734. doi: 10.3934/dcdss.2019047

[18]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete and Continuous Dynamical Systems - B, 2021, 26 (4) : 1827-1842. doi: 10.3934/dcdsb.2020364

[19]

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

[20]

Yejuan Wang, Tomás Caraballo. Morse decomposition for gradient-like multi-valued autonomous and nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (8) : 2303-2326. doi: 10.3934/dcdss.2020092

 Impact Factor: 

Metrics

  • PDF downloads (302)
  • HTML views (570)
  • Cited by (5)

Other articles
by authors

[Back to Top]