A resilient convex combination for consensus-based distributed algorithms

Xuan Wang; Shaoshuai Mou; Shreyas Sundaram

doi:10.3934/naco.2019018

Article Contents

2019, Volume 9, Issue 3: 269-281. Doi: 10.3934/naco.2019018

This issue Previous Article Bearing rigidity and formation stabilization for multiple rigid bodies in

$ SE(3) $

Next Article Optimal sparse output feedback for networked systems with parametric uncertainties

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
^* Corresponding author: Shaoshuai Mou, mous@purdue.edu

Received: April 2018

Revised: April 2019

Published: May 2019

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

Abstract / Introduction Full Text(HTML) Figure(7) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 68Q85; Secondary: 11D04.

Citation:

FullText(HTML)

Figure 1. Finding Tverberg point $ \mathcal{T} $ (yellow) and $ \mathcal{R} $ (red) in a 2-D space, with $ \bar{\mathcal{A}} = \{1\} $

Download: Full-size image PowerPoint slide

Figure 2. A network of 11 agents with malicious agents marked in red

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

Figure 5. Simulations by using the resilient convex combination $ u_i(t) $ of (17) into (22)

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

Figure 7. Simulations by using the resilient convex combination $ u_i(t) $ of (17) in (23)

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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. 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.
[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.
[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.
[5]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004. doi: 10.1017/CBO9780511804441.
[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.
[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.
[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.
[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.
[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. Lamport, R. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4 (1982), 382-401.
[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.
[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.
[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.
[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.
[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.
[17]	S. Mou and M. Cao, Distributed averaging using compensation, IEEE Communication Letters, 17 (2013), 1672-1675.
[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.
[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.
[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. 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.
[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. 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.
[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.
[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. 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.
[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. Wang, S. Mou and D. Sun, Improvement of a distributed algorithm for solving linear equations, IEEE Transactions on Industrial Electronics, 64 (2017), 3113-3117.