Consensus of Multi-Agent Networks in the Presence of Adversaries Using Only Local Information

Authors: Heath J. LeBlanc, Haotian Zhang, Shreyas Sundaram, Xenofon Koutsoukos

Conference on High Confidence Networked Systems (HiCoNS) at CPSWeek 2012

Abstract:

This paper addresses the problem of resilient consensus in the presence
of misbehaving nodes. Although it is typical to assume knowledge
of at least some nonlocal information when studying secure
and fault-tolerant consensus algorithms, this assumption is not suitable
for large-scale dynamic networks. To remedy this, we emphasize
the use of local strategies to deal with resilience to security
breaches. We study a consensus protocol that uses only
local information and we consider worst-case security breaches,
where the compromised nodes have full knowledge of the network
and the intentions of the other nodes. We provide necessary and
sufficient conditions for the normal nodes to reach consensus despite
the influence of the malicious nodes under different threat assumptions.
These conditions are stated in terms of a novel graphtheoretic
property referred to as network robustness.