control//multi-agent control//consensus protocol
A consensus protocol is a distributed rule by which every agent of a network repeatedly moves its value toward the values of the neighbours it hears, so that the whole group converges to a common value that no agent computes centrally. Five drones measuring air temperature with noisy sensors can agree on the average this way, talking only to those in range; the same rule makes a fleet agree on a heading, a meeting point or a shared estimate. The linear rule and its matrix form are
A consensus protocol is a distributed rule by which every agent of a network repeatedly moves its value toward the values of the neighbours it hears, so that the whole group converges to a common value that no agent computes centrally. Five drones measuring air temperature with noisy sensors can agree on the average this way, talking only to those in range; the same rule makes a fleet agree on a heading, a meeting point or a shared estimate. The linear rule and its matrix form are
x˙i=∑j∈Niaij (xj−xi)⟺x˙=−Lx.\dot x_i=\sum_{j\in\mathcal N_i}a_{ij}\,(x_j-x_i)\qquad\Longleftrightarrow\qquad \dot x=-Lx.x˙i=j∈Ni∑aij(xj−xi)⟺x˙=−Lx.
Here xix_ixi is agent iii's value, Ni\mathcal N_iNi its neighbours, aij>0a_{ij}>0aij>0 the weight it gives each, and LLL the graph Laplacian of the communication graph. Three facts do the work: L1=0L\mathbf 1=0L1=0, so agreement is an equilibrium; with symmetric links 1TL=0\mathbf 1^{\mathsf T}L=01TL=0, so the sum is conserved and the final value is the initial average; and the disagreement decays at least as e−λ2te^{-\lambda_2 t}e−λ2t (spectral gap). The mathematics of that flow lives in diffusion and consensus.
λ2 at the start0.852 links in range27 time constant13.0 s disagreement after 30 sunder 0.001 m Ten drones meet at one point by consensus over a 35 m radio, losing 10 % of packets, with gain 0.10 1/s. At the start λ2 = 0.852, so the disagreement should fall with a time constant near 1/(k(1 − p)λ2) = 13.0 s; it goes from 23.20 m to under 0.001 m in 30 s, faster than that, because the graph fills in as they gather. With a 15 m radio the same fleet splits into 4 groups and λ2 drops to 0.
Drop the radio range until the graph splits and λ2\lambda_2λ2 falls to zero: the disagreement line on the log plot goes flat, and each group agrees only with itself.
Consensus reaches the average on a connected graph at the speed of λ2\lambda_2λ2, and more links buy that speed with tolerance to delay. With a uniform delay τ\tauτ, x˙(t)=−Lx(t−τ)\dot x(t)=-Lx(t-\tau)x˙(t)=−Lx(t−τ) converges only if τ<π/(2λN)\tau<\pi/(2\lambda_N)τ<π/(2λN) (Olfati-Saber and Murray, 2004). Ten drones that all hear each other lose convergence at 157 ms of delay; the same ten in a chain hold to about 400 ms and agree a hundred times slower. The error moves (error relocation).
On board it runs in steps, x[k+1]=(I−εL) x[k]x[k+1]=(I-\varepsilon L),x[k]x[k+1]=(I−εL)x[k], which converges for 0<ε<2/λN0<\varepsilon<2/\lambda_N0<ε<2/λN; ε≤1/dmax\varepsilon\le 1/d_{\max}ε≤1/dmax, with dmaxd_{\max}dmax the largest degree, is the safe rule. Above the limit the values jump from side to side and diverge, like an over-tuned PID controller.
Lost packets make the graph flicker, and consensus survives if the union of the links over every bounded window is connected (Jadbabaie, Lin and Morse, 2003). With one-way links it converges if some agent reaches all the others along the arrows, to a weighted average that favours the most listened-to. Because moving changes the links, some variants deliberately preserve connectivity.
Max-consensus replaces the average by a maximum: each agent keeps the highest value it has heard, and the group agrees in as many rounds as the graph's diameter. It is how auction prices spread in task allocation.
An agent that never updates drags everyone to its value (leader-follower); against malicious agents there is resilient consensus. Agreement among replicas in the computing sense is a different problem under the same name (distributed consensus).