r-robustness

In the presence of adversarial or faulty agents, the agents locally cannot figure out which agents are reliable. In that case, the agents cannot perform distributed algorithms effectively. However, if the network is \(r\)-robust, then the agents can still perform distributed algorithms effectively.

Throughout, \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) is a graph on \(n\) nodes and \(\mathcal{N}_i\) is the neighbour set of node \(i\). For digraphs, read \(\mathcal{N}_i\) as the set of in-neighbours everywhere below.

The definitions

Reachability is a property that one node can talk to the outside of a subset. Robustness means that agents are able to communicate outside of any subsets. This ensures that agents have enough redundnacy in communication.

One structural detail matters later: the quantifier ranges over every possible pair of nonempty, disjoint subsets. This makes the condition expensive to check.

The W-MSR algorithm

Weighted Mean Subsequence Reduced (W-MSR)is the standard resilient consensus rule. At each step, normal node \(i\) collects its neighbours' values, discards the \(F\) largest that are strictly greater than \(x_i[k]\) and the \(F\) smallest that are strictly less, and updates as a convex combination of its own value and the retained set \(\mathcal{R}_i[k]\):

$$x_i[k+1] = w_{ii}[k]\,x_i[k] + \sum_{j \in \mathcal{R}_i[k]} w_{ij}[k]\,x_j[k],$$

with all weights bounded below by some \(\alpha > 0\) and summing to one. Nobody has to identify the adversaries. Under the \(F\)-local model - at most \(F\) adversaries in any normal node's neighbourhood - the filter alone does the work.

Then the agents can perform within the "safe regions" (within the convex hull of their initial values) and reach a consensus.

Why filtering is safe

Local Perspective: you have possibly \(F\) adversaries in your neighbourhood. You discard the \(F\) largest and \(F\) smallest values, so you are guaranteed to have values within the convex hull of the normal values.

Global Perspective: r-robustness ensures that the network remains connected even every node loses r-1 edges. So, if the network is (2F+1)-robust, then the network remains connected even each agent loses 2F edges (which happens by filtering at most 2F values out).

The proof is three lines. Suppose the surviving graph were disconnected and let \(\mathcal{S}_1, \mathcal{S}_2\) be two of its components. They are nonempty and disjoint, so robustness gives a node \(v\) in one of them with \(r\) neighbours outside it. At most \(r-1\) of those were deleted. So \(v\) still reaches outside, and it was never a component. Contradiction.

Note how different this accounting is from connectivity. \(r\)-connectivity tolerates \(r-1\) edge removals in total. Robustness tolerates \(r-1\) removals from every agent.

The (\(r,s)\)-robustness

If instead at most \(F\) agents are adversarial in the whole network, we can have better conditiosn and guarantees. Write

$$\mathcal{X}^r_{\mathcal{S}} = \big\{ i \in \mathcal{S} \ :\ |\mathcal{N}_i \setminus \mathcal{S}| \ge r \big\}$$

for the nodes of \(\mathcal{S}\) that are individually \(r\)-reachable. Then \(G\) is \((r,s)\)-robust if for every nonempty disjoint pair at least one of

$$\big|\mathcal{X}^r_{\mathcal{S}_1}\big| = |\mathcal{S}_1|, \qquad \big|\mathcal{X}^r_{\mathcal{S}_2}\big| = |\mathcal{S}_2|, \qquad \big|\mathcal{X}^r_{\mathcal{S}_1}\big| + \big|\mathcal{X}^r_{\mathcal{S}_2}\big| \ge s$$

holds. Ordinary \(r\)-robustness is the case \((r,1)\). For W-MSR under the \(F\)-total malicious model, \((F+1, F+1)\)-robustness is necessary and sufficient.

Why r is hard to compute

The decision problem is: given \(G\) and an integer \(r\), is \(G\) \(r\)-robust? The two possible answers are lopsided.

"Not robust" is cheap to certify. Exhibit one pair \((\mathcal{S}_1, \mathcal{S}_2)\) in which neither set is \(r\)-reachable. Verifying it means counting outside neighbours for the nodes in those two sets, which is linear in the graph. So the complement problem is in NP, which puts \(r\)-robustness in coNP.

Proxy metrics: minimum degree and connectivity

Both standard structural measures are polynomial - minimum degree \(\delta(G)\) trivially, vertex connectivity \(\kappa(G)\) by max-flow - and both relate cleanly to robustness:

$$G \text{ is } r\text{-robust} \ \Longrightarrow\ G \text{ is } r\text{-connected} \ \Longrightarrow\ \delta(G) \ge r.$$

Writing \(r^\star(G)\) for the largest \(r\) that holds, this chain says

$$r^\star(G) \ \le\ \kappa(G) \ \le\ \delta(G) ,$$

which is an upper bound, sometimes very loose. Consider two cliques joined by a perfect matching have \(\kappa = \delta = n/2\) but \(r^\star = 1\), so the gap can be as wide as the graph permits. The only unconditional coincidence is at \(r = 1\), where 1-robust and 1-connected are the same property. There is also a ceiling, \(r^\star \le \lceil n/2 \rceil\), attained by \(K_n\).

Further reading

• LeBlanc, Zhang, Koutsoukos, Sundaram, “Resilient asymptotic consensus in robust networks,” IEEE JSAC 31(4), 2013. Origin of \(r\)- and \((r,s)\)-robustness and the W-MSR convergence conditions.
• Zhang, Fata, Sundaram, “A notion of robustness in complex networks,” IEEE TCNS 2(3), 2015. Random-graph thresholds and the coNP-completeness proof.
• Usevitch, Panagou, “Determining \(r\)- and \((r,s)\)-robustness of digraphs using mixed integer linear programming” Automatica 111, 2020. MILP to compute r- and (r,s)-robustness.
• Lee, Panagou, “Minimal construction of graphs with maximum robustness ” IEEE TAC 2027. Sparsest graphs with maximum r- and (r,s)-robustness.