Guodong Shi

Julien M. Hendrickx, Guodong Shi, Karl H. Johansson

We discuss the possibility of reaching consensus in finite time using only linear iterations, with the additional restrictions that the update matrices must be stochastic with positive diagonals and consistent with a given graph structure. We show that finite-time average consensus can always be achieved for connected undirected graphs. For directed graphs, we show some necessary conditions for finite-time consensus, including strong connectivity and the presence of a simple cycle of even length.

Xiaoqiang Ren, Junfeng Wu, Karl H. Johansson et al.

Jointly optimal transmission power control and remote estimation over an infinite horizon is studied. A sensor observes a dynamic process and sends its observations to a remote estimator over a wireless fading channel characterized by a time-homogeneous Markov chain. The successful transmission probability depends on both the channel gains and the transmission power used by the sensor. The transmission power control rule and the remote estimator should be jointly designed, aiming to minimize an infinite-horizon cost consisting of the power usage and the remote estimation error. A first question one may ask is: Does this joint optimization problem have a solution? We formulate the joint optimization problem as an average cost belief-state Markov decision process and answer the question by proving that there exists an optimal deterministic and stationary policy. We then show that when the monitored dynamic process is scalar, the optimal remote estimates depend only on the most recently received sensor observation, and the optimal transmission power is symmetric and monotonically increasing with respect to the innovation error.

Guodong Shi, Mikael Johansson, Karl Henrik Johansson

The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes are selected to interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.

Yang Liu, Christian Lageman, Brian D. O. Anderson et al.

We study the approach to obtaining least squares solutions to systems of linear algebraic equations over networks by using distributed algorithms. Each node has access to one of the linear equations and holds a dynamic state. The aim for the node states is to reach a consensus as a least squares solution of the linear equations by exchanging their states with neighbors over an underlying interaction graph. A continuous-time distributed least squares solver over networks is developed in the form of the famous Arrow-Hurwicz-Uzawa flow. A necessary and sufficient condition is established on the graph Laplacian for the continuous-time distributed algorithm to give the least squares solution in the limit, with an exponentially fast convergence rate. The feasibility of different fundamental graphs is discussed including path graph, star graph, etc. Moreover, a discrete-time distributed algorithm is developed by Euler's method, converging exponentially to the least squares solution at the node states with suitable step size and graph conditions. The exponential convergence rate for both the continuous-time and discrete-time algorithms under the established conditions is confirmed by numerical examples. Finally, we investigate the performance of the proposed flow under switching networks, and surprisingly, switching networks at high switching frequencies can lead to approximate least square solvers even if all graphs in the switching signal fail to do so in the absence of structure switching.

Yang Liu, Youcheng Lou, Brian D. O. Anderson et al.

This paper presents a first-order {distributed continuous-time algorithm} for computing the least-squares solution to a linear equation over networks. Given the uniqueness of the solution, with nonintegrable and diminishing step size, convergence results are provided for fixed graphs. The exact rate of convergence is also established for various types of step size choices falling into that category. For the case where non-unique solutions exist, convergence to one such solution is proved for constantly connected switching graphs with square integrable step size, and for uniformly jointly connected switching graphs under the boundedness assumption on system states. Validation of the results and illustration of the impact of step size on the convergence speed are made using a few numerical examples.

Youcheng Lou, Guodong Shi, Karl Henrik Johansson et al.

In this paper, we propose an approximate projected consensus algorithm for a network to cooperatively compute the intersection of convex sets. Instead of assuming the exact convex projection proposed in the literature, we allow each node to compute an approximate projection and communicate it to its neighbors. The communication graph is directed and time-varying. Nodes update their states by weighted averaging. Projection accuracy conditions are presented for the considered algorithm. They indicate how much projection accuracy is required to ensure global consensus to a point in the intersection set when the communication graph is uniformly jointly strongly connected. We show that $π/4$ is a critical angle error of the projection approximation to ensure a bounded state. A numerical example indicates that this approximate projected consensus algorithm may achieve better performance than the exact projected consensus algorithm in some cases.

Junfeng Wu, Guodong Shi, Brian D. O. Anderson et al.

In this paper, we investigate probabilistic stability of Kalman filtering over fading channels modeled by $\ast$-mixing random processes, where channel fading is allowed to generate non-stationary packet dropouts with temporal and/or spatial correlations. Upper/lower almost sure (a.s.) stabilities and absolutely upper/lower a.s. stabilities are defined for characterizing the sample-path behaviors of the Kalman filtering. We prove that both upper and lower a.s. stabilities follow a zero-one law, i.e., these stabilities must happen with a probability either zero or one, and when the filtering system is one-step observable, the absolutely upper and lower a.s. stabilities can also be interpreted using a zero-one law. We establish general stability conditions for (absolutely) upper and lower a.s. stabilities. In particular, with one-step observability, we show the equivalence between absolutely a.s. stabilities and a.s. ones, and necessary and sufficient conditions in terms of packet arrival rate are derived; for the so-called non-degenerate systems, we also manage to give a necessary and sufficient condition for upper a.s. stability.

Guodong Shi, Alexandre Proutiere, Karl Henrik Johansson

This paper explores the fundamental properties of distributed minimization of a sum of functions with each function only known to one node, and a pre-specified level of node knowledge and computational capacity. We define the optimization information each node receives from its objective function, the neighboring information each node receives from its neighbors, and the computational capacity each node can take advantage of in controlling its state. It is proven that there exist a neighboring information way and a control law that guarantee global optimal consensus if and only if the solution sets of the local objective functions admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a control law that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for successful distributed optimization for a large class of algorithms.

Hongsheng Qi, Biqiang Mu, Ian R. Petersen et al.

In this paper, we study dynamical quantum networks which evolve according to Schrödinger equations but subject to sequential local or global quantum measurements. A network of qubits forms a composite quantum system whose state undergoes unitary evolution in between periodic measurements, leading to hybrid quantum dynamics with random jumps at discrete time instances along a continuous orbit. The measurements either act on the entire network of qubits, or only a subset of qubits. First of all, we reveal that this type of hybrid quantum dynamics induces probabilistic Boolean recursions representing the measurement outcomes. With global measurements, it is shown that such resulting Boolean recursions define Markov chains whose state-transitions are fully determined by the network Hamiltonian and the measurement observables. Particularly, we establish an explicit and algebraic representation of the underlying recursive random mapping driving such induced Markov chains. Next, with local measurements, the resulting probabilistic Boolean dynamics is shown to be no longer Markovian. The state transition probability at any given time becomes dependent on the entire history of the sample path, for which we establish a recursive way of computing such non-Markovian probability transitions. Finally, we adopt the classical bilinear control model for the continuous Schrödinger evolution, and show how the measurements affect the controllability of the quantum networks.

Angela Fontan, Guodong Shi, Xiaoming Hu et al.

The constrained consensus problem considered in this paper, denoted interval consensus, is characterized by the fact that each agent can impose a lower and upper bound on the achievable consensus value. Such constraints can be encoded in the consensus dynamics by saturating the values that an agent transmits to its neighboring nodes. We show in the paper that when the intersection of the intervals imposed by the agents is nonempty, the resulting constrained consensus problem must converge to a common value inside that intersection. In our algorithm, convergence happens in a fully distributed manner, and without need of sharing any information on the individual constraining intervals. When the intersection of the intervals is an empty set, the intrinsic nonlinearity of the network dynamics raises new challenges in understanding the node state evolution. Using Brouwer fixed-point theorem we prove that in that case there exists at least one equilibrium, and in fact the possible equilibria are locally stable if the constraints are satisfied or dissatisfied at the same time among all nodes. For graphs with sufficient sparsity it is further proven that there is a unique equilibrium that is globally attractive if the constraint intervals are pairwise disjoint.

Youcheng Lou, Yiguang Hong, Lihua Xie et al.

In this paper, we investigate a distributed Nash equilibrium computation problem for a time-varying multi-agent network consisting of two subnetworks, where the two subnetworks share the same objective function. We first propose a subgradient-based distributed algorithm with heterogeneous stepsizes to compute a Nash equilibrium of a zero-sum game. We then prove that the proposed algorithm can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs with homogenous stepsizes. Moreover, we demonstrate that for weighted-unbalanced graphs a Nash equilibrium may not be achieved with homogenous stepsizes unless certain conditions on the objective function hold. We show that there always exist heterogeneous stepsizes for the proposed algorithm to guarantee that a Nash equilibrium can be achieved for UJSC digraphs. Finally, in two standard weight-unbalanced cases, we verify the convergence to a Nash equilibrium by adaptively updating the stepsizes along with the arc weights in the proposed algorithm.

Guangyang Zeng, Shiyu Chen, Biqiang Mu et al.

The Perspective-n-Point (PnP) problem has been widely studied in both computer vision and photogrammetry societies. With the development of feature extraction techniques, a large number of feature points might be available in a single shot. It is promising to devise a consistent estimator, i.e., the estimate can converge to the true camera pose as the number of points increases. To this end, we propose a consistent PnP solver, named \emph{CPnP}, with bias elimination. Specifically, linear equations are constructed from the original projection model via measurement model modification and variable elimination, based on which a closed-form least-squares solution is obtained. We then analyze and subtract the asymptotic bias of this solution, resulting in a consistent estimate. Additionally, Gauss-Newton (GN) iterations are executed to refine the consistent solution. Our proposed estimator is efficient in terms of computations -- it has $O(n)$ computational complexity. Experimental tests on both synthetic data and real images show that our proposed estimator is superior to some well-known ones for images with dense visual features, in terms of estimation precision and computing time.

Yang Liu, Junfeng Wu, Ian R. Manchester et al.

A distributed computing protocol consists of three components: (i) Data Localization: a network-wide dataset is decomposed into local datasets separately preserved at a network of nodes; (ii) Node Communication: the nodes hold individual dynamical states and communicate with the neighbors about these dynamical states; (iii) Local Computation: state recursions are computed at each individual node. Information about the local datasets enters the computation process through the node-to-node communication and the local computations, which may be leaked to dynamics eavesdroppers having access to global or local node states. In this paper, we systematically investigate this potential computational privacy risks in distributed computing protocols in the form of structured system identification, and then propose and thoroughly analyze a Privacy-Preserving-Summation-Consistent (PPSC) mechanism as a generic privacy encryption subroutine for consensus-based distributed computations. The central idea is that the consensus manifold is where we can both hide node privacy and achieve computational accuracy. In this first part of the paper, we demonstrate the computational privacy risks in distributed algorithms against dynamics eavesdroppers and particularly in distributed linear equation solvers, and then propose the PPSC mechanism and illustrate its usefulness.

Yang Liu, Junfeng Wu, Ian Manchester et al.

In the first part of the paper, we have studied the computational privacy risks in distributed computing protocols against local or global dynamics eavesdroppers, and proposed a Privacy-Preserving-Summation-Consistent (PPSC) mechanism as a generic privacy encryption subroutine for consensus-based distributed computations. In this part of this paper, we show that the conventional deterministic and random gossip algorithms can be used to realize the PPSC mechanism over a given network. At each time step, a node is selected to interact with one of its neighbors via deterministic or random gossiping. Such node generates a random number as its new state, and sends the subtraction between its current state and that random number to the neighbor; then the neighbor updates its state by adding the received value to its current state. We establish concrete privacy-preservation conditions by proving the impossibility for the reconstruction of the network input from the output of the gossip-based PPSC mechanism against eavesdroppers with full network knowledge, and by showing that the PPSC mechanism can achieve differential privacy at arbitrary privacy levels. The convergence is characterized explicitly and analytically for both deterministic and randomized gossiping, which is essentially achieved in a finite number of steps. Additionally, we illustrate that the proposed algorithms can be easily made adaptive in real-world applications by making realtime trade-offs between resilience against node dropout or communication failure and privacy preservation capabilities.

Bo Li, Guodong Shi

In this paper, we investigate the fundamental limitations of feedback mechanism in dealing with uncertainties for network systems. The study of maximum capability of feedback control was pioneered in Xie and Guo (2000) for scalar systems with nonparametric nonlinear uncertainty. In a network setting, nodes with unknown and nonlinear dynamics are interconnected through a directed interaction graph. Nodes can design feedback controls based on all available information, where the objective is to stabilize the network state. Using information structure and decision pattern as criteria, we specify three categories of network feedback laws, namely the global-knowledge/global-decision, network-flow/local-decision, and local-flow/local-decision feedback. We establish a series of network capacity characterizations for these three fundamental types of network control laws. First of all, we prove that for global-knowledge/global-decision and network-flow/local-decision control where nodes know the information flow across the entire network, there exists a critical number $\big(3/2+\sqrt{2}\big)/\|A_{\mathrm{G}}\|_\infty$, where $3/2+\sqrt{2}$ is as known as the Xie-Guo constant and $A_{\mathrm{G}}$ is the network adjacency matrix, defining exactly how much uncertainty in the node dynamics can be overcome by feedback. Interestingly enough, the same feedback capacity can be achieved under max-consensus enhanced local flows where nodes only observe information flows from neighbors as well as extreme (max and min) states in the network. Next, for local-flow/local-decision control, we prove that there exists a structure-determined value being a lower bound of the network feedback capacity. These results reveal the important connection between network structure and fundamental capabilities of in-network feedback control.

Fletcher Fan, Bowen Yi, David Rye et al.

In this paper, we present a new data-driven method for learning stable models of nonlinear systems. Our model lifts the original state space to a higher-dimensional linear manifold using Koopman embeddings. Interestingly, we prove that every discrete-time nonlinear contracting model can be learnt in our framework. Another significant merit of the proposed approach is that it allows for unconstrained optimization over the Koopman embedding and operator jointly while enforcing stability of the model, via a direct parameterization of stable linear systems, greatly simplifying the computations involved. We validate our method on a simulated system and analyze the advantages of our parameterization compared to alternatives.

Dafa Ren, Xiaoqiang Ren, Xiaofan Wang et al.

Grasping objects in cluttered scenarios is a challenging task in robotics. Performing pre-grasp actions such as pushing and shifting to scatter objects is a way to reduce clutter. Based on deep reinforcement learning, we propose a Fast-Learning Grasping (FLG) framework, that can integrate pre-grasping actions along with grasping to pick up objects from cluttered scenarios with reduced real-world training time. We associate rewards for performing moving actions with the change of environmental clutter and utilize a hybrid triggering method, leading to data-efficient learning and synergy. Then we use the output of an extended fully convolutional network as the value function of each pixel point of the workspace and establish an accurate estimation of the grasp probability for each action. We also introduce a mask function as prior knowledge to enable the agents to focus on the accurate pose adjustment to improve the effectiveness of collecting training data and, hence, to learn efficiently. We carry out pre-training of the FLG over simulated environment, and then the learnt model is transferred to the real world with minimal fine-tuning for further learning during actions. Experimental results demonstrate a 94% grasp success rate and the ability to generalize to novel objects. Compared to state-of-the-art approaches in the literature, the proposed FLG framework can achieve similar or higher grasp success rate with lesser amount of training in the real world. Supplementary video is available at https://youtu.be/e04uDLsxfDg.

Bowen Yi, Chi Jin, Lei Wang et al.

In this paper we propose a novel observer to solve the problem of visual simultaneous localization and mapping (SLAM), only using the information from a single monocular camera and an inertial measurement unit (IMU). The system state evolves on the manifold $SE(3)\times \mathbb{R}^{3n}$, on which we design dynamic extensions carefully in order to generate an invariant foliation, such that the problem is reformulated into online \emph{constant parameter} identification. Then, following the recently introduced parameter estimation-based observer (PEBO) and the dynamic regressor extension and mixing (DREM) procedure, we provide a new simple solution. A notable merit is that the proposed observer guarantees almost global asymptotic stability requiring neither persistency of excitation nor uniform complete observability, which, however, are widely adopted in most existing works with guaranteed stability.

Deming Yuan, Alexandre Proutiere, Guodong Shi

We consider distributed online convex optimization problems, where the distributed system consists of various computing units connected through a time-varying communication graph. In each time step, each computing unit selects a constrained vector, experiences a loss equal to an arbitrary convex function evaluated at this vector, and may communicate to its neighbors in the graph. The objective is to minimize the system-wide loss accumulated over time. We propose a decentralized algorithm with regret and cumulative constraint violation in $\mathcal{O}(T^{\max\{c,1-c\} })$ and $\mathcal{O}(T^{1-c/2})$, respectively, for any $c\in (0,1)$, where $T$ is the time horizon. When the loss functions are strongly convex, we establish improved regret and constraint violation upper bounds in $\mathcal{O}(\log(T))$ and $\mathcal{O}(\sqrt{T\log(T)})$. These regret scalings match those obtained by state-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problem (for both convex and strongly convex loss functions). In the case of bandit feedback, the proposed algorithms achieve a regret and constraint violation in $\mathcal{O}(T^{\max\{c,1-c/3 \} })$ and $\mathcal{O}(T^{1-c/2})$ for any $c\in (0,1)$. We numerically illustrate the performance of our algorithms for the particular case of distributed online regularized linear regression problems.

Deming Yuan, Alexandre Proutiere, Guodong Shi

We study online linear regression problems in a distributed setting, where the data is spread over a network. In each round, each network node proposes a linear predictor, with the objective of fitting the \emph{network-wide} data. It then updates its predictor for the next round according to the received local feedback and information received from neighboring nodes. The predictions made at a given node are assessed through the notion of regret, defined as the difference between their cumulative network-wide square errors and those of the best off-line network-wide linear predictor. Various scenarios are investigated, depending on the nature of the local feedback (full information or bandit feedback), on the set of available predictors (the decision set), and the way data is generated (by an oblivious or adaptive adversary). We propose simple and natural distributed regression algorithms, involving, at each node and in each round, a local gradient descent step and a communication and averaging step where nodes aim at aligning their predictors to those of their neighbors. We establish regret upper bounds typically in ${\cal O}(T^{3/4})$ when the decision set is unbounded and in ${\cal O}(\sqrt{T})$ in case of bounded decision set.

Yang Liu, Bo Li, Brian Anderson et al.

This paper proposes and investigates a framework for clique gossip protocols. As complete subnetworks, the existence of cliques is ubiquitous in various social, computer, and engineering networks. By clique gossiping, nodes interact with each other along a sequence of cliques. Clique-gossip protocols are defined as arbitrary linear node interactions where node states are vectors evolving as linear dynamical systems. Such protocols become clique-gossip averaging algorithms when node states are scalars under averaging rules. We generalize the classical notion of line graph to capture the essential node interaction structure induced by both the underlying network and the specific clique sequence. We prove a fundamental eigenvalue invariance principle for periodic clique-gossip protocols, which implies that any permutation of the clique sequence leads to the same spectrum for the overall state transition when the generalized line graph contains no cycle. We also prove that for a network with $n$ nodes, cliques with smaller sizes determined by factors of $n$ can always be constructed leading to finite-time convergent clique-gossip averaging algorithms, provided $n$ is not a prime number. Particularly, such finite-time convergence can be achieved with cliques of equal size $m$ if and only if $n$ is divisible by $m$ and they have exactly the same prime factors. A proven fastest finite-time convergent clique-gossip algorithm is constructed for clique-gossiping using size-$m$ cliques. Additionally, the acceleration effects of clique-gossiping are illustrated via numerical examples.

Weiguo Xia, Guodong Shi, Ziyang Meng et al.

This paper studies deterministic consensus networks with discrete-time dynamics under persistent flows and non-reciprocal agent interactions. An arc describing the interaction strength between two agents is said to be persistent if its weight function has an infinite $l_1$ norm. We discuss two balance conditions on the interactions between agents which generalize the arc-balance and cut-balance conditions in the literature respectively. The proposed conditions require that such a balance should be satisfied over each time window of a fixed length instead of at each time instant. We prove that in both cases global consensus is reached if and only if the persistent graph, which consists of all the persistent arcs, contains a directed spanning tree. The convergence rates of the system to consensus are also provided in terms of the interactions between agents having taken place. The results are obtained under a weak condition without assuming the existence of a positive lower bound of all the nonzero weights of arcs and are compared with the existing results. Illustrative examples are provided to show the critical importance of the nontrivial lower boundedness of the self-confidence of the agents.

Guodong Shi, Brian D. O. Anderson, U. Helmke

We study distributed network flows as solvers in continuous time for the linear algebraic equation $\mathbf{z}=\mathbf{H}\mathbf{y}$. Each node $i$ has access to a row $\mathbf{h}_i^{\rm T}$ of the matrix $\mathbf{H}$ and the corresponding entry $z_i$ in the vector $\mathbf{z}$. The first "consensus + projection" flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the $\mathbf{h}_i$ and $z_i$. The second "projection consensus" flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs as well as without positively lower bounded assumption on arc weights, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the "consensus + projection" flow while local for the "projection consensus" flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the "consensus + projection" flow under fixed bidirectional graphs. Semi-global convergence to approximate least squares solutions is demonstrated for general switching directed graphs under suitable conditions. It is also shown that the "projection consensus" flow drives the average of the node states to the least squares solution with complete graph. Numerical examples are provided as illustrations of the established results.

Brian D. O. Anderson, Guodong Shi, Jochen Trumpf

We study continuous-time consensus dynamics for multi-agent systems with undirected switching interaction graphs. We establish a necessary and sufficient condition for exponential asymptotic consensus based on the classical theory of complete observability. The proof is remarkably simple compared to similar results in the literature and the conditions for consensus are mild. This observability-based method can also be applied to the case where negatively weighted edges are present. Additionally, as a by-product of the observability based arguments, we show that the nodes' initial value can be recovered from the signals on the edges up to a shift of the network average.

Guodong Shi, Alexandre Proutiere, Karl Henrik Johansson

In this paper, we establish a few new synchronization conditions for complex networks with nonlinear and nonidentical self-dynamics with switching directed communication graphs. In light of the recent works on distributed sub-gradient methods, we impose integral convexity for the nonlinear node self-dynamics in the sense that the self-dynamics of a given node is the gradient of some concave function corresponding to that node. The node couplings are assumed to be linear but with switching directed communication graphs. Several sufficient and/or necessary conditions are established for exact or approximate synchronization over the considered complex networks. These results show when and how nonlinear node self-dynamics may cooperate with the linear diffusive coupling, which eventually leads to network synchronization conditions under relaxed connectivity requirements.

Tao Yang, Ziyang Meng, Guodong Shi et al.

This paper considers the synchronization problem for networks of coupled nonlinear dynamical systems under switching communication topologies. Two types of nonlinear agent dynamics are considered. The first one is non-expansive dynamics (stable dynamics with a convex Lyapunov function $φ(\cdot)$) and the second one is dynamics that satisfies a global Lipschitz condition. For the non-expansive case, we show that various forms of joint connectivity for communication graphs are sufficient for networks to achieve global asymptotic $φ$-synchronization. We also show that $φ$-synchronization leads to state synchronization provided that certain additional conditions are satisfied. For the globally Lipschitz case, unlike the non-expansive case, joint connectivity alone is not sufficient for achieving synchronization. A sufficient condition for reaching global exponential synchronization is established in terms of the relationship between the global Lipschitz constant and the network parameters. We also extend the results to leader-follower networks.

Shuangshuang Fu, Guodong Shi, Ian R. Petersen et al.

In this paper, we investigate the evolution of the network entropy for consensus dynamics in classical or quantum networks. We show that in the classical case, the network entropy decreases at the consensus limit if the node initial values are i.i.d. Bernoulli random variables, and the network differential entropy is monotonically non-increasing if the node initial values are i.i.d. Gaussian. While for quantum consensus dynamics, the network's von Neumann entropy is in contrast non-decreasing. In light of this inconsistency, we compare several gossiping algorithms with random or deterministic coefficients for classical or quantum networks, and show that quantum gossiping algorithms with deterministic coefficients are physically related to classical gossiping algorithms with random coefficients.

Junfeng Wu, Guodong Shi, Brian D. O. Anderson et al.

This paper investigates the stability of Kalman filtering over Gilbert-Elliott channels where random packet drop follows a time-homogeneous two-state Markov chain whose state transition is determined by a pair of failure and recovery rates. First of all, we establish a relaxed condition guaranteeing peak-covariance stability described by an inequality in terms of the spectral radius of the system matrix and transition probabilities of the Markov chain. We further show that that condition can be interpreted using a linear matrix inequality feasibility problem. Next, we prove that the peak-covariance stability implies mean-square stability, if the system matrix has no defective eigenvalues on the unit circle. This connection between the two stability notions holds for any random packet drop process. We prove that there exists a critical curve in the failure-recovery rate plane, below which the Kalman filter is mean-square stable and no longer mean-square stable above, via a coupling method in stochastic processes. Finally, a lower bound for this critical failure rate is obtained making use of the relationship we establish between the two stability criteria, based on an approximate relaxation of the system matrix.