Resilient distributed vector consensus using centerpoint

DOI10.1016/J.AUTOMATICA.2021.110046MaRDI QIDQ2063807zbMATH OpenOpenAlexFDO

Authors Waseem Abbas, Mudassir Shabbir, Jiani Li, Xenofon D. Koutsoukos

Publication date 3 January 2022

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.05497

zbMATH Keywords

computational geometrycenterpointresilient consensusfault tolerant networks

Mathematics Subject Classification ID

Multi-agent systems (93A16) Networked control (93B70) Consensus (93D50)

Abstract: In this paper, we study the resilient vector consensus problem in networks with adversarial agents and improve resilience guarantees of existing algorithms. A common approach to achieving resilient vector consensus is that every non-adversarial (or normal) agent in the network updates its state by moving towards a point in the convex hull of its emph{normal} neighbors' states. Since an agent cannot distinguish between its normal and adversarial neighbors, computing such a point, often called as emph{safe point}, is a challenging task. To compute a safe point, we propose to use the notion of emph{centerpoint}, which is an extension of the median in higher dimensions, instead of Tverberg partition of points, which is often used for this purpose. We discuss that the notion of centerpoint provides a complete characterization of safe points in $mathbb{R}^d$. In particular, we show that a safe point is essentially an interior centerpoint if the number of adversaries in the neighborhood of a normal agent $i$ is less than $frac{N}_{i}d+1$, where $d$ is the dimension of the state vector and $N_i$ is the total number of agents in the neighborhood of $i$. Consequently, we obtain necessary and sufficient conditions on the number of adversarial agents to guarantee resilient vector consensus. Further, by considering the complexity of computing centerpoints, we discuss improvements in the resilience guarantees of vector consensus algorithms and compare with the other existing approaches. Finally, we numerically evaluate the performance of our approach through experiments.

Recommendations

• Resilient multi-dimensional consensus in adversarial environment
• A resilient convex combination for consensus-based distributed algorithms
• Low complexity resilient consensus in networked multi-agent systems with adversaries
• General resilient consensus algorithms
• Relaxed Byzantine vector consensus

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• A resilient convex combination for consensus-based distributed algorithms
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• An extension of Radon's theorem
• Approximate centerpoints with proofs
• Approximating Tverberg points in linear time for any fixed dimension
• Byzantine vector consensus in complete graphs
• Distributed Optimization Under Adversarial Nodes
• Improving Network Connectivity and Robustness Using Trusted Nodes With Application to Resilient Consensus
• Iterative approximate Byzantine consensus under a generalized fault model
• Multidimensional agreement in Byzantine systems
• New cases of Reay's conjecture on partitions of points into simplices with \(k\)-dimensional intersection
• The Critical Set of a Convex Body

Cited in

(4)

• Matrix-scaled resilient consensus of discrete-time and continuous-time networks
• On the geometric convergence of Byzantine-resilient distributed optimization algorithms
• On the non-resiliency of subsequence reduced resilient consensus in multiagent networks
• Resilient consensus in continuous-time networks with \(\ell\)-hop communication and time delay

This page was built for publication: Resilient distributed vector consensus using centerpoint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2063807)