Search

Abstract When dealing with network systems, a fundamental challenge is to ensure their functioning even when some of the network nodes do not operate as intended due to faults or attacks. The objective of this paper is to address the problem of resilient consensus in a context where the nodes have their own clocks, possibly operating in an asynchronous way, and can make updates at arbitrary time instants. The results represent a first step towards the development of resilient event-triggered and self-triggered coordination protocols. [ABSTRACT FROM AUTHOR]

Online learning has become increasingly popular on handling massive data. The sequential nature of online learning, however, requires a centralized learner to store data and update parameters. In this paper, we consider online learning with distributed data sources. The autonomous learners update local parameters based on local data sources and periodically exchange information with a small subset of neighbors in a communication network. We derive the regret bound for strongly convex functions that generalizes the work by Ram et al. for convex functions. More importantly, we show that our algorithm has intrinsic privacy-preserving properties, and we prove the sufficient and necessary conditions for privacy preservation in the network. These conditions imply that for networks with greater-than-one connectivity, a malicious learner cannot reconstruct the subgradients (and sensitive raw data) of other learners, which makes our algorithm appealing in privacy-sensitive applications. [ABSTRACT FROM AUTHOR]

Abstract: We consider a network in which every node has a value that it wishes to disseminate to all other nodes, despite an attack by an adversary that can falsify messages on a number of the links. To achieve this objective, we study a class of linear iterative strategies in which, at each time-step, each node in the network broadcasts a value to its neighbors that is a linear combination of its previous value and the values received from its neighbors. We take the number of unreliable links to be bounded, in that the number of incoming unreliable links to any node plus the total number of other nodes with incoming unreliable links is no greater than some nonnegative integer . We show that the linear iterative strategy will be resilient to the unreliable links if and only if the vertex connectivity is at least . If this condition is satisfied, we show that almost any choice of weights in the linear combinations will suffice to provide resilience. We further show that each node can identify the exact set of unreliable links that directly enter that node, and can communicate this information to the other nodes via the linear strategy. [Copyright &y& Elsevier]

Abstract: We consider the problem of constructing partial state observers for discrete-time linear systems with unknown inputs. Specifically, for any given system, we develop a design procedure that characterizes the set of all linear functionals of the system state that can be reconstructed through a linear observer with a given delay. By treating the delay as a design parameter, we allow greater flexibility in estimating state functionals, and are able to obtain a procedure that directly produces the corresponding observer parameters. Our technique is also applicable to continuous-time systems by replacing delayed outputs with differentiated outputs. [Copyright &y& Elsevier]

This paper develops a framework for performing fault-tolerant convolution via error-correcting codes based on the Chinese Remainder Theorem (CRT) with non-coprime moduli. In contrast to convolution that is protected through CRT codes with coprime moduli, our scheme allows errors to be detected and located in a highly parallel manner, and has the advantage of being robust to faults that occur during the error handling stage. In addition, for certain important classes of errors, the codes developed in this paper require less redundancy than CRT codes constructed from coprime moduli. We demonstrate the applicability and advantages of our codes by comparing them to both CRT codes with coprime moduli and repetition codes. We focus on codes over polynomial rings, but our constructions apply naturally to integer codes; we discuss this extension and show that it generalizes the distance properties and error correction strategies associated with previously developed approaches for codes based on non-coprime integer moduli. [ABSTRACT FROM AUTHOR]

Abstract: Control systems that utilize switched linear controllers have proven to be useful (and, in some cases, essential) for accomplishing certain control objectives in particular classes of plants. These controllers are often digital in nature and, as such, are subject to internal hardware malfunctions (faults). In this paper, we present a systematic methodology for constructing embeddings to protect switched linear controllers against hardware faults that corrupt their internal state. Our methodology is based on replacing the original controller with a redundant (higher dimensional) controller that preserves the functionality of the original controller while enabling error detection and correction. More importantly, this methodology allows an external mechanism to detect and identify transient state-transition faults through non-concurrent (e.g. periodic) parity checks. The resulting error detection and correction procedures can then be performed periodically, thereby relaxing the reliability requirements and overhead associated with the checking mechanism. [Copyright &y& Elsevier]

Consider a linear time-invariant (LTI) dynamical system monitored by a network of sensors, modeled as nodes of an underlying directed communication graph. We study the problem of collaboratively estimating the state of the system when certain nodes are compromised by adversaries. Specifically, we consider a Byzantine adversary model, where a compromised node possesses complete knowledge of the system dynamics and the network, and can deviate arbitrarily from the rules of any prescribed algorithm. We first characterize certain fundamental limitations of any distributed state estimation algorithm in terms of the measurement and communication structure of the nodes. We then develop an attack-resilient, provably correct state estimation algorithm that admits a fully distributed implementation. To characterize feasible network topologies that guarantee success of our proposed technique, we introduce a notion of 'strong-robustness' that captures both measurement and communication redundancy. Finally, by drawing connections to bootstrap percolation theory, we argue that given an LTI system and an associated sensor network, the 'strong-robustness' property can be checked in polynomial time. [ABSTRACT FROM AUTHOR]

As the scale of distributed control systems over networks increases and interactions between different subsystems become more sophisticated, questions of the resilience of such networks to attacks and faults increase in importance. The need to adapt (and redefine) classical system and control-theoretic notions to answer such questions using the language of graphs has recently started to gain attention as a fertile and important area of research. This paper presents an overview of graph-theoretic methods for analyzing the resilience of distributed control systems. We survey distributed algorithms that have been proposed to solve a variety of problems in networked systems, and summarize their resilience against adversarial actions in the context of the structure of the underlying networks. We also discuss graph-theoretic methods to quantify the attack impact, and reinterpret some system-theoretic notions of robustness from a graph-theoretic standpoint to mitigate the impact of the attacks. We conclude by introducing some avenues for further research in this field. [ABSTRACT FROM AUTHOR]

Random interdependent networks consist of a group of subnetworks where each edge between two different subnetworks is formed independently with probability p . In this paper, we investigate certain spectral and structural properties of such networks, with corresponding implications for certain variants of consensus and diffusion dynamics on those networks. We start by providing a characterization of the isoperimetric constant in terms of the inter-network edge formation probability p . We then analyze the algebraic connectivity of such networks, and provide an asymptotically tight rate of growth of this quantity for a certain range of inter-network edge formation probabilities. Next, we give bounds on the smallest eigenvalue of the grounded Laplacian matrix (obtained by removing certain rows and columns of the Laplacian matrix) of random interdependent networks for the case where the removed rows and columns correspond to one of the subnetworks. Finally, we study a property known as r -robustness, which is a strong indicator of the ability of a network to tolerate structural perturbations and dynamical attacks. Our results yield new insights into the structure and robustness properties of random interdependent networks. [ABSTRACT FROM AUTHOR]

We consider the problem of selecting an optimal set of sensors to estimate the states of linear dynamical systems. Specifically, the goal is to choose (at design-time) a subset of sensors (satisfying certain budget constraints) from a given set in order to minimize the trace of the steady state a priori or a posteriori error covariance produced by a Kalman filter. We show that the a priori and a posteriori error covariance-based sensor selection problems are both NP-hard, even under the additional assumption that the system is stable. We then provide bounds on the worst-case performance of sensor selection algorithms based on the system dynamics, and show that greedy algorithms are optimal for a certain class of systems. However, as a negative result, we show that certain typical objective functions are not submodular or supermodular in general. While this makes it difficult to evaluate the performance of greedy algorithms for sensor selection (outside of certain special cases), we show via simulations that these greedy algorithms perform well in practice. [ABSTRACT FROM AUTHOR]

We study a common-pool resource game where the resource experiences failure with a probability that grows with the aggregate investment in the resource. To capture decision making under such uncertainty, we model each player's risk preference according to the value function from prospect theory. We show the existence and uniqueness of a pure Nash equilibrium when the players have heterogeneous risk preferences and under certain assumptions on the rate of return and failure probability of the resource. Greater competition, vis-a-vis the number of players, increases the failure probability at the Nash equilibrium; we quantify this effect by obtaining bounds on the ratio of the failure probability at the Nash equilibrium to the failure probability under investment by a single user. We further show that heterogeneity in attitudes towards loss aversion leads to higher failure probability of the resource at the equilibrium. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the computational complexity of reconstructing the state of a linear system from sensor measurements that have been corrupted by an adversary. The first result establishes that the problem is, in general, NP-hard. We then introduce the notion of eigenvalue observability and show that the state can be reconstructed in polynomial time when each eigenvalue is observable by at least 2 s + 1 sensors and at most s sensors are corrupted by an adversary. However, there is a gap between eigenvalue observability and the possibility of reconstructing the state despite attacks — this gap has been characterized in the literature by the notion of sparse observability. To better understand this, we show that when the A matrix of the linear system has unitary geometric multiplicity, the gap disappears, i.e., eigenvalue observability coincides with sparse observability, and there exists a polynomial time algorithm to reconstruct the state provided the state can be reconstructed. [ABSTRACT FROM AUTHOR]

Highlights: [•] Separate linearized models are derived for the fluid dynamics and the thermal dynamics. [•] The proposed control architecture is motivated by the clear structure in the derived models. [•] Local controllers are completely decentralized to be easily scalable with the number of evaporators. [•] Global controller regulates composite superheat to meet global performance objectives. [•] Proposed control architecture and design is demonstrated through a simulated case study. [ABSTRACT FROM AUTHOR]

We consider the problem of distributed inference where agents in a network observe a stream of private signals generated by an unknown state, and aim to uniquely identify this state from a finite set of hypotheses. We focus on scenarios where communication between agents is costly, and takes place over channels with finite bandwidth. To reduce the frequency of communication, we develop a novel event-triggered distributed learning rule that is based on the principle of diffusing low beliefs on each false hypothesis. Building on this principle, we design a trigger condition under which an agent broadcasts only those components of its belief vector that have adequate innovation, to only those neighbors that require such information. We prove that our rule guarantees convergence to the true state exponentially fast almost surely despite sparse communication, and that it has the potential to significantly reduce information flow from uninformative agents to informative agents. Next, to deal with finite-precision communication channels, we propose a distributed learning rule that leverages the idea of adaptive quantization. We show that by sequentially refining the range of the quantizers, every agent can learn the truth exponentially fast almost surely, while using just 1 bit to encode its belief on each hypothesis. For both our proposed algorithms, we rigorously characterize the trade-offs between communication-efficiency and the learning rate. [ABSTRACT FROM AUTHOR]

In this paper, we propose a state and unknown input observer for discrete-time linear systems with bounded unknown inputs and measurement disturbances. The design procedure is formulated using a set of linear matrix inequalities, and leverages delayed (or fixed-lag) estimates. The observer error states and/or user-defined performance outputs are guaranteed to operate at certain performance bounds. Furthermore, by employing sufficiently large delays, the observer is guaranteed to provide exact asymptotic state and input estimates for minimum-phase systems. We demonstrate, via numerical examples, that the proposed observer can be used for a wider class of systems than those satisfying matching conditions. [ABSTRACT FROM AUTHOR]

We consider a scenario where mobile agents are required to collect measurements from a geographically dispersed set of sensors and return them to a base. An agent faces a risk of destruction while traversing the environment to reach the sensors, and gets a reward for gathering a sensor measurement only if it successfully returns to base. We first consider the single agent scenario and characterize several properties of the optimal policy for the agent based on a quantity that we term the "reward-to-risk" ratio of the tasks. We provide the optimal policy when the risk of destruction is sufficiently high, and then extend our analysis to multiple (heterogeneous) agents, with potentially different costs and survival probabilities. In particular, when the risk of destruction is sufficiently high, we show that the multi-agent task allocation problem has a submodular structure, and accordingly provide a greedy algorithm that is guaranteed to return an allocation that is within a 1 2 factor of optimal. [ABSTRACT FROM AUTHOR]