Resilient Vector Consensus in Multi-Agent Networks Using Centerpoints
Authors:
- Mudassir ShabbirMSMudassir Shabbir
- Jiani LiJLJiani Li
- Waseem AbbasWAWaseem Abbas
- Xenofon KoutsoukosXKXenofon Koutsoukos
Preprint
Abstract
In this paper, we study the resilient vector consensus problem in multi-agent networks and improve resilience guarantees of existing algorithms. In resilient vector consensus, agents update their states, which are vectors in $\mathbb{R}^d$, by locally interacting with other agents some of which might be adversarial. The main objective is to ensure that normal (non-adversarial) agents converge at a common state that lies in the convex hull of their initial states. Currently, resilient vector consensus algorithms, such as approximate distributed robust convergence (ADRC) are based on the idea that to update states in each time step, every normal node needs to compute a point that lies in the convex hull of its normal neighbors' states. {To compute such a point, the idea of Tverberg partition is typically used, which is computationally hard. Approximation algorithms for Tverberg partition negatively impact the resilience guarantees of consensus algorithm.} To deal with this issue, we propose to use the idea of centerpoint, which is an extension of median in higher dimensions, instead of Tverberg partition. We show that the resilience of such algorithms to adversarial nodes is improved if we use the notion of centerpoint. Furthermore, using centerpoint provides a better characterization of the necessary and sufficient conditions guaranteeing resilient vector consensus. We analyze these conditions in two, three, and higher dimensions separately. Finally, we numerically evaluate the performance of our approach through various experiments.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Improving Network Connectivity and Robustness Using Trusted Nodes With Application to Resilient ConsensusIEEE Transactions on Control of Network Systems, 2017
- Fault-Tolerant Rendezvous of Multirobot SystemsIEEE Transactions on Robotics, 2017
- Approximating Tverberg Points in Linear Time for Any Fixed DimensionDiscrete & Computational Geometry, 2013
- Resilient Asymptotic Consensus in Robust NetworksIEEE Journal on Selected Areas in Communications, 2013
- Approximate centerpoints with proofsComputational Geometry, 2010
- New cases of Reay’s conjecture on partitions of points into simplices with -dimensional intersectionEuropean Journal of Combinatorics, 2009
- An optimal extension of the centerpoint theoremComputational Geometry, 2009
- Computing a centerpoint of a finite planar set of points in linear timeDiscrete & Computational Geometry, 1994
- Cutting hyperplanes for divide-and-conquerDiscrete & Computational Geometry, 1993
- Partitioning with two lines in the planeJournal of Algorithms, 1985