PaperlayerView exact revision on arXiv

Source-linked AI summary

Average Consensus on General Strongly Connected Digraphs

Kai Cai, Hideaki Ishii

arXiv:1203.2563v1eess.SY

TL;DR

The paper addresses average consensus with unidirectional information flow, where arbitrary strongly connected digraphs need not preserve the agents’ state sum. It introduces surplus-based linear algorithms for synchronous and asynchronous communication and proves averaging under this topology condition. The synchronous algorithm achieves asymptotic state averaging, while the asynchronous gossip algorithm achieves mean-square and almost-sure average consensus.

  • Problem

    Average consensus on arbitrary strongly connected digraphs is challenging because unidirectional information flow need not preserve the agents’ state sum.

  • Method

    The paper augments each agent with a surplus variable that records state changes and develops linear deterministic and gossip algorithms for synchronous and asynchronous communication.

  • Results

    The algorithms guarantee average consensus on arbitrary strongly connected digraphs: asymptotically in synchronous networks, and in the mean-square sense and with probability one in asynchronous networks.

  • Takeaways & Limitations

    Strong connectivity alone is sufficient for the paper’s state-averaging guarantees, extending the graphical conditions reported previously.

Abstract

from arXiv · show

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

I. INTRODUCTION

The paper develops linear distributed algorithms for average consensus under synchronous and asynchronous communication, extending guaranteed state averaging to arbitrary strongly connected digraphs. Its surplus variables address non-preserved state sums, while matrix perturbation tools support convergence analysis.

  • I. INTRODUCTION: The paper studies average consensus under both synchronous and asynchronous communication setups.It presents corresponding distributed algorithms for these two communication regimes.
  • I. INTRODUCTION: The algorithms guarantee state averaging on arbitrary strongly connected digraphs, without requiring balanced or symmetric networks.This generalizes graphical conditions associated with earlier approaches based on balanced, strongly connected, or symmetric topologies.
  • I. INTRODUCTION: The central challenge is that directed information flow can make the agents’ state sum vary, shifting the average over time.The paper explicitly frames non-preservation of the state sum as the primary difficulty on arbitrary strongly connected digraphs.
  • I. INTRODUCTION: Each agent receives a surplus variable that records its state changes, collectively retaining information about the shift in the average.This surplus mechanism differs from auxiliary-variable approaches that use extra variables for other purposes.
  • I. INTRODUCTION: The proposed algorithms are linear, allowing convergence to be analyzed through associated matrix spectra, nonnegative matrix theory, algebraic graph theory, and perturbation tools.Eigenvalue perturbation, optimal matching distance, and the Bauer-Fike Theorem are identified as important analytical tools.
  • I. INTRODUCTION: The paper rigorously proves state-averaging guarantees for its synchronous and asynchronous solution algorithms on general strongly connected digraphs.The paper also includes specialized topology results, numerical examples, and conclusions addressing these algorithms.

II. PROBLEM FORMULATION

The paper formulates average consensus for synchronous and asynchronous directed networks, using surplus variables to preserve the initial state sum on general strongly connected digraphs.

  • Network model: A digraph models agents and directed information flow, with each edge (j, i) indicating communication toward agent i.Strong connectivity means every node is reachable from every other node.
  • Consensus objective: Average consensus requires all states to converge to the initial average xa using only local neighbor information.The target is (xa1, 0) when surplus variables are included.
  • Consensus objective: On general digraphs, the state sum need not remain invariant, so agents augment each node with a surplus variable si(k).Surplus locally records state changes and is initialized at zero.
  • Consensus objective: The surplus preserves the global quantity 1T(x+s), which equals the initial state sum throughout the iterations.This restores the quantity needed to track the initial average.
  • Synchronous networks: The paper studies synchronous updates in which every node communicates with its neighbors simultaneously, then updates its state and surplus.The deterministic protocol sends states and weighted surpluses along directed edges.
  • Algorithm scope: Surplus-based distributed algorithms are proposed for both settings and are asserted to achieve average consensus on general strongly connected digraphs.The synchronous and gossip algorithms use locally stored, updated, and exchanged state and surplus variables.
  • Asynchronous networks: The asynchronous setting activates exactly one directed edge at random, allowing the receiving node to update from the sender’s state and surplus.Each edge has a time-invariant strictly positive activation probability.
  • Asynchronous networks: The paper defines mean-square and almost sure average consensus for gossip dynamics, distinguishing convergence of moments from convergence along sample paths.It notes that neither convergence notion generally implies the other.

B. Convergence Result

The deterministic surplus-based algorithm achieves exact average consensus on strongly connected digraphs, including non-balanced graphs, under a sufficiently small parameter choice.

  • Proof strategy: The convergence analysis uses eigenvalue perturbation to show that a small positive ǫ separates one eigenvalue at 1 from the remaining spectrum.The result is established through a graphical characterization and perturbation-based proof.
  • Convergence result: The deterministic algorithm achieves average consensus if and only if the digraph is strongly connected.This removes the balance requirement present in standard state-only consensus algorithms.
  • Convergence result: Unlike the earlier quantized surplus method, this linear algorithm converges to the exact average with zero steady-state surpluses.Its convergence is analyzed using matrix theory rather than finite-state Markov-chain arguments.
  • Parameter condition: For strongly connected graphs, average consensus is guaranteed when ǫ lies in (0, ¯ǫ(d)).The bound depends on the graph and the number of agents.
  • Parameter condition: The bound ¯ǫ(d) is conservative because it contains a factor raised to the power n, although this dependence is unavoidable for general perturbation bounds.The paper attributes the conservatism to general matrix perturbation theory.
  • Parameter condition: Bounding ǫ requires information about the agent-network structure, including spectral information tied to the graph topology.The paper identifies this non-local requirement as a practical constraint.

C. Proof of Theorem 1

The theorem characterizes average consensus spectrally: the update matrix must have a simple eigenvalue at 1 and all other eigenvalues strictly inside the unit circle.

  • Spectral criterion: The deterministic algorithm achieves average consensus if and only if 1 is a simple eigenvalue of M and every other eigenvalue has modulus below one.This converts convergence into a spectral condition on the augmented state-surplus matrix.
  • Spectral criterion: Because the columns of M sum to one, 1 is always an eigenvalue and the quantity x(k)+s(k) remains constant.The proof then studies whether the remaining modes decay.
  • Proof strategy: The augmented matrix M is larger and can contain negative entries, so standard nonnegative matrix tools cannot be applied directly.The proof therefore relies on spectral perturbation methods for general matrices.
  • Necessity: Without strong connectivity, closed components can retain different initial states, preventing average consensus.This supplies the necessity direction of the theorem.
  • Unperturbed system: Strong connectivity makes I−L and S irreducible stochastic matrices, yielding simple Perron eigenvalues and a semisimple double eigenvalue at 1 for M0.This establishes the unperturbed spectral structure used in the proof.
  • Perturbation argument: For sufficiently small positive ǫ, continuity keeps the remaining eigenvalues inside the unit circle, producing the spectral condition for consensus.The proof concludes by applying the spectral proposition.

D. Proof of Proposition 1

The proposition is proved by bounding spectral movement under the perturbation ǫF and showing that every non-unit eigenvalue remains strictly inside the unit circle.

  • Perturbation bound: The spectral matching distance between M0 and M measures how far the perturbed eigenvalues can move from the unperturbed spectrum.An upper bound controls this movement using matrix norms and ǫ.
  • Perturbation bound: The perturbation estimate bounds d(σ(M0),σ(M)) by a norm expression involving M0, M, and ǫF.This estimate is the quantitative basis for choosing a valid parameter range.
  • Remaining eigenvalues: For ǫ in (0, ¯ǫ(d)), the eigenvalues λ3(ǫ), ..., λ2n(ǫ) have moduli below one.Their unperturbed counterparts already lie strictly inside the unit circle.
  • Unit eigenvalue: For ǫ in (0, ¯ǫ(d)), λ2(ǫ) also satisfies |λ2(ǫ)|<1, completing the spectral condition.The proof excludes complex-unit, −1, and repeated-1 alternatives.
  • Conclusion: Combining the bounds gives λ1(ǫ)=1 and |λ2(ǫ)|,...,|λ2n(ǫ)|<1, so the deterministic algorithm achieves average consensus.This establishes Proposition 1.

IV. AVERAGING IN ASYNCHRONOUS NETWORKS

The paper introduces a surplus-based gossip algorithm for asynchronous directed networks and establishes mean-square and almost sure average-consensus results for arbitrary strongly connected topologies.

  • The surplus-based gossip algorithm extends earlier average-consensus algorithms beyond undirected graphs to arbitrary strongly connected topologies.The approach augments the agents’ states with surplus variables that track individual state updates.

A. Algorithm Description

The asynchronous protocol activates one directed edge at random per iteration and updates transmitted states and surpluses locally. Its analysis uses an i.i.d. random matrix sequence and spectral conditions on a Kronecker-product expectation.

  • A. Algorithm Description: At each iteration, exactly one directed edge is activated independently, transmitting the sender’s state and surplus to the receiving node.The receiving node updates using a weight wij and parameter ǫ, while the sender’s surplus is reset to zero.
  • A. Algorithm Description: The update preserves x(k) + s(k), although its matrix M(k) can contain negative entries because of the Laplacian block.The matrices M(k) are i.i.d. under the assumed edge-activation distribution.
  • A. Algorithm Description: Surplus variables locally record individual state updates, addressing the loss of state-sum invariance in directed gossip networks.States and surpluses can be implemented as ordinary variables with local exchange and update rules.
  • B. Convergence Result: Mean-square convergence is reduced to the spectral behavior of E[M(k) ⊗ M(k)] through the consensus-error dynamics.Vectorizing the error outer product yields the recursion involving M(k) ⊗ M(k).
  • B. Convergence Result: For sufficiently small ǫ, the expected Kronecker matrix has a simple eigenvalue 1 and all remaining eigenvalues with modulus below one.This spectral property establishes the gossip algorithm’s mean-square average consensus on strongly connected digraphs.
  • B. Convergence Result: Eigenvalue perturbation shows that one eigenvalue remains at 1 while the relevant other eigenvalues move left for small positive ǫ.Continuity then yields a sufficiently small interval of ǫ values for which all other eigenvalues have modulus below one.

V. SPECIAL TOPOLOGIES

The paper specializes deterministic-consensus analysis to balanced, symmetric, and cyclic topologies, deriving less conservative parameter bounds than the general bound and validating them through stability analysis.

  • Symmetric and Cyclic Digraphs: For symmetric or cyclic digraphs, the paper derives analytic ǫ bounds less conservative than the general bound.The specialization exploits additional topology structure to improve the parameter bounds.
  • Balanced Digraphs: For strongly connected balanced digraphs, the deterministic algorithm achieves average consensus when the polynomial roots associated with nonzero Laplacian eigenvalues lie inside the unit circle.The proof analyzes the eigenvalues of the algorithm matrix through the Laplacian spectrum.
  • Balanced Digraphs: Kharitonov-based analysis produces upper bounds on ǫ that grow linearly with n, contrasting with the general bound’s exponential decay.The paper attributes this difference to decreasing uncertainty in the polynomial coefficients as n increases.
  • Balanced Digraphs: The true bound on ǫ is reported to lie between the analytically derived solid and dashed curves, whose discrepancy is relatively small.The dashed curve uses minima over 1000 random samples satisfying the stability inequalities.

A. Connected Undirected Graphs

For connected undirected graphs, a simple explicit upper bound on ǫ guarantees deterministic average consensus, and this bound grows as the number of nodes increases.

  • ǫ ∈ (0, (1 − (1/n))(2 − (1/n))) guarantees average consensus for the deterministic algorithm on any connected undirected graph.The graph’s symmetry makes its Laplacian eigenvalues real, enabling the Jury stability test.
  • Under this bound, the algorithm matrix has a simple eigenvalue λ1 = 1 and all other eigenvalues in (0, 1).Proposition 2 then yields average consensus.
  • The upper bound ensuring average consensus grows as n increases, matching the reported behavior for the broader class of balanced digraphs.This comparison is made with the bounds displayed in Fig. 2.

B. Cyclic Digraphs

For cyclic strongly connected digraphs, the deterministic algorithm’s convergence is analyzed through matrix perturbation and Fourier-based diagonalization. A parameter bound ensures average consensus.

  • B. Cyclic Digraphs: The deterministic algorithm achieves average consensus on cyclic strongly connected digraphs when ǫ satisfies a derived upper bound.The proof studies the algorithm’s eigenvalues as perturbations of those of an unperturbed matrix.
  • B. Cyclic Digraphs: The algorithm matrix is decomposed as M = M0 + ǫF, enabling Bauer–Fike eigenvalue perturbation analysis.The perturbation bound places eigenvalues of M near eigenvalues of M0.
  • B. Cyclic Digraphs: For cyclic digraphs, the Laplacian is circulant and can be unitarily diagonalized using the Fourier matrix.This diagonalization establishes that the unperturbed matrix M0 is diagonalizable.
  • B. Cyclic Digraphs: The eigenvalue analysis gives λ1(ǫ) = 1 while all other eigenvalues lie strictly inside the unit circle under the bound.This spectral condition yields average consensus through the stated deterministic-algorithm proposition.

2. It then follows

The perturbation argument shows that sufficiently small ǫ keeps the relevant eigenvalues inside the unit circle, proving convergence of the deterministic algorithm. The resulting bound becomes more conservative as network size increases.

  • 2. It then follows: The perturbation bound guarantees that the perturbed eigenvalues remain within the unit circle.It establishes |λl(ǫ) − λl′| < 1 − |λ3| for the relevant eigenvalues.
  • 2. It then follows: λ1(ǫ) = 1 and all remaining eigenvalues have modulus below one, so the deterministic algorithm achieves average consensus.This follows from the spectral characterization of convergence.
  • 2. It then follows: The upper bound on ǫ decays as the number n of nodes increases for cyclic digraphs.The paper contrasts this behavior with the bound for the more general class of balanced digraphs.
  • 2. It then follows: The cyclic-digraph proof relies on a perturbation result specific to diagonalizable matrices, yielding a less conservative bound than the general result.The limitation is tied to the diagonalizability assumption in the perturbation theorem.

VI. NUMERICAL EXAMPLES

Numerical examples test both algorithms on strongly connected, non-balanced digraphs. They show that convergence depends on ǫ and network connectivity, with more communication channels generally improving speed and robustness.

  • VI. NUMERICAL EXAMPLES: The experiments use strongly connected, non-balanced digraphs with 10 nodes and 17, 29, and 38 edges.Both algorithms are applied with uniform weights and probabilities on these graphs.
  • VI. NUMERICAL EXAMPLES: Small ǫ ensures convergence of both algorithms, while large ǫ can lead to instability.The gossip algorithm requires smaller ǫ for mean-square convergence.
  • VI. NUMERICAL EXAMPLES: As the number of edges increases from Ga to Gc, convergence becomes faster and the algorithms tolerate a larger range of ǫ values.The results associate additional communication channels with faster convergence and greater robustness.
  • VI. NUMERICAL EXAMPLES: With ǫ = 0.7 on Ga, the deterministic algorithm reaches state averaging and the surplus vanishes, whereas the gossip algorithm fails to converge.Applying gossip to Gb and Gc restores average consensus, with faster convergence on Gc.

B. Convergence Speed versus Parameter ǫ

The convergence factor varies nonmonotonically with ǫ: increasing ǫ can initially accelerate convergence, but eventually causes slower convergence and divergence. The paper concludes with broader scope and future-work boundaries.

  • B. Convergence Speed versus Parameter ǫ: For the deterministic algorithm, increasing ǫ initially decreases the convergence factor and speeds convergence, before eventually increasing it and causing divergence.The transition occurs when the dominant inner and outer eigenvalue moduli exchange roles.
  • B. Convergence Speed versus Parameter ǫ: The gossip algorithm shows a similar dependence of its convergence factor on ǫ, motivating searches for minimizing parameter values and convergence bounds.The paper identifies these as directions for improving convergence-speed analysis.
  • VII. CONCLUSIONS: The proposed algorithms achieve average consensus on arbitrary strongly connected digraphs without requiring balanced network structure.The deterministic algorithm applies to synchronous networks, while the gossip algorithm applies to asynchronous networks.
  • VII. CONCLUSIONS: Extending the deterministic algorithm to time-varying digraphs and jointly strongly connected networks remains future work.The jointly strongly connected case is described as more challenging and requiring further investigation.
Loading 1203.2563v1…