Jadbabaie et al. (2003) — DOI:10.1109/TAC.2003.812781
Key takeaways
The object. Vicsek et al.’s (1995) self-propelled particles, with the noise
removed: “The Vicsek system also includes noise input signals, which we ignore
in this paper.” Each agent sets its heading to the average of its own and its
neighbours’ (within radius r). The model is a switched linear system
θ(t+1) = F_σ(t) θ(t) over simple undirected graphs, with each F_p
row-stochastic with a positive diagonal.
The move that makes it tractable. The switching really depends on agent positions, but “it would be difficult to take into account in a convergence analysis”. The paper “ignores how σ depends on the agent positions … and assumes instead that σ might be any switching signal in some suitably defined set”. Every theorem is about arbitrary switching sequences meeting a connectivity hypothesis. None proves that the Vicsek dynamics produce one.
- Theorem 1. Connected at every step → headings converge to a common value.
- Theorem 2 (the main result). If there is an infinite sequence of contiguous, nonempty, bounded intervals across each of which “the n agents are linked together” (the union graph is connected), headings converge to a common value. The authors call contiguity “more restrictive than one might hope for”. Lengths may vary and need only be bounded. The proof goes through Wolfowitz’s theorem on infinite products of ergodic matrices (LIT-301), for which “The finiteness of the set … is crucial”.
- No common quadratic Lyapunov function. The system is stable and yet has none: “a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function”. This is established by a semidefinite-programming check on 10-vertex connected graphs with 9–10 edges, not proved analytically.
- Theorem 4 (leader following). One agent holds a fixed heading. If the followers are jointly linked to it across contiguous bounded intervals, they all converge to its heading.
- Theorem 5 (continuous time, with dwell time). Convergence to the leader holds for bounded, non-overlapping intervals (here not required to be contiguous), “no matter what the value of τ_D is, so long as τ_D is greater than zero”.
- A variant with gain
1/g,g > n, gives symmetric matrices with a common Lyapunov function, at the cost of every agent knowing a bound on group size. “A proof … will not be given.”
What the evidence does not cover
- Whether the Vicsek model generates such sequences. The paper expects the opposite for sparse starts: “with widely distributed initial agent positions and r very small, one would expect to see a bifurcation of the group into distinct subgroups”. It runs no simulations of its own.
- Any rate. Convergence is asymptotic, which is why the gossip practices that need a rate (spectral gap) do not rest on it.
- Noise. “the analysis in this paper is deterministic and does not address the noise issue”.
- Directed graphs. The directed spanning-tree condition the imported text attributed to this paper is later work.
- Headings on the circle. They are treated as reals in
[0, 2π), which the paper flags as a defect. - Priority. A 2007 comment by Bertsekas and Tsitsiklis (TAC 52(5), not read) says the update is a special case of their 1980s agreement algorithms (LIT-325) and “the main convergence results are essentially the same”. Do not call this paper “first” without that caveat. A 2003 correction by the authors (TAC 48(9)) exists and has not been read.
Standing in the anthology
Read — the reading is NOTE-136. Arrived in the imported batch, which brought in the consensus, synchronization and flocking literature that the decentralized-training results rest on.
Re-read in full on 2026-09-25, and the imported text was wrong in load-bearing ways (see the version note). The reading-time triage of that day proposed it as unheld. It was held all along. The feed’s URL for it was a different paper, Tahbaz-Salehi and Jadbabaie’s On Consensus Over Random Networks, the conference precursor of LIT-326.
No practice or theory cites it. It is background to SOTA-223 (resample the gossip topology every round), whose argument turns on a sequence of topologies. This paper is the classical statement that a sequence of individually disconnected graphs can still agree. It is not evidence for that practice’s rate claim.