Olfati-Saber and Murray (2004) — DOI:10.1109/TAC.2004.834113
Key takeaways
The reference for Laplacian consensus on directed networks. The undirected case was earlier work (the paper cites its own prior result for undirected graphs with and without delay); this paper extends the analysis to digraphs with fixed or switching topology, ties convergence speed to the Fiedler eigenvalue of a “mirror graph”, gives an exact bound on tolerable uniform delay, and adds a max-consensus protocol. Theorem numbers below are the Caltech preprint’s (May 2003), which is what was read; the TAC version’s numbering may differ.
- Strong connectivity is a rank condition (Theorem 1). A weighted digraph is strongly connected iff rank(L) = n − 1. With Theorem 3 (the limit of exp(−Lt) is w_r w_lᵀ for a strongly connected digraph), Corollary 1 gives consensus for protocol ẋ = −Lx on any strongly connected digraph — but the agreed value is a weighted average set by the left eigenvector, not necessarily the average.
- Average consensus on a digraph needs balance (Theorems 4–6). For a strongly connected digraph the protocol reaches the average of the initial states iff the graph is balanced (in-degree equals out-degree at every node), equivalently 1ᵀL = 0, which makes the average an invariant. A three-node connected digraph that fails to average is given as a counterexample.
- Speed is the Fiedler value of the mirror graph (Theorems 7–8). For a balanced graph, (L + Lᵀ)/2 is itself a valid Laplacian, of the “mirror” undirected graph Ĝ. For a balanced, strongly connected digraph the disagreement vanishes as ‖δ(t)‖ ≤ ‖δ(0)‖·e^{−λ₂(Ĝ)t}, with V(δ) = ½‖δ‖² as Lyapunov function.
- Switching topology (Theorem 9) — every graph balanced and strongly connected. If the topology switches arbitrarily within the set of digraphs that are each strongly connected and balanced, average consensus is reached, because ½‖δ‖² is a common Lyapunov function for every graph in the set; the rate is at least min λ₂(Ĝ) over the set. It does not prove consensus under connectivity of the union over a window — that weaker, jointly-connected condition is Jadbabaie et al.’s (LIT-285) result. Holds when: each graph in the switching set is individually strongly connected and balanced.
- Uniform delay (Theorem 10). For an undirected connected graph with the same delay τ on every link, the delayed protocol reaches average consensus iff τ < π/(2λ_max(L)); at τ = π/(2λ_max) it oscillates at frequency λ_max. The bound is on the largest Laplacian eigenvalue, so adding links (raising λ_max) shrinks the tolerable delay.
- Max-consensus (Theorem 11). A discrete-time max protocol with a Boolean leader flag reaches the network maximum in at most n − 1 iterations on a strongly connected digraph.
What the evidence does not cover
- Linear averaging dynamics, apart from the max-consensus protocol — no nonlinear couplings.
- No noise — stochastic consensus requires separate analysis (Tahbaz-Salehi for IID random topology).
- Uniform delay, and undirected graphs, for the delay result — heterogeneous delays and delays on digraphs are left open.
- The switching result needs every graph in the set to be connected; it says nothing about topologies that are disconnected at some instants.
- Continuous-time throughout for the averaging results; discrete-time versions are related only through the Euler-approximation remark.
Standing in the anthology
It takes LIT-285’s setting and changes both the graphs and the proof. Read in the Caltech preprint (April 2003) rather than the TAC version: Remark 6 says Jadbabaie et al.’s discrete-time heading update is the first-order Euler approximation of this paper’s continuous-time protocol with a particular choice of weights, and the paper moves the problem from LIT-285’s undirected graphs to directed ones, where average consensus holds exactly when the graph is balanced. Where LIT-285 argues through infinite products of stochastic matrices, this uses a disagreement function as a common Lyapunov function, so its switching-topology theorem (Theorem 9 in the preprint) asks that every graph in the switching set be strongly connected and balanced, a stronger hypothesis than LIT-285’s joint connectivity over intervals.
Read — the reading is NOTE-126. Arrived in the imported batch, which brought in the consensus, synchronization and flocking literature that the decentralized-training results rest on.