One of the intensely studied concepts of network robustness is r-robustness, which is a network topology property quantified by an integer r. It is required by mean subsequence reduced (MSR) algorithms and their variants to achieve resilient consensus. However, determining r-robustness is intractable for large networks. In this paper, we propose a sample-based algorithm to approximately test r-robustness of a digraph with n vertices and m edges. For a digraph with a moderate assumption on the minimum in-degree, and an error parameter 0 < epsilon <= 1, the proposed algorithm distinguishes (r+epsilon n)-robust graphs from graphs which are not r-robust with probability (1-delta). Our algorithm runs in exp(O((ln 1/epsilon delta)/epsilon(2))).m time. The running time is linear in the number of edges if epsilon is a constant.

The paper considers continuous-time networked susceptible-infected-susceptible (SIS) diseases spreading over a population. Each agent represents a sub-population and has its own healing rate and infection rate; the state of the agent at a time instant denotes what fraction of the said sub-population is infected with the disease at the said time instant. By taking account of the changes in behaviors of the agents in response to the infection rates in real-time, our goal is to devise a feedback strategy such that the infection level for each agent strictly stays below a pre-specified value. Furthermore, we are also interested in ensuring that the closed-loop system converges either to the disease-free equilibrium or, when it exists, to the endemic equilibrium. The upshot of devising such a strategy is that it allows health administration officials to ensure that there is sufficient capacity in the healthcare system to treat the most severe cases. We demonstrate the effectiveness of our controller via numerical examples. Copyright

This paper presents an overview on the recent advances in the research of security of cyber-physical systems. We place particular emphases on consensus problems for multi-agent systems in hostile environments and their analyses on the resiliency against two types of attacks. First, we discuss a class of data injection attacks by focusing on the approach based on mean subsequence reduced (MSR) algorithms and their variants. Agents equipped with such algorithms will ignore their neighbors taking extreme state values. Characterizations on the properties necessary for network topologies and moreover a number of extensions with enhanced resiliency will be established. As the second class of attacks, the effects of denial-of-service (DoS) attacks will be examined in the context of multi-agent consensus. By employing a DoS model based on the energy constraints of the attacker, we will observe that robustness against such attacks may depend on system properties such as dynamics of the individual agents and network structures. Applications of the algorithms will be further discussed for clock synchronization in wireless sensor networks and control of a group of mobile robots.

This paper addresses novel consensus problems for multi-agent systems operating in an unreliable environment where adversaries are spreading. The dynamics of the adversarial spreading processes follows the susceptible-infected-recovered (SIR) model, where the infection induces faulty behaviors in the agents and affects their state values. Such a problem setting serves as a model of opinion dynamics in social networks where consensus is to be formed at the time of pandemic and infected individuals may deviate from their true opinions. To ensure resilient consensus among the noninfectious agents, the difficulty is that the number of infectious agents changes over time. We assume that a local policy maker announces the local level of infection in real-time, which can be adopted by the agent for its preventative measures. It is demonstrated that this problem can be formulated as resilient consensus in the presence of the socalled mobile malicious models, where the mean subsequence reduced (MSR) algorithms are known to be effective. We characterize sufficient conditions on the network structures for different policies regarding the announced infection levels and the strength of the epidemic. Numerical simulations are carried out for random graphs to verify the effectiveness of our approach.

This article addresses novel real-valued consensus problems in the presence of malicious adversaries that can move within the network and induce faulty behaviors in the attacked agents. By adopting several mobile adversary models from the computer science literature, we develop protocols which can mitigate the influence of such malicious agents. The algorithms follow the class of mean subsequence reduced (MSR) algorithms, under which agents ignore the suspicious values received from neighbors during their state updates. Different from the static adversary models, even after the adversaries move away, the infected agents may remain faulty in their values, whose effects must be taken into account. We develop conditions on the network structures for both the complete and non-complete directed graph cases, under which the proposed algorithms are guaranteed to attain resilient consensus. The tolerance bound for network conditions becomes more strict as the adversaries are allowed to have more power. Extensive simulations are carried out over random graphs to verify the effectiveness of our approach when the information of the adversarial agents in terms of their models and numbers is unknown to the agents.

In this paper, we consider the problem of multi-agent consensus in the presence of mobile adversaries. Faulty agents try to prevent the coordination among the regular agents and moreover are mobile in the sense that they can change their identities over time. Our approach towards resilient consensus is to extend the so-called mean subsequence reduced (MSR) algorithms to reduce the necessary communication based on two measures: The information exchanged by the agents takes the form of ternary data in each message and furthermore self-triggered method is used to keep the transmission frequency limited. Certain features are introduced to address issues specific to the mobile nature of the adversarial agents. We verify the effectiveness of the proposed algorithm by means of a numerical example.

This paper addresses novel consensus problems for multi-agent systems operating in a pandemic environment where infectious diseases are spreading. The dynamics of the diseases follows the susceptible-infected-recovered (SIR) model, where the infection induces faulty behaviors in the agents and affects their state values. To ensure resilient consensus among the noninfectious agents, the difficulty is that the number of infectious agents changes over time. We assume that a high-level policy maker announces the level of infection in real-time, which can be adopted by the agents for their preventative measures. It is demonstrated that this problem can be formulated as resilient consensus in the presence of the socalled mobile malicious models, where the mean subsequence reduced (MSR) algorithms are known to be effective. We characterize sufficient conditions on the network structures for different policies regarding the announced infection levels and the strength of the pandemic. Numerical simulations are carried out for random graphs to verify the effectiveness of our approach. 

This paper considers the problem of multi-agent consensus in the presence of adversarial agents. Such adversaries may try to introduce undesired influence on the coordination of the regular agents and to even prevent them from reaching consensus. To our setting, we extend the so-called mean subsequence reduced algorithms with the aim to reduce the use of computation and communication resources of the agents. In particular, by employing self-and event-triggered communication, the frequencies of state updates as well as data transmissions are kept low. Moreover, the control inputs of the agents take the form of ternary signals, allowing them to further reduce the amount of information at each transmission. We will observe that in hostile environments with adversaries, the self-triggered approach can bring certain advantages over the event-triggered counterpart. Moreover, a novel switching scheme is introduced to mix the two protocols to further enhance the performance of the agents.

This paper considers the susceptible-infected-susceptible (SIS) epidemic model with an underlying network structure and focuses on the effect of social distancing to regulate the epidemic level. We demonstrate that if each subpopulation is informed of its infection rate and reduces interactions accordingly, the fraction of the subpopulation infected stays below half for all time instants. To this end, we first modify the basic SIS model by introducing a state dependent parameter representing the frequency of interactions between subpopulations. Thereafter, we show that for this modified SIS model, the spectral radius of a suitably-defined matrix being not greater than one causes all the agents, regardless of their initial sickness levels, to converge to the healthy state; assuming non-trivial disease spread, the spectral radius being greater than one leads to the existence of a unique endemic equilibrium, which is also asymptotically stable. Finally, by leveraging the aforementioned results, we show that the fraction of (sub)populations infected never exceeds half. Copyright