# 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:

show all references

##### References:
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] 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 & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2020111 [6] 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 [7] Seung-Yeal Ha, Dohyun Kim, Jaeseung Lee, Se Eun Noh. Emergent dynamics of an orientation flocking model for multi-agent system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (4) : 2037-2060. doi: 10.3934/dcds.2020105 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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) : 0-. doi: 10.3934/dcdss.2020092 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] 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

Impact Factor: