Hideaki Ishii

Kai Cai, Hideaki Ishii

We study the average consensus problem of multi-agent systems for general network topologies with unidirectional information flow. We propose two (linear) distributed algorithms, deterministic and gossip, respectively for the cases where the inter-agent communication is synchronous and asynchronous. Our contribution is that in both cases, the developed algorithms guarantee state averaging on arbitrary strongly connected digraphs; in particular, this graphical condition does not require that the network be balanced or symmetric, thereby extending many previous results in the literature. The key novelty of our approach is to augment an additional variable for each agent, called "surplus", whose function is to locally record individual state updates. For convergence analysis, we employ graph-theoretic and nonnegative matrix tools, with the eigenvalue perturbation theory playing a crucial role.

Seyed Mehran Dibaji, Hideaki Ishii

We study the problem of resilient consensus of sampled-data multi-agent networks with double-integrator dynamics. The term resilient points to algorithms considering the presence of attacks by faulty/malicious agents in the network. Each normal agent updates its state based on a predetermined control law using its neighbors' information which may be delayed while misbehaving agents make updates arbitrarily and might threaten the consensus within the network. Assuming that the maximum number of malicious agents in the system is known, we focus on algorithms where each normal agent ignores large and small position values among its neighbors to avoid being influenced by malicious agents. The malicious agents are assumed to be omniscient in that they know the updating times and delays and can collude with each other. We deal with both synchronous and partially asynchronous cases with delayed information and derive topological conditions in terms of graph robustness.

Seyed Mehran Dibaji, Hideaki Ishii, Roberto Tempo

We consider the problem of multi-agent consensus where some agents are subject to faults/attacks and might make updates arbitrarily. The network consists of agents taking integer-valued (i.e., quantized) states under directed communication links. The goal of the healthy normal agents is to form consensus in their state values, which may be disturbed by the non-normal, malicious agents. We develop update schemes to be equipped by the normal agents whose interactions are asynchronous and subject to non-uniform and time-varying time delays. In particular, we employ a variant of the so-called mean subsequence reduced (MSR) algorithms, which have been long studied in computer science, where each normal agent ignores extreme values from its neighbors. We solve the resilient quantized consensus problems in the presence of totally/locally bounded adversarial agents and provide necessary and sufficient conditions in terms of the connectivity notion of graph robustness. Furthermore, it will be shown that randomization is essential both in quantization and in the updating times when normal agents interact in an asynchronous manner. The results are examined through a numerical example.

Ahmet Cetinkaya, Hideaki Ishii, Tomohisa Hayakawa

We study cyber security issues in networked control of a linear dynamical system. Specifically, the dynamical system and the controller are assumed to be connected through a communication channel that face malicious attacks as well as random packet losses due to unreliability of transmissions. We provide a probabilistic characterization for the link failures which allows us to study combined effects of malicious and random packet losses. We first investigate almost sure stabilization under an event-triggered control law, where we utilize Lyapunov-like functions to characterize the triggering times at which the plant and the controller attempt to exchange state and control data over the network. We then provide a look at the networked control problem from the attacker's perspective and explore malicious attacks that cause instability. Finally, we demonstrate the efficacy of our results with numerical examples.

Hideaki Ishii, Roberto Tempo

In the search engine of Google, the PageRank algorithm plays a crucial role in ranking the search results. The algorithm quantifies the importance of each web page based on the link structure of the web. We first provide an overview of the original problem setup. Then, we propose several distributed randomized schemes for the computation of the PageRank, where the pages can locally update their values by communicating to those connected by links. The main objective of the paper is to show that these schemes asymptotically converge in the mean-square sense to the true PageRank values. A detailed discussion on the close relations to the multi-agent consensus problems is also given.

Hideaki Ishii, Roberto Tempo, Er-Wei Bai

The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus.

Ahmet Cetinkaya, Hideaki Ishii, Tomohisa Hayakawa

We investigate the stability problem for discrete-time stochastic switched linear systems under the specific scenarios where information about the switching patterns and the probability of switches are not available. Our analysis focuses on the average number of times each mode becomes active in the long run and, in particular, utilizes their lower- and upper-bounds. This setup is motivated by cyber security issues for networked control systems in the presence of packet losses due to malicious jamming attacks where the attacker's strategy is not known a priori. We derive a sufficient condition for almost sure asymptotic stability of the switched systems which can be examined by solving a linear programming problem. Our approach exploits the dynamics of an equivalent system that describes the evolution of the switched system's state at every few steps; the stability analysis may become less conservative by increasing the step size. The computational efficiency is further enhanced by exploiting the structure in the stability analysis problem, and we introduce an alternative linear programming problem that has fewer variables. We demonstrate the efficacy of our results by analyzing networked control problems where communication channels face random packet losses as well as jamming attacks.

Ahmet Cetinkaya, Kaito Kikuchi, Tomohisa Hayakawa et al.

Multi-agent consensus under jamming attacks is investigated. Specifically, inter-agent communications over a network are assumed to fail at certain times due to jamming of transmissions by a malicious attacker. A new stochastic communication protocol is proposed to achieve finite-time practical consensus between agents. In this protocol, communication attempt times of agents are randomized and unknown by the attacker until after the agents make their communication attempts. Through a probabilistic analysis, we show that the proposed communication protocol, when combined with a stochastic ternary control law, allows agents to achieve consensus regardless of the frequency of attacks. We demonstrate the efficacy of our results by considering two different strategies of the jamming attacker: a deterministic attack strategy and a more malicious communication-aware attack strategy.

Ahmet Cetinkaya, Hideaki Ishii, Tomohisa Hayakawa

Event-triggered networked control of a linear dynamical system is investigated. Specifically, the dynamical system and the controller are assumed to be connected through a communication channel. State and control input information packets between the system and the controller are attempted to be exchanged over the network only at time instants when certain triggering conditions are satisfied. We provide a probabilistic characterization for the link failures which allows us to model random packet losses due to unreliability in transmissions as well as those caused by malicious jamming attacks. We obtain conditions for the almost sure stability of the closed-loop system, and we illustrate the efficacy of our approach with a numerical example.

Kunihisa Okano, Hideaki Ishii

In this paper, we consider a stabilization problem of an uncertain system in a networked control setting. Due to the network, the measurements are quantized to finite-bit signals and may be randomly lost in the communication. We study uncertain autoregressive systems whose state and input parameters vary within given intervals. We derive conditions for making the plant output to be mean square stable, characterizing limitations on data rate, packet loss probabilities, and magnitudes of uncertainty. It is shown that a specific class of nonuniform quantizers can achieve stability with a lower data rate compared with the common uniform one.

Chiara Ravazzi, Paolo Frasca, Roberto Tempo et al.

This paper regards the relative localization problem in sensor networks. We study a randomized algorithm, which is based on input-driven consensus dynamics and involves pairwise "gossip" communications and updates. Due to the randomness of the updates, the state of this algorithm ergodically oscillates around a limit value. Exploiting the ergodicity of the dynamics, we show that the time-average of the state almost surely converges to the least-squares solution of the localization problem. Remarkably, the computation of the time-average does not require the sensors to share any common clock. Hence, the proposed algorithm is fully distributed and asynchronous.

Ahmet Cetinkaya, Hideaki Ishii, Tomohisa Hayakawa

Jamming attacks on wireless networked control systems are investigated for the scenarios where the system dynamics face exogenous disturbance. In particular, the control input packets are assumed to be transmitted from a controller to a remotely located linear plant over an insecure wireless communication channel that is subject to jamming attacks. The time-varying likelihood of transmission failures on this channel depends on the power of the jamming interference signal emitted by an attacker. We show that jamming attacks can prevent stability when the system faces disturbance, even if the attacked system without disturbance is stable. We also show that stability under jamming and disturbance can be achieved if the average jamming interference power is restricted in a certain way that we characterize in the paper. We illustrate our results on an example networked control system with a fading wireless channel, where the outage probability is affected by jamming attacks.

Kai Cai, Hideaki Ishii

We have recently proposed quantized gossip algorithms which solve the consensus and averaging problems on directed graphs with the least restrictive connectivity requirements. In this paper we study the convergence time of these algorithms. To this end, we investigate the shrinking time of the smallest interval that contains all states for the consensus algorithm, and the decay time of a suitable Lyapunov function for the averaging algorithm. The investigation leads us to characterizing the convergence time by the hitting time in certain special Markov chains. We simplify the structures of state transition by considering the special case of complete graphs, where every edge can be activated with an equal probability, and derive polynomial upper bounds on convergence time.

Kunihisa Okano, Hideaki Ishii

This paper considers data rate limitations for mean square stabilization of uncertain discrete-time linear systems via finite data rate and lossy channels. For a plant having parametric uncertainties, a necessary condition and a sufficient condition are derived, represented by the data rate, the packet loss probability, uncertainty bounds on plant parameters, and the unstable eigenvalues of the plant. The results extend those existing in the area of networked control, and in particular, the condition is exact for the scalar plant case.

Yuan Wang, Hideaki Ishii

We consider resilient versions of discrete-time multi-agent consensus in the presence of faulty or even malicious agents in the network. In particular, we develop event-triggered update rules which can mitigate the influence of the malicious agents and at the same time reduce the necessary communication. Each regular agent updates its state based on a given rule using its neighbors' information. Only when the triggering condition is satisfied, the regular agents send their current states to their neighbors. Otherwise, the neighbors will continue to use the state received the last time. Assuming that a bound on the number of malicious nodes is known, we propose two update rules with event-triggered communication. They follow the so-called mean subsequence reduced (MSR) type algorithms and ignore values received from potentially malicious neighbors. We provide full characterizations for the necessary connectivity in the network for the algorithms to perform correctly, which are stated in terms of the notion of graph robustness. A numerical example is provided to demonstrate the effectiveness of the proposed approach.

Iori Takaki, Ahmet Cetinkaya, Hideaki Ishii

This paper studies cyber attacks against informativity-based analysis in data-driven control. Focusing on strong observability, we consider an adversary who post-processes finite time-series data by an invertible linear transformation acting on the data matrices. We show that such transformations are capable of embedding malicious states into the invariant subspace explained by the transformed dataset. We provide a constructive attack method and derive feasibility conditions that characterize when such transformations exist. Moreover, we formulate an optimization problem to obtain the minimum-norm attack that quantifies the smallest data distortion required to destroy informativity. Numerical examples demonstrate that small and structured transformations can invalidate informativity certificates.

Tamer Başar, Tomohisa Hayakawa, Hideaki Ishii et al.

This tutorial presents cooperative and noncooperative game-theoretic frameworks for modeling, learning, and control in socio-technical systems, where human behavior, incentives, institutions, and social interactions are coupled with cyber-physical and networked infrastructures. The paper reviews strategic, dynamic, cooperative, matching, learning, and feedback-control approaches for analyzing how local decision-making, adaptation, and strategic interactions shape collective system outcomes. The tutorial further develops feedback-learning and incentive-design perspectives that connect equilibrium analysis with adaptation, distributed control, and mechanism design under information and coordination constraints. We also examine resilience and security challenges arising from adversarial behavior, misinformation, disruptions, and cascading failures in interconnected socio-technical networks. Finally, we discuss emerging research directions at the intersection of game theory, control, learning, and network science for resilient and adaptive socio-technical systems.

Song Fang, Karl Henrik Johansson, Mikael Skoglund et al.

In this paper, we introduce the concept of two-way coding, which originates in communication theory characterizing coding schemes for two-way channels, into control theory, particularly to facilitate the analysis and design of feedback control systems under injection attacks. Moreover, we propose the notion of attack decoupling, and show how the controller and the two-way coding can be co-designed to nullify the transfer function from attack to plant, rendering the attack effect zero both in transient phase and in steady state.

Xin Wang, Hideaki Ishii, Linkang Du et al.

With the proliferation of training data, distributed machine learning (DML) is becoming more competent for large-scale learning tasks. However, privacy concerns have to be given priority in DML, since training data may contain sensitive information of users. In this paper, we propose a privacy-preserving ADMM-based DML framework with two novel features: First, we remove the assumption commonly made in the literature that the users trust the server collecting their data. Second, the framework provides heterogeneous privacy for users depending on data's sensitive levels and servers' trust degrees. The challenging issue is to keep the accumulation of privacy losses over ADMM iterations minimal. In the proposed framework, a local randomization approach, which is differentially private, is adopted to provide users with self-controlled privacy guarantee for the most sensitive information. Further, the ADMM algorithm is perturbed through a combined noise-adding method, which simultaneously preserves privacy for users' less sensitive information and strengthens the privacy protection of the most sensitive information. We provide detailed analyses on the performance of the trained model according to its generalization error. Finally, we conduct extensive experiments using real-world datasets to validate the theoretical results and evaluate the classification performance of the proposed framework.

Song Fang, Mikael Skoglund, Karl Henrik Johansson et al.

In this paper, we obtain generic bounds on the variances of estimation and prediction errors in time series analysis via an information-theoretic approach. It is seen in general that the error bounds are determined by the conditional entropy of the data point to be estimated or predicted given the side information or past observations. Additionally, we discover that in order to achieve the prediction error bounds asymptotically, the necessary and sufficient condition is that the "innovation" is asymptotically white Gaussian. When restricted to Gaussian processes and 1-step prediction, our bounds are shown to reduce to the Kolmogorov-Szegö formula and Wiener-Masani formula known from linear prediction theory.

Song Fang, Hideaki Ishii, Jie Chen et al.

In this paper, we discover that the trace of the division of the optimal output estimation error covariance over the noise covariance attained by the Kalman-Bucy filter can be explicitly expressed in terms of the plant dynamics and noise statistics in a frequency-domain integral characterization. Towards this end, we examine the algebraic Riccati equation associated with Kalman-Bucy filtering using analytic function theory and relate it to the Bode integral. Our approach features an alternative, frequency-domain framework for analyzing algebraic Riccati equations and reduces to various existing related results.

Ahmet Cetinkaya, Hideaki Ishii, Tomohisa Hayakawa

The control problem of a linear discrete-time dynamical system over a multi-hop network is explored. The network is assumed to be subject to packet drops by malicious and nonmalicious nodes as well as random and malicious data corruption issues. We utilize asymptotic tail-probability bounds of transmission failure ratios to characterize the links and paths of a network as well as the network itself. This probabilistic characterization allows us to take into account multiple failures that depend on each other, and coordinated malicious attacks on the network. We obtain a sufficient condition for the stability of the networked control system by utilizing our probabilistic approach. We then demonstrate the efficacy of our results in different scenarios concerning transmission failures on a multi-hop network.

Wicak Ananduta, José María Maestre, Carlos Ocampo-Martinez et al.

In this paper, distributed energy management of interconnected microgrids, which is stated as a dynamic economic dispatch problem, is studied. Since the distributed approach requires cooperation of all local controllers, when some of them do not comply with the distributed algorithm that is applied to the system, the performance of the system might be compromised. Specifically, it is considered that adversarial agents (microgrids with their controllers) might implement control inputs that are different than the ones obtained from the distributed algorithm. By performing such behavior, these agents might have better performance at the expense of deteriorating the performance of the regular agents. This paper proposes a methodology to deal with this type of adversarial agents such that we can still guarantee that the regular agents can still obtain feasible, though suboptimal, control inputs in the presence of adversarial behaviors. The methodology consists of two steps: (i) the robustification of the underlying optimization problem and (ii) the identification of adversarial agents, which uses hypothesis testing with Bayesian inference and requires to solve a local mixed-integer optimization problem. Furthermore, the proposed methodology also prevents the regular agents to be affected by the adversaries once the adversarial agents are identified. In addition, we also provide a sub-optimality certificate of the proposed methodology.

Shuai Feng, Ahmet Cetinkaya, Hideaki Ishii et al.

We study communication-constrained networked control problems for linear time-invariant systems in the presence of Denial-of-Service (DoS) attacks, namely attacks that prevent transmissions over the communication network. Our work aims at exploring the relationship between system resilience and network bandwidth capacity. Given a class of DoS attacks, we first characterize time-invariant bit-rate bounds that are dependent on the unstable eigenvalues of the dynamic matrix of the plant and the parameters of DoS attacks, beyond which exponential stability of the closed-loop system can be guaranteed. Second, we design the time-varying bit-rate protocol and show that it can enable the system to maintain the comparable robustness as the one under the time-invariant bit-rate protocol and meanwhile promote the possibility of transmitting fewer bits especially when the attack levels are low. Our characterization clearly shows the trade-off between the communication bandwidth and resilience against DoS. An example is given to illustrate the proposed solution approach.

Masashi Wakaiki, Ahmet Cetinkaya, Hideaki Ishii

This paper addresses quantized output feedback stabilization under Denial-of-Service (DoS) attacks. First, assuming that the duration and frequency of DoS attacks are averagely bounded and that an initial bound of the plant state is known, we propose an output encoding scheme that achieves exponential convergence with finite data rates. Next we show that a suitable state transformation allows us to remove the assumption on the DoS frequency. Finally, we discuss the derivation of state bounds under DoS attacks and obtain sufficient conditions on the bounds of DoS duration and frequency for achieving Lyapunov stability of the closed-loop system.

Paolo Frasca, Chiara Ravazzi, Roberto Tempo et al.

In this paper we study a novel model of opinion dynamics in social networks, which has two main features. First, agents asynchronously interact in pairs, and these pairs are chosen according to a random process. We refer to this communication model as "gossiping". Second, agents are not completely open-minded, but instead take into account their initial opinions, which may be thought of as their "prejudices". In the literature, such agents are often called "stubborn". We show that the opinions of the agents fail to converge, but persistently undergo ergodic oscillations, which asymptotically concentrate around a mean distribution of opinions. This mean value is exactly the limit of the synchronous dynamics of the expected opinions.