Search

Decentralized optimization strategies are helpful for various applications, from networked estimation to distributed machine learning. This paper studies finite-sum minimization problems described over a network of nodes and proposes a computationally efficient algorithm that solves distributed convex problems and optimally finds the solution to locally non-convex objective functions. In contrast to batch gradient optimization in some literature, our algorithm is on a single-time scale with no extra inner consensus loop. It evaluates one gradient entry per node per time. Further, the algorithm addresses link-level nonlinearity representing, for example, logarithmic quantization of the exchanged data or clipping of the exchanged data bits. Leveraging perturbation-based theory and algebraic Laplacian network analysis proves optimal convergence and dynamics stability over time-varying and switching networks. The time-varying network setup might be due to packet drops or link failures. Despite the nonlinear nature of the dynamics, we prove exact convergence in the face of odd sign-preserving sector-bound nonlinear data transmission over the links. Illustrative numerical simulations further highlight our contributions., Comment: IEEE Transaction on Network Science and Engineering

Decentralized algorithms have gained substantial interest owing to advancements in cloud computing, Internet of Things (IoT), intelligent transportation networks, and parallel processing over sensor networks. The convergence of such algorithms is directly related to specific properties of the underlying network topology. Specifically, the clustering coefficient is known to affect, for example, the controllability/observability and the epidemic growth over networks. In this work, we study the effects of the clustering coefficient on the convergence rate of networked optimization approaches. In this regard, we model the structure of large-scale distributed systems by random scale-free (SF) and clustered scale-free (CSF) networks and compare the convergence rate by tuning the network clustering coefficient. This is done by keeping other relevant network properties (such as power-law degree distribution, number of links, and average degree) unchanged. Monte-Carlo-based simulations are used to compare the convergence rate over many trials of SF graph topologies. Furthermore, to study the convergence rate over real case studies, we compare the clustering coefficient of some real-world networks with the eigenspectrum of the underlying network (as a measure of convergence rate). The results interestingly show higher convergence rate over low-clustered networks. This is significant as one can improve the learning rate of many existing decentralized machine-learning scenarios by tuning the network clustering., Comment: SNAM Journal

Decentralized strategies are of interest for learning from large-scale data over networks. This paper studies learning over a network of geographically distributed nodes/agents subject to quantization. Each node possesses a private local cost function, collectively contributing to a global cost function, which the proposed methodology aims to minimize. In contrast to many existing literature, the information exchange among nodes is quantized. We adopt a first-order computationally-efficient distributed optimization algorithm (with no extra inner consensus loop) that leverages node-level gradient correction based on local data and network-level gradient aggregation only over nearby nodes. This method only requires balanced networks with no need for stochastic weight design. It can handle log-scale quantized data exchange over possibly time-varying and switching network setups. We analyze convergence over both structured networks (for example, training over data-centers) and ad-hoc multi-agent networks (for example, training over dynamic robotic networks). Through analysis and experimental validation, we show that (i) structured networks generally result in a smaller optimality gap, and (ii) logarithmic quantization leads to smaller optimality gap compared to uniform quantization.

Resource allocation and scheduling in multi-agent systems present challenges due to complex interactions and decentralization. This survey paper provides a comprehensive analysis of distributed algorithms for addressing the distributed resource allocation (DRA) problem over multi-agent systems. It covers a significant area of research at the intersection of optimization, multi-agent systems, and distributed consensus-based computing. The paper begins by presenting a mathematical formulation of the DRA problem, establishing a solid foundation for further exploration. Real-world applications of DRA in various domains are examined to underscore the importance of efficient resource allocation, and relevant distributed optimization formulations are presented. The survey then delves into existing solutions for DRA, encompassing linear, nonlinear, primal-based, and dual-formulation-based approaches. Furthermore, this paper evaluates the features and properties of DRA algorithms, addressing key aspects such as feasibility, convergence rate, and network reliability. The analysis of mathematical foundations, diverse applications, existing solutions, and algorithmic properties contributes to a broader comprehension of the challenges and potential solutions for this domain., Comment: Submitted to annual reviews in control

Distributed allocation finds applications in many scenarios including CPU scheduling, distributed energy resource management, and networked coverage control. In this paper, we propose a fast convergent optimization algorithm with a tunable rate using the signum function. The convergence rate of the proposed algorithm can be managed by changing two parameters. We prove convergence over uniformly-connected multi-agent networks. Therefore, the solution converges even if the network loses connectivity at some finite time intervals. The proposed algorithm is all-time feasible, implying that at any termination time of the algorithm, the resource-demand feasibility holds. This is in contrast to asymptotic feasibility in many dual formulation solutions (e.g., ADMM) that meet resource-demand feasibility over time and asymptotically., Comment: Conditionally accepted in IEEE SPL

We consider a discrete-time model of continuous-time distributed optimization over dynamic directed-graphs (digraphs) with applications to distributed learning. Our optimization algorithm works over general strongly connected dynamic networks under switching topologies, e.g., in mobile multi-agent systems and volatile networks due to link failures. Compared to many existing lines of work, there is no need for bi-stochastic weight designs on the links. The existing literature mostly needs the link weights to be stochastic using specific weight-design algorithms needed both at the initialization and at all times when the topology of the network changes. This paper eliminates the need for such algorithms and paves the way for distributed optimization over time-varying digraphs. We derive the bound on the gradient-tracking step-size and discrete time-step for convergence and prove dynamic stability using arguments from consensus algorithms, matrix perturbation theory, and Lyapunov theory. This work, particularly, is an improvement over existing stochastic-weight undirected networks in case of link removal or packet drops. This is because the existing literature may need to rerun time-consuming and computationally complex algorithms for stochastic design, while the proposed strategy works as long as the underlying network is weight-symmetric and balanced. The proposed optimization framework finds applications to distributed classification and learning.

This paper proposes two nonlinear dynamics to solve constrained distributed optimization problem for resource allocation over a multi-agent network. In this setup, coupling constraint refers to resource-demand balance which is preserved at all-times. The proposed solutions can address various model nonlinearities, for example, due to quantization and/or saturation. Further, it allows to reach faster convergence or to robustify the solution against impulsive noise or uncertainties. We prove convergence over weakly connected networks using convex analysis and Lyapunov theory. Our findings show that convergence can be reached for general sign-preserving odd nonlinearity. We further propose delay-tolerant mechanisms to handle general bounded heterogeneous time-varying delays over the communication network of agents while preserving all-time feasibility. This work finds application in CPU scheduling and coverage control among others. This paper advances the state-of-the-art by addressing (i) possible nonlinearity on the agents/links, meanwhile handling (ii) resource-demand feasibility at all times, (iii) uniform-connectivity instead of all-time connectivity, and (iv) possible heterogeneous and time-varying delays. To our best knowledge, no existing work addresses contributions (i)-(iv) altogether. Simulations and comparative analysis are provided to corroborate our contributions.

Understanding the impact of network clustering and small-world properties on epidemic spread can be crucial in developing effective strategies for managing and controlling infectious diseases. Particularly in this work, we study the impact of these network features on targeted intervention (e.g., self-isolation and quarantine). The targeted individuals for self-isolation are based on centrality measures and node influence metrics. Compared to our previous works on scale-free networks, small-world networks are considered in this paper. Small-world networks resemble real-world social and human networks. In this type of network, most nodes are not directly connected but can be reached through a few intermediaries (known as the small-worldness property). Real social networks, such as friendship networks, also exhibit this small-worldness property, where most people are connected through a relatively small number of intermediaries. We particularly study the epidemic curve flattening by centrality-based interventions/isolation over small-world networks. Our results show that high clustering while having low small-worldness (higher shortest path characteristics) implies flatter infection curves. In reality, a flatter infection curve implies that the number of new cases of a disease is spread out over a longer period of time, rather than a sharp and sudden increase in cases (a peak in epidemic). In turn, this reduces the strain on healthcare resources and helps to relieve the healthcare services.

In this work, we propose distributed and networked energy management scenarios to optimize the production and reservation of energy among a set of distributed energy nodes. In other words, the idea is to optimally allocate the generated and reserved powers based on nodes' local cost gradient information while meeting the demand energy. One main concern is the all-time (or anytime) resource-demand feasibility, implying that at all iterations of the scheduling algorithm, the balance between the produced power and demand plus reserved power must hold. The other concern is to design algorithms to tolerate communication time-delays and changes in the network. Further, one can incorporate possible model nonlinearity in the algorithm to address both inherent (e.g., saturation and quantization) and purposefully-added (e.g., signum-based) nonlinearities in the model. The proposed optimal allocation algorithm addresses all the above concerns, while it benefits from possible features of the distributed (or networked) solutions such as no-single-node-of-failure and distributed information processing. We show both the all-time feasibility of the proposed scheme and its convergence under certain bound on the step-rate using Lyapunov-type proofs., Comment: IEEE LCSS 2023

This paper considers distributed optimization algorithms, with application in binary classification via distributed support-vector-machines (D-SVM) over multi-agent networks subject to some link nonlinearities. The agents solve a consensus-constraint distributed optimization cooperatively via continuous-time dynamics, while the links are subject to strongly sign-preserving odd nonlinear conditions. Logarithmic quantization and clipping (saturation) are two examples of such nonlinearities. In contrast to existing literature that mostly considers ideal links and perfect information exchange over linear channels, we show how general sector-bounded models affect the convergence to the optimizer (i.e., the SVM classifier) over dynamic balanced directed networks. In general, any odd sector-bounded nonlinear mapping can be applied to our dynamics. The main challenge is to show that the proposed system dynamics always have one zero eigenvalue (associated with the consensus) and the other eigenvalues all have negative real parts. This is done by recalling arguments from matrix perturbation theory. Then, the solution is shown to converge to the agreement state under certain conditions. For example, the gradient tracking (GT) step size is tighter than the linear case by factors related to the upper/lower sector bounds. To the best of our knowledge, no existing work in distributed optimization and learning literature considers non-ideal link conditions.

Recent studies in network science and control have shown a meaningful relationship between the epidemic processes (e.g., COVID-19 spread) and some network properties. This paper studies how such network properties, namely clustering coefficient and centrality measures (or node influence metrics), affect the spread of viruses and the growth of epidemics over scale-free networks. The results can be used to target individuals (the nodes in the network) to \textit{flatten the infection curve}. This so-called flattening of the infection curve is to reduce the health service costs and burden to the authorities/governments. Our Monte-Carlo simulation results show that clustered networks are, in general, easier to flatten the infection curve, i.e., with the same connectivity and the same number of isolated individuals they result in more flattened curves. Moreover, distance-based centrality measures, which target the nodes based on their average network distance to other nodes (and not the node degrees), are better choices for targeting individuals for isolation/vaccination., Comment: Published in Social network analysis and mining

We propose a distributed (single) target tracking scheme based on networked estimation and consensus algorithms over static sensor networks. The tracking part is based on linear time-difference-of-arrival (TDOA) measurement proposed in our previous works. This paper, in particular, develops delay-tolerant distributed filtering solutions over sparse data-transmission networks. We assume general arbitrary heterogeneous delays at different links. This may occur in many realistic large-scale applications where the data-sharing between different nodes is subject to latency due to communication-resource constraints or large spatially distributed sensor networks. The solution we propose in this work shows improved performance (verified by both theory and simulations) in such scenarios. Another privilege of such distributed schemes is the possibility to add localized fault-detection and isolation (FDI) strategies along with survivable graph-theoretic design, which opens many follow-up venues to this research. To our best knowledge no such delay-tolerant distributed linear algorithm is given in the existing distributed tracking literature., Comment: ICRoM22

This paper considers distributed resource allocation and sum-preserving constrained optimization over lossy networks, where the links are unreliable and subject to packet drops. We define the conditions to ensure convergence under packet drops and link removal by focusing on two main properties of our allocation algorithm: (i) The weight-stochastic condition in typical consensus schemes is reduced to balanced weights, with no need for readjusting the weights to satisfy stochasticity. (ii) The algorithm does not require all-time connectivity but instead uniform connectivity over some non-overlapping finite time intervals. First, we prove that our algorithm provides primal-feasible allocation at every iteration step and converges under the conditions (i)-(ii) and some other mild conditions on the nonlinear iterative dynamics. These nonlinearities address possible practical constraints in real applications due to, for example, saturation or quantization among others. Then, using (i)-(ii) and the notion of bond-percolation theory, we relate the packet drop rate and the network percolation threshold to the (finite) number of iterations ensuring uniform connectivity and, thus, convergence towards the optimum value.

Latency is inherent in almost all real-world networked applications. In this paper, we propose a distributed allocation strategy over multi-agent networks with delayed communications. The state of each agent (or node) represents its share of assigned resources out of a fixed amount (equal to overall demand). Every node locally updates its state toward optimizing a global allocation cost function via received information of its neighbouring nodes even when the data exchange over the network is heterogeneously delayed at different links. The update is based on the alternating direction method of multipliers (ADMM) formulation subject to both sum-preserving coupling-constraint and local box-constraints. The solution is derivative-free and holds for general (not necessarily differentiable) convex cost models. We use the notion of augmented consensus over undirected networks to model delayed information exchange and for convergence analysis. We simulate our \textit{delay-tolerant} algorithm for, Comment: CDC22

This paper considers a network of collaborating agents for local resource allocation subject to nonlinear model constraints. In many applications, it is required (or desirable) that the solution be anytime feasible in terms of satisfying the sum-preserving global constraint. Motivated by this, sufficient conditions on the nonlinear mapping for anytime feasibility (or non-asymptotic feasibility) are addressed in this paper. For the two proposed distributed solutions, one converges over directed weight-balanced networks and the other one over undirected networks. In particular, we elaborate on uniform quantization and discuss the notion of {\epsilon}-accurate solution, which gives an estimate of how close we can get to the exact optimizer subject to different quantization levels. This work, further, handles general (possibly non-quadratic) strictly convex objective functions with application to CPU allocation among a cloud of data centers via distributed solutions. The results can be used as a coordination mechanism to optimally balance the tasks and CPU resources among a group of networked servers while addressing quantization or limited server capacity. Index Terms: multi-agent systems, sum-preserving resource allocation, distributed optimization, anytime feasibility, Comment: CCTA2022

We propose a linear time-difference-of-arrival (TDOA) measurement model to improve \textit{distributed} estimation performance for localized target tracking. We design distributed filters over sparse (possibly large-scale) communication networks using consensus-based data-fusion techniques. The proposed distributed and localized tracking protocols considerably reduce the sensor network's required connectivity and communication rate. We, further, consider $\kappa$-redundant observability and fault-tolerant design in case of losing communication links or sensor nodes. We present the minimal conditions on the remaining sensor network (after link/node removal) such that the distributed observability is still preserved and, thus, the sensor network can track the (single) maneuvering target. The motivation is to reduce the communication load versus the processing load, as the computational units are, in general, less costly than the communication devices. We evaluate the tracking performance via simulations in MATLAB., Comment: VTC22

In this paper, we study stateless and stateful physics-based anomaly detection scenarios via distributed estimation over sensor networks. In the stateful case, the detector keeps track of the sensor residuals (i.e., the difference of estimated and true outputs) and reports an alarm if certain statistics of the recorded residuals deviate over a predefined threshold, e.g., \chi^2 (Chi-square) detector. Instead, only instantaneous deviation of the residuals raises the alarm in the stateless case without considering the history of the sensor outputs and estimation data. Given (approximate) false-alarm rate for both cases, we propose a probabilistic threshold design based on the noise statistics. We show by simulation that increasing the window length in the stateful case may not necessarily reduce the false-alarm rate. On the other hand, it adds unwanted delay to raise the alarm. The distributed aspect of the proposed detection algorithm enables local isolation of the faulty sensors with possible recovery solutions by adding redundant observationally-equivalent sensors. We, then, offer a mechanism to design Q-redundant distributed observers, robust to failure (or removal) of up to Q sensors over the network., Comment: ECC22

Motivated by recent development in networking and parallel data-processing, we consider a distributed and localized finite-sum (or fixed-sum) allocation technique to solve resource-constrained convex optimization problems over multi-agent networks (MANs). Such networks include (smart) agents representing an intelligent entity capable of communication, processing, and decision-making. In particular, we consider problems subject to practical nonlinear constraints on the dynamics of the agents in terms of their communications and actuation capabilities (referred to as the node dynamics), e.g., networks of mobile robots subject to actuator saturation and quantized communication. The considered distributed sum-preserving optimization solution further enables adding purposeful nonlinear constraints, for example, sign-based nonlinearities, to reach convergence in predefined-time or robust to impulsive noise and disturbances in faulty environments. Moreover, convergence can be achieved under minimal network connectivity requirements among the agents; thus, the solution is applicable over dynamic networks where the channels come and go due to the agent's mobility and limited range. This paper discusses how various nonlinearity constraints on the optimization problem (e.g., collaborative allocation of resources) can be addressed for different applications via a distributed setup (over a network)., Comment: IEEE VTC2022

This paper proposes a distributed attack detection and mitigation technique based on distributed estimation over a multi-agent network, where the agents take partial system measurements susceptible to (possible) biasing attacks. In particular, we assume that the system is not locally observable via the measurements in the direct neighborhood of any agent. First, for performance analysis in the attack-free case, we show that the proposed distributed estimation is unbiased with bounded mean-square deviation in steady-state. Then, we propose a residual-based strategy to locally detect possible attacks at agents. In contrast to the deterministic thresholds in the literature assuming an upper bound on the noise support, we define the thresholds on the residuals in a probabilistic sense. After detecting and isolating the attacked agent, a system-digraph-based mitigation strategy is proposed to replace the attacked measurement with a new observationally-equivalent one to recover potential observability loss. We adopt a graph-theoretic method to classify the agents based on their measurements, to distinguish between the agents recovering the system rank-deficiency and the ones recovering output-connectivity of the system digraph. The attack detection/mitigation strategy is specifically described for each type, which is of polynomial-order complexity for large-scale applications. Illustrative simulations support our theoretical results., Comment: Accepted TNSE

A general nonlinear $1$st-order consensus-based solution for distributed constrained convex optimization is proposed with network resource allocation applications. The solution is used to optimize continuously-differentiable strictly convex cost functions over weakly-connected undirected networks, while it is anytime feasible and models various nonlinearities to account for imperfections and constraints on the (physical model of) agents in terms of limited actuation capabilities, e.g., quantization and saturation. Due to such inherent nonlinearities, the existing linear solutions considering ideal agent models may not necessarily converge with guaranteed optimality and anytime feasibility. Some applications also impose specific nonlinearities, e.g., convergence in fixed/finite-time or sign-based robust disturbance-tolerant dynamics. Our proposed distributed protocol generalizes such nonlinear models. Putting convex set analysis together with nonsmooth Lyapunov analysis, we prove convergence, (i) regardless of the particular type of nonlinearity, and (ii) with weak network-connectivity requirements (uniform-connectivity).

Observability and estimation are closely tied to the system structure, which can be visualized as a system graph--a graph that captures the inter-dependencies within the state variables. For example, in social system graphs such inter-dependencies represent the social interactions of different individuals. It was recently shown that contractions, a key concept from graph theory, in the system graph are critical to system observability, as (at least) one state measurement in every contraction is necessary for observability. Thus, the size and number of contractions are critical in recovering for loss of observability. In this paper, the correlation between the average-size/number of contractions and the global clustering coefficient (GCC) of the system graph is studied. Our empirical results show that estimating systems with high GCC requires fewer measurements, and in case of measurement failure, there are fewer possible options to find substitute measurement that recovers the system's observability. This is significant as by tuning the GCC, we can improve the observability properties of large-scale engineered networks, such as social networks and smart grid.

This paper considers distributed estimation of linear systems when the state observations are corrupted with Gaussian noise of unbounded support and under possible random adversarial attacks. We consider sensors equipped with single time-scale estimators and local chi-square ($\chi^2$) detectors to simultaneously opserve the states, share information, fuse the noise/attack-corrupted data locally, and detect possible anomalies in their own observations. While this scheme is applicable to a wide variety of systems associated with full-rank (invertible) matrices, we discuss it within the context of distributed inference in social networks. The proposed technique outperforms existing results in the sense that: (i) we consider Gaussian noise with no simplifying upper-bound assumption on the support; (ii) all existing $\chi^2$-based techniques are centralized while our proposed technique is distributed, where the sensors \textit{locally} detect attacks, with no central coordinator, using specific probabilistic thresholds; and (iii) no local-observability assumption at a sensor is made, which makes our method feasible for large-scale social networks. Moreover, we consider a Linear Matrix Inequalities (LMI) approach to design block-diagonal gain (estimator) matrices under appropriate constraints for isolating the attacks.

In this paper, we consider the binary classification problem via distributed Support-Vector-Machines (SVM), where the idea is to train a network of agents, with limited share of data, to cooperatively learn the SVM classifier for the global database. Agents only share processed information regarding the classifier parameters and the gradient of the local loss functions instead of their raw data. In contrast to the existing work, we propose a continuous-time algorithm that incorporates network topology changes in discrete jumps. This hybrid nature allows us to remove chattering that arises because of the discretization of the underlying CT process. We show that the proposed algorithm converges to the SVM classifier over time-varying weight balanced directed graphs by using arguments from the matrix perturbation theory., Comment: submitted to CDC21

Classical distributed estimation scenarios typically assume timely and reliable exchanges of information over the sensor network. This paper, in contrast, considers single time-scale distributed estimation via a sensor network subject to transmission time-delays. The proposed discrete-time networked estimator consists of two steps: (i) consensus on (delayed) a-priori estimates, and (ii) measurement update. The sensors only share their a-priori estimates with their out-neighbors over (possibly) time-delayed transmission links. The delays are assumed to be fixed over time, heterogeneous, and known. We assume distributed observability instead of local observability, which significantly reduces the communication/sensing loads on sensors. Using the notions of augmented matrices and Kronecker product, the convergence of the proposed estimator over strongly-connected networks is proved for a specific upper-bound on the time-delay., Comment: submitted to LCSS

This paper proposes networked dynamics to solve resource allocation problems over time-varying multi-agent networks. The state of each agent represents the amount of used resources (or produced utilities) while the total amount of resources is fixed. The idea is to optimally allocate the resources among the group of agents by minimizing the overall cost function subject to fixed sum of resources. Each agents' information is restricted to its own state and cost function and those of its immediate in-neighbors. This is motivated by distributed applications such as mobile edge-computing, economic dispatch over smart grids, and multi-agent coverage control. This work provides a fast convergent solution (in comparison with linear dynamics) while considering relaxed network connectivity with quantized communication links. The proposed dynamics reaches optimal solution over switching (possibly disconnected) undirected networks as far as their union over some bounded non-overlapping time-intervals has a spanning-tree. We prove feasibility of the solution, uniqueness of the optimal state, and convergence to the optimal value under the proposed dynamics, where the analysis is applicable to similar 1st-order allocation dynamics with strongly sign-preserving nonlinearities, such as actuator saturation., Comment: ECC2022

In this paper, we study large-scale networks in terms of observability and controllability. In particular, we compare the number of unmatched nodes in two main types of Scale-Free (SF) networks: the Barab{\'a}si-Albert (BA) model and the Holme-Kim (HK) model. Comparing the two models based on theory and simulation, we discuss the possible relation between clustering coefficient and the number of unmatched nodes. In this direction, we propose a new algorithm to reduce the number of unmatched nodes via link addition. The results are significant as one can reduce the number of unmatched nodes and therefore number of embedded sensors/actuators in, for example, an IoT network. This may significantly reduce the cost of controlling devices or monitoring cost in large-scale systems.

This paper considers the problem of simultaneous sensor fault detection, isolation, and networked estimation of linear full-rank dynamical systems. The proposed networked estimation is a variant of single time-scale protocol and is based on (i) consensus on \textit{a-priori} estimates and (ii) measurement innovation. The necessary connectivity condition on the sensor network and stabilizing block-diagonal gain matrix is derived based on our previous works. Considering additive faults in the presence of system and measurement noise, the estimation error at sensors is derived and proper residuals are defined for fault detection. Unlike many works in the literature, no simplifying upper-bound condition on the noise is considered and we assume Gaussian system/measurement noise. A probabilistic threshold is then defined for fault detection based on the estimation error covariance norm. Finally, a graph-theoretic sensor replacement scenario is proposed to recover possible loss of networked observability due to removing the faulty sensor. We examine the proposed fault detection and isolation scheme on an illustrative academic example to verify the results and make a comparison study with related literature.

Finite-time stability of networked control systems under Denial of Service (DoS) attacks are investigated in this paper, where the communication between the plant and the controller is compromised at some time intervals. Toward this goal, first an event-triggered mechanism based on the variation rate of the Lyapunov function is proposed such that the closed-loop system remains finite-time stable (FTS) and at the same time, the amount data exchange in the network is reduced. Next, the vulnerability of the proposed event-triggered finite-time controller in the presence of DoS attacks are evaluated and sufficient conditions on the DoS duration and frequency are obtained to assure the finite-time stability of the closed-loop system in the presence of DoS attack where no assumption on the DoS attack in terms of following a certain probabilistic or a well-structured periodic model is considered. Finally, the efficiency of the proposed approach is demonstrated through a simulation study.

Observability is a fundamental concept in system inference and estimation. This paper is focused on structural observability analysis of Cartesian product networks. Cartesian product networks emerge in variety of applications including in parallel and distributed systems. We provide a structural approach to extend the structural observability of the constituent networks (referred as the factor networks) to that of the Cartesian product network. The structural approach is based on graph theory and is generic. We introduce certain structures which are tightly related to structural observability of networks, namely parent Strongly-Connected-Component (parent SCC), parent node, and contractions. The results show that for particular type of networks (e.g. the networks containing contractions) the structural observability of the factor network can be recovered via Cartesian product. In other words, if one of the factor networks is structurally rank-deficient, using the other factor network containing a spanning cycle family, then the Cartesian product of the two nwtworks is structurally full-rank. We define certain network structures for structural observability recovery. On the other hand, we derive the number of observer nodes--the node whose state is measured by an output-- in the Cartesian product network based on the number of observer nodes in the factor networks. An example illustrates the graph-theoretic analysis in the paper.

In this brief paper, a new consensus protocol based on the sign of innovations is proposed. Based on this protocol each agent only requires single-bit of information about its relative state to its neighboring agents. This is significant in real-time applications, since it requires less computation and/or communication load on agents. Using Lyapunov stability theorem the convergence is proved for networks having a spanning tree. Further, the convergence is shown to be in finite-time, which is significant as compared to most asymptotic protocols in the literature. Time-variant network topologies are also considered in this paper, and final consensus value is derived for undirected networks. Applications of the proposed consensus protocol in (i) 2D/3D rendezvous task, (ii) distributed estimation, (iii) distributed optimization, and (iv) formation control are considered and significance of applying this protocol is discussed. Numerical simulations are provided to compare the protocol with the existing protocols in the literature.

In this paper, we consider composite networks formed from the Kronecker product of smaller networks. We find the observability and controllability properties of the product network from those of its constituent smaller networks. The overall network is modeled as a Linear-Structure-Invariant (LSI) dynamical system where the underlying matrices have a fixed zero/non-zero structure but the non-zero elements are potentially time-varying. This approach allows to model the system parameters as free variables whose values may only be known within a certain tolerance. We particularly look for minimal sufficient conditions on the observability and controllability of the composite network, which have a direct application in distributed estimation and in the design of networked control systems. The methodology in this paper is based on the structured systems analysis and graph theory, and therefore, the results are generic, i.e., they apply to almost all non-zero choices of free parameters. We show the controllability/observability results for composite product networks resulting from full structural-rank systems and self-damped networks. We provide an illustrative example of estimation based on Kalman filtering over a composite network to verify our results., Comment: Accepted for publication in IEEE TSIPN

This paper considers the problem of minimal control inputs to affect the system states such that the resulting system is structurally controllable. This problem and the dual problem of minimal observability are claimed to have no polynomial-order exact solution and, therefore, are NP-hard. Here, adopting a graph-theoretic approach, this problem is solved for general nonlinear (and also structure-invariant) systems and a P-order solution is proposed. In this direction, the dynamical system is modeled as a directed graph, called \textit{system digraph}, and two types of graph components are introduced which are tightly related with structural controllability. Two types of nodes which are required to be affected (or driven) by an input, called \textit{driver nodes}, are defined, and minimal number of these driver nodes are obtained. Polynomial-order complexity of the given algorithms to solve the problem ensures applicability of the solution for analysis of large-scale dynamical systems. {The structural results in this paper are significant as compared to the existing literature which offer approximate and computationally less-efficient, e.g. Gramian-based, solutions for the problem, while this paper provides exact solution with lower computational complexity and applicable for controllability analysis of nonlinear systems., Comment: accepted at IEEE Systems Journal

In this paper, we consider the optimal design of networked estimators to minimize the communication/measurement cost under the networked observability constraint. This problem is known as the minimum-cost networked estimation problem, which is generally claimed to be NP-hard. The main contribution of this work is to provide a polynomial-order solution for this problem under the constraint that the underlying dynamical system is self-damped. Using structural analysis, we subdivide the main problem into two NP-hard subproblems known as (i) optimal sensor selection, and (ii) minimum-cost communication network. For self-damped dynamical systems, we provide a polynomial-order solution for subproblem (i). Further, we show that the subproblem (ii) is of polynomial-order complexity if the links in the communication network are bidirectional. We provide an illustrative example to explain the methodologies., Comment: accepted at IEEE transactions on network Science and Engineering

In this paper, we compare the number of unmatched nodes and the size of dilations in two main random network models, the Scale-Free and Clustered Scale-Free networks. The number of unmatched nodes determines the necessary number of control inputs and is known to be a measure for network controllability, while the size of dilation is a measure of controllability recovery in case of control input failure. Our results show that clustered version of Scale-Free networks require fewer control inputs for controllability. Further, the average size of dilations is smaller in clustered Scale-Free networks, implying that potentially fewer options for controllability recovery are available.

This paper models the cyber-social system as a cyber-network of agents monitoring states of individuals in a social network. The state of each individual is represented by a social node and the interactions among individuals are represented by a social link. In the cyber-network each node represents an agent and the links represent information sharing among agents. Agents make an observation of social states and perform distributed inference. In this direction, the contribution of this work is threefold: (i) A novel distributed inference protocol is proposed that makes no assumption on the rank of the underlying social system. This is significant as most protocols in the literature only work on full-rank systems. (ii) A novel agent classification is developed, where it is shown that connectivity requirement on the cyber-network differs for each type. This is particularly important in finding the minimal number of observations and minimal connectivity of the cyber-network as the next contribution. (iii) The cost-optimal design of cyber-network constraint with distributed observability is addressed. This problem is subdivided into sensing cost optimization and networking cost optimization where both are claimed to be NP-hard. We solve both problems for certain types of social networks and find polynomial-order solutions., Comment: 12 pages, 7 figures

In this letter we discuss cost optimization of sensor networks monitoring structurally full-rank systems under distributed observability constraint. Using structured systems theory, the problem is relaxed into two subproblems: (i) sensing cost optimization and (ii) networking cost optimization. Both problems are reformulated as combinatorial optimization problems. The sensing cost optimization is shown to have a polynomial order solution. The networking cost optimization is shown to be NP-hard in general, but has a polynomial order solution under specific conditions. A 2-approximation polynomial order relaxation is provided for general networking cost optimization, which is applicable in large-scale system monitoring.

Observability of complex systems/networks is the focus of this paper, which is shown to be closely related to the concept of contraction. Indeed, for observable network tracking it is necessary/sufficient to have one node in each contraction measured. Therefore, nodes in a contraction are equivalent to recover for loss of observability, implying that contraction size is a key factor for observability recovery. Here, using a polynomial order contraction detection algorithm, we analyze the distribution of contractions, studying its relation with key network properties. Our results show that contraction size is related to network clustering coefficient and degree heterogeneity. Particularly, in networks with power-law degree distribution, if the clustering coefficient is high there are less contractions with smaller size on average. The implication is that estimation/tracking of such systems requires less number of measurements, while their observational recovery is more restrictive in case of sensor failure. Further, in Small-World networks higher degree heterogeneity implies that there are more contractions with smaller size on average. Therefore, the estimation of representing system requires more measurements, and also the recovery of measurement failure is more limited. These results imply that one can tune the properties of synthetic networks to alleviate their estimation/observability recovery., Comment: IEEE Transactions on Network Science and Engineering

Single time-scale distributed estimation of dynamic systems via a network of sensors/estimators is addressed in this letter. In single time-scale distributed estimation, the two fusion steps, consensus and measurement exchange, are implemented only once, in contrast to, e.g., a large number of consensus iterations at every step of the system dynamics. We particularly discuss the problem of failure in the sensor/estimator network and how to recover for distributed estimation by adding new sensor measurements from equivalent states. We separately discuss the recovery for two types of sensors, namely \alpha and \beta sensors. We propose polynomial order algorithms to find equivalent state nodes in graph representation of system to recover for distributed observability. The polynomial order solution is particularly significant for large-scale systems., Comment: IEEE signal processing letters

Measurements and sensing implementations impose certain cost in sensor networks. The sensor selection cost optimization is the problem of minimizing the sensing cost of monitoring a physical (or cyber- physical) system. Consider a given set of sensors tracking states of a dynamical system for estimation purposes. For each sensor assume different costs to measure different (realizable) states. The idea is to assign sensors to measure states such that the global cost is minimized. The number and selection of sensor measurements need to ensure the observability to track the dynamic state of the system with bounded estimation error. The main question we address is how to select the state measurements to minimize the cost while satisfying the observability conditions. Relaxing the observability condition for structurally cyclic systems, the main contribution is to propose a graph theoretic approach to solve the problem in polynomial time. Note that, polynomial time algorithms are suitable for large-scale systems as their running time is upper-bounded by a polynomial expression in the size of input for the algorithm. We frame the problem as a linear sum assignment with solution complexity of O(m3).

This letter studies measurement partitioning and equivalence in state estimation based on graph-theoretic principles. We show that a set of critical measurements (required to ensure LTI state-space observability) can be further partitioned into two types:~$\alpha$ and~$\beta$. This partitioning is driven by different graphical (or algebraic) methods used to define the corresponding measurements. Subsequently, we describe observational equivalence, i.e. given an~$\alpha$ (or~$\beta$) measurement, say~$y_i$, what is the set of measurements equivalent to~$y_i$, such that only one measurement in this set is required to ensure observability? Since~$\alpha$ and~$\beta$ measurements are cast using different algebraic and graphical characteristics, their equivalence sets are also derived using different algebraic and graph-theoretic principles. We illustrate the related concepts on an appropriate system digraph.

We consider distributed inference in social networks where a phenomenon of interest evolves over a given social interaction graph, referred to as the \emph{social digraph}. For inference, we assume that a network of agents monitors certain nodes in the social digraph and no agent may be able to perform inference within its neighborhood; the agents must rely on inter-agent communication. The key contributions of this paper include: (i) a novel construction of the distributed estimator and distributed observability from the first principles; (ii) a graph-theoretic agent classification that establishes the importance and role of each agent towards inference; (iii) characterizing the necessary conditions, based on the classification in (ii), on the agent network to achieve distributed observability. Our results are based on structured systems theory and are applicable to any parameter choice of the underlying system matrix as long as the social digraph remains fixed. In other words, any social phenomena that evolves (linearly) over a structure-invariant social digraph may be considered--we refer to such systems as Liner Structure-Invariant (LSI). The aforementioned contributions, (i)--(iii), thus, only require the knowledge of the social digraph (topology) and are independent of the social phenomena. We show the applicability of the results to several real-wold social networks, i.e. social influence among monks, networks of political blogs and books, and a co-authorship graph., Comment: submitted for journal publication

In this paper, we consider networked estimation of linear, discrete-time dynamical systems monitored by a network of agents. In order to minimize the power requirement at the (possibly, battery-operated) agents, we require that the agents can exchange information with their neighbors only \emph{once per dynamical system time-step}; in contrast to consensus-based estimation where the agents exchange information until they reach a consensus. It can be verified that with this restriction on information exchange, measurement fusion alone results in an unbounded estimation error at every such agent that does not have an observable set of measurements in its neighborhood. To over come this challenge, state-estimate fusion has been proposed to recover the system observability. However, we show that adding state-estimate fusion may not recover observability when the system matrix is structured-rank ($S$-rank) deficient. In this context, we characterize the state-estimate fusion and measurement fusion under both full $S$-rank and $S$-rank deficient system matrices., Comment: submitted for IEEE journal publication