Resilient group consensus in the presence of Byzantine agents

Abstract

In this paper, we address the resilient group consensus of multi-agent networks in the presence of structured and unstructured Byzantine faults. In the case of structured Byzantine faults that feed different but structured values to the network, it is shown that non-faulty nodes can achieve group consensus without using any fault tolerant algorithm. Necessary and sufficient conditions on the network are derived so that the conventional consensus algorithm leads to group consensus values in the range determined by the initial values of the non-faulty nodes. In the presence of unstructured Byzantine faults, two fault tolerant algorithms are proposed to overcome the highly disruptive behaviour. Subsequently, convergence analysis of these algorithms is carried out by exploiting the robustness properties of the network. Finally, theoretical results are illustrated with several simulation examples.

Keywords:

• Fault tolerant consensus
• Byzantine faults
• approximate Byzantine group consensus
• robust networks

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 Throughout the paper, the term agent is interchangeably referred to as node.

2 A spanning tree exists in a digraph if there exists a directed tree formed by directed graph edges that connect all the nodes of the graph (Godsil & Royle, 2013).

3 Given two graphs $G=(V,E)$ and $\tilde{G}=(\tilde{V},\tilde{E})$, $\tilde{G}$ is said to be a subgraph of G if $\tilde{V}\subseteq V$ and $\tilde{E}\subseteq E\cap (\tilde{V}\times \tilde{V})$ hold for $\tilde{G}$.

4 The notation $x_{ij}\left[k\right]$ is used to model faulty behaviour, whereas $x_i\left[k\right]$ refers to the non-faulty behaviour, i.e. $x_{ij}\left[k\right]$ is the state value of the faulty node j that is sent to node i and $x_i\left[k\right]$ is the state value of the non-faulty node i.

5 Pseudo-code of the L-MSR algorithm is given in Algorithm 1.

6 Minimum in-degree of a graph G, denoted by ${\delta }^{in}\left(G\right)$, is the minimum number of incoming edges for all vertices of the graph G (LeBlanc et al., 2013).

Additional information

Funding

This work was sponsored by Scientific and Technical Research Council of Turkey (Türkiye Bilimsel ve Teknolojik Araştirma Kurumu) under TUBITAK Grant 114E613.