We establish a thorough treatment of reduced-state synchronization for qubit networks with the aim of driving the qubits’ reduced states to a common trajectory. The evolution of the quantum network’s state is described by a master equation, where the network Hamiltonian is either a direct sum or a tensor product of identical qubit Hamiltonians, and the coupling terms are given by a set of permutation operators over the network. The permutations introduce naturally quantum directed interactions. We show that reduced-state synchronization is achieved if and only if the quantum interaction graphs corresponding to the permutation operators form a strongly connected union graph. The proof is based on an algebraic analysis making use of the Perron-Frobenius theorem for non-negative matrices. The convergence rate and the limiting orbit are explicitly characterized. Numerical examples are provided illustrating the obtained results. Further, we investigate the missing symmetry in the reduced-state synchronization from a graphical point of view. The information-flow hierarchy in quantum permutation operators is characterized by different layers of information-induced graphs. We show that the quantum synchronization equation is by nature equivalent to several parallel cut-balanced consensus processes, and a necessary and sufficient condition is obtained for quantum reduced-state synchronization under switching interactions applying recent work of Hendrickx and Tsitsiklis.
Consensus and synchronization of node states in a network of coupled dynamics have been extensively studied in the past decades @cite_24 @cite_36 @cite_31 . The basic idea is that @cite_23 nodes in a network with suitable connectivity can reach a common state or trajectory where all nodes' initial values are encoded with distributed node interactions, and the strong involvement of graph-theoretic approaches has reshaped the study of networked control systems @cite_16 . Excellent results have been derived towards the understandings of how bidirectional or directed, fixed or switching, deterministic or random, node interactions influence the consensus value and the speed of consensus, e.g., @cite_28 @cite_30 @cite_0 @cite_32 .
@cite_30 @cite_36 @cite_28 @cite_32 @cite_24 @cite_0 @cite_23 @cite_31 @cite_16
1949110650 2135254481 2114482313 2142465565 2160643434 2158401151 1978708265 2058750992 1838286088
We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to o([EQUATION]) nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2. We study several variants of coordinated consensus in dynamic networks. We assume a synchronous model, where the communication graph for each round is chosen by a worst-case adversary. The network topology is always connected, but can change completely from one round to the next. The model captures mobile and wireless networks, where communication can be unpredictable. In this setting we study the fundamental problems of eventual, simultaneous, and Δ-coordinated consensus, as well as their relationship to other distributed problems, such as determining the size of the network. We show that in the absence of a good initial upper bound on the size of the network, eventual consensus is as hard as computing deterministic functions of the input, e.g., the minimum or maximum of inputs to the nodes. We also give an algorithm for computing such functions that is optimal in every execution. Next, we show that simultaneous consensus can never be achieved in less than n - 1 rounds in any execution, where n is the size of the network; consequently, simultaneous consensus is as hard as computing an upper bound on the number of nodes in the network. For Δ-coordinated consensus, we show that if the ratio between nodes with input 0 and input 1 is bounded away from 1, it is possible to decide in time n-Θ(√ nΔ), where Δ bounds the time from the first decision until all nodes decide. If the dynamic graph has diameter D, the time to decide is min O(nD Δ),n-Ω(nΔ D) , even if D is not known in advance. Finally, we show that (a) there is a dynamic graph such that for every input, no node can decide before time n-O(Δ0.28n0.72); and (b) for any diameter D = O(Δ), there is an execution with diameter D where no node can decide before time Ω(nD Δ). To our knowledge, our work constitutes the first study of Δ-coordinated consensus in general graphs. The paper investigates the synchronization of a network of identical linear state-space models under a possibly time-varying and directed interconnection structure. The main result is the construction of a dynamic output feedback coupling that achieves synchronization if the decoupled systems have no exponentially unstable mode and if the communication graph is uniformly connected. The result can be interpreted as a generalization of classical consensus algorithms. Stronger conditions are shown to be sufficient-but to some extent, also necessary-to ensure synchronization with the diffusive static output coupling often considered in the literature. We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts other nodes and updates its current state based on the state communicated by the last contacted node. We assume that both signaling (the information exchanged at node contacts) and memory (computation state at each node) are limited and restrict our attention to systems where each node can contact any other node (i.e., complete graphs). It is well known that for systems with binary signaling and memory, the probability of reaching incorrect consensus is equal to the fraction of nodes that initially held the minority state. We show that extending both the signaling and memory by just one state dramatically improves the reliability and speed of reaching the correct consensus. Specifically, we show that the probability of error decays exponentially with the number of nodes N and the convergence time is logarithmic in N for large N. We also examine the case when the state is ternary and signaling is binary. The convergence of this system to consensus is again shown to be logarithmic in N for large N, and is therefore faster than purely binary systems. The type of distributed consensus problems that we study arises in the context of decentralized peer-to-peer networks, e.g. sensor networks and opinion formation in social networks - our results suggest that robust and efficient protocols can be built with rather limited signaling and memory. This paper provides a theoretical framework for analysis of consensus algorithms for multi-agent networked systems with an emphasis on the role of directed information flow, robustness to changes in network topology due to link node failures, time-delays, and performance guarantees. An overview of basic concepts of information consensus in networks and methods of convergence and performance analysis for the algorithms are provided. Our analysis framework is based on tools from matrix theory, algebraic graph theory, and control theory. We discuss the connections between consensus problems in networked dynamic systems and diverse applications including synchronization of coupled oscillators, flocking, formation control, fast consensus in small-world networks, Markov processes and gossip-based algorithms, load balancing in networks, rendezvous in space, distributed sensor fusion in sensor networks, and belief propagation. We establish direct connections between spectral and structural properties of complex networks and the speed of information diffusion of consensus algorithms. A brief introduction is provided on networked systems with nonlocal information flow that are considerably faster than distributed systems with lattice-type nearest neighbor interactions. Simulation results are presented that demonstrate the role of small-world effects on the speed of consensus algorithms and cooperative control of multivehicle formations This paper is concerned with the convergence of a class of continuous-time nonlinear consensus algorithms for single integrator agents. In the consensus algorithms studied here, the control input of each agent is assumed to be a state-dependent combination of the relative positions of its neighbors in the information flow graph. Using a novel approach based on the smallest order of the nonzero derivative, it is shown that under some mild conditions the convex hull of the agents has a contracting property. A set-valued LaSalle-like approach is subsequently employed to show the convergence of the agents to a common point. The results are shown to be more general than the ones reported in the literature in some cases. An illustrative example demonstrates how the proposed convergence conditions can be verified. In this paper, we study the problem of reaching a consensus among all the agents in the networked control systems (NCS) in the presence of misbehaving agents. A reputation-based resilient distributed control algorithm is first proposed for the leader-follower consensus network. The proposed algorithm embeds a resilience mechanism that includes four phases (detection, mitigation, identification, and update), into the control process in a distributed manner. At each phase, every agent only uses local and one-hop neighbors' information to identify and isolate the misbehaving agents, and even compensate their effect on the system. We then extend the proposed algorithm to the leaderless consensus network by introducing and adding two recovery schemes (rollback and excitation recovery) into the current framework to guarantee the accurate convergence of the well-behaving agents in NCS. The effectiveness of the proposed method is demonstrated through case studies in multirobot formation control and wireless sensor networks. In this paper, we investigate the convergence of the state of a quantum network to a consensus (symmetric) state. The state evolution of the quantum network with continuous-time swapping operators can be described by a Lindblad master equation, which also introduces an underlying interaction graph for the network. For a fixed quantum interaction graph, we prove that the state of a quantum network with continuous-time Markovian dynamics converges to a consensus state, with convergence rate given by the smallest nonzero eigenvalue of a matrix serving as the Laplacian of the quantum interaction graph. We show that this convergence rate can be optimized via standard convex programming given a fixed amount of edge weights. For switching quantum interaction graphs, we establish necessary and sufficient conditions for exponential quantum consensus and asymptotic quantum consensus, respectively. The convergence analysis is based on a bridge built between the proposed quantum consensus scheme and classical consensus dynamics, in that quantum consensus of n qubits naturally defines a consensus process on an induced classical graph with 22n nodes. Existing consensus results on classical networks can thus be adopted to establish the quantum consensus convergence. Inspired by the characteristics of biologically-motivated systems consisting of autonomous agents, we define the notion of stabilizing consensus in fully decentralized and highly dynamic ad hoc systems. Stabilizing consensus requires non-faulty nodes to eventually agree on one of their inputs, but individual nodes do not necessarily know when agreement is reached. First we show that, similar to the original consensus problem in the synchronous model, there exist deterministic solutions to the stabilizing consensus problem tolerating crash faults. Similarly, stabilizing consensus can also be solved deterministically in presence of Byzantine faults with the assumption that n > 3f where n is the number of nodes and f is the number of faulty nodes. Our main result is a Byzantine consensus protocol in a model in which the input to each node can change finitely many times during execution and eventually stabilizes. Finally we present an impossibility result for stabilizing consensus in systems of identical nodes.