Task 3.1: Mean Subsequence Reduced (MSR) Algorithms for Resilient Distributed Optimization
Most of the resilient protocols proposed in the literature leverage the so-called mean subsequence reduced (MSR) algorithm, mainly known for its simplicity and scalability [18]. MSR algorithms simply order solution estimations in ascending (or descending order) and remove F top and lowest values from the ordered list, where F is an a-priori fixed bound to the number of malicious agents. Then, the average among the remaining values is computed and a standard linear consensus update equation is applied. The key idea in most of these existing algorithms is to avoid utilizing malicious states broadcast by adversarial agents to guarantee that the final state is within the interval of the smallest initial state and the largest one.
The first aim is to strengthen the CPS resilience to cyber-attacks by proposing novel MSR-based distributed optimization algorithms that largely extend the ones proposed in the literature. Specifically, the task aims at addressing the following issues:
1. Several minimal graph properties (i.e. s-r robustness, the existence of a dominant set) are shown to be critical for the network structure to guarantee the success of resilient distributed optimization algorithms. In this respect we greatly enlarge the analysis of such structural properties to the scenario of weighted CPS graphs, allowing different levels of trust attributed to different neighbors, thus breaking the symmetry implicit in the topological assumption of MSR mechanisms. This feature plays a focal role in dealing with the safety of modern CPSs where individuals and groups are characterized by different levels of trust/reputation.
2. In most standard distributed optimization algorithms, only local solution estimations are exchanged. Although directly exchanging gradients might not be necessary, it would be interesting to analyze and quantify the gain in exchanging gradient information. In addition, the MSR mechanism will be applied to auxiliary local variables that asymptotically track the gradient of the global cost, in order to both use a fixed step-size (overcoming the drawback of slow convergence due to the diminishing step-sizes) and further enhance the resilience of the overall CPS.
Task 3.2: Robustification of Distributed Optimization Algorithms for CPS
Link failures, latency and information alteration naturally occur in CPS applications due to network imperfections. Also, denial of service (DoS) and flooding attacks can force dropped packets and induce time delays. Previous literature has not thoroughly investigated the effect of network disruptions on distributed optimization performance. A further contribution of the project concerns the analysis and robustification of resilient distributed optimization algorithms against link failures, largely extending the scenario usually considered in the literature. The contributions of the task are:
- In distributed optimization algorithms the exchange of solution estimation and/or gradient information is crucial. However, if communication links are unreliable or subject to attacks, the convergence process of the algorithms can be seriously disrupted. The task aims at implementing filters on the solution and gradient data which only accept values compatible with underlying assumptions about the considered scenario (i.e. convexity of optimality functions, level of heterogeneity of agents’ behavior, constraints on the global minimizer). These can enhance the robustness of the optimization algorithm with respect to both exogenous attacks and unreliable communications.
- Robustifying distributed optimization against link failures is a focal aim to address the implementation of distributed optimization approaches in a realistic scenario of CPS applications (i.e. supervision and control of vehicles, smart grids). We firstly investigate the behavior of consensus-based optimization algorithms in the presence of unreliable communication channels where messages can be lost. Then, we aim at designing packet loss tolerant optimization algorithms by integrating the ones at Task 3.1 with a consensus mechanism that is robust to link failures.
