Low Complexity Resilient Consensus in Networked Multi-Agent Systems with Adversaries

Authors: Heath J. LeBlanc, Xenofon Koutsoukos

Accepted for the Hybrid Systems: Computation and Control 2012 (HSCC 2012) conference,

ABSTRACT
Recently, many applications have arisen in distributed control that
require consensus protocols. Concurrently, we have seen a proliferation
of malicious attacks on large-scale distributed systems.
Hence, there is a need for (i) consensus problems that take into
consideration the presence of adversaries and specify correct behavior
through appropriate conditions on agreement and safety, and
(ii) algorithms for distributed control applications that solve such
consensus problems resiliently despite breaches in security. This
paper addresses these issues by (i) defining the adversarial asymptotic
agreement problem, which requires that the uncompromised
agents asymptotically align their states while satisfying an invariant
condition in the presence of adversaries, and (ii) by designing
a low complexity consensus protocol, the Adversarial Robust Consensus
Protocol (ARC-P), which combines ideas from distributed
computing and cooperative control. Two types of omniscient adversaries
are considered: (i) Byzantine agents can convey different
state trajectories to different neighbors in the network, and (ii) malicious
agents must convey the same information to each neighbor.
For each type of adversary, sufficient conditions are provided that
ensure ARC-P guarantees the agreement and safety conditions in
static and switching network topologies, whenever the number of
adversaries in the network is bounded by a constant. The conservativeness
of the conditions is examined, and the conditions are
compared to results in the literature.