09 Distributed Consensus & Task Allocation · #35 of 46

Average Consensus

How a crowd agrees on a number with nobody in charge

A dense cluster of thousands of honeybees hanging from a tree branch, a swarm in the middle of choosing a new home. — Ten thousand bees, one decision, zero managers. The queen is in there somewhere, and she gets no vote. · T. Voekler, CC BY-SA 3.0

Ten thousand honeybees, hanging from a branch, have to pick a new home, and get it wrong only at the cost of the entire colony.

There is no architect bee. There is no committee. There is no boss. And yet they decide, reliably, in hours.

The trick the bees use has a name in robotics, and it is shockingly simple: keep nudging your opinion toward your neighbours' until everyone lands in the same place. Stir a swarm of agents that each only talk to whoever's nearby, and (with no leader, no map, no central tally) they all glide to the exact global average of where they started. Let's watch it happen, then prove it can't fail.

16 agents spread 0.000 avg 0.000 step 0 converging

disagreement (spread) per iteration — flatter, slower decay at small α; steeper at large α; spikes/ringing once α passes the stability limit

step size α 0.18

drag a node up or down to pin its value, then watch its neighbours get pulled toward it

Try this:

Watch the spread collapse. The nodes start with random values (radius and colour both encode the value). Each step, every node averages itself toward its graph neighbours. The cloud of disagreement shrinks to a single number, the global mean, shown in the readout.
Push α too far. Drag the step size up. Small steps crawl in; large steps overshoot and ring like a struck bell; push past the limit and it diverges outright. There is a knife-edge, and below we'll derive exactly where it sits.
Reset and re-run. New random values, same connected ring, and they always converge to the new average. The destination is set the instant the agents are born; the network only decides how fast they get there.

The whole algorithm fits in one line

Forget leaders. Each agent $i$ holds a number $x_i$ and follows one rule, forever:

x_i(t+1) = x_i(t) + \alpha \sum_{j \in N_i} \bigl(x_j(t) - x_i(t)\bigr)

Read it out loud: look at each neighbour, take a fraction $\alpha$ of the gap between us, step that way. If your neighbours are mostly above you, you drift up. If they're below, you drift down. Nobody computes the average. Nobody is allowed to. And yet the average is precisely where everyone ends up.

Why? Because the rule conserves the total. Every gap you close, your neighbour closes by the same amount in the opposite direction: what you gain, they lose. The sum $\sum_i x_i$ never changes, so the only value everyone can agree on is the one that preserves it: the mean of the starting numbers.

Connectivity is everything

There is exactly one thing that can break this: if the communication graph falls into disconnected islands, each island averages itself into its own local consensus and the islands never reconcile. Two cliques, two answers, no agreement. The math has a single, beautiful gatekeeper for this, a number called $\lambda_2$ , the algebraic connectivity of the graph.

A wonderful consequence: this is robust by construction. Lose an agent, drop a link, add a newcomer mid-run: as long as the survivors stay connected, the swarm just re-converges to the new average. No leader means no single point of failure. You cannot decapitate a system that has no head.

The linear-algebra proof: why it always converges, and exactly how fast

Stack every agent's value into a vector $x(t)$ . The one-line rule becomes a single matrix step:

x(t+1) = (I - \alpha L)\, x(t)

where $L$ is the graph Laplacian, degree on the diagonal, $-1$ for each edge. $L$ is symmetric and positive-semidefinite, so its eigenvalues are real and non-negative:

0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_{\max}

The smallest is always $\lambda_1 = 0$ , with eigenvector $\mathbf{1}$ (all ones): that is the conserved-average direction, the agreement we want. Convergence hinges on the other eigenvalues shrinking under repeated multiplication by $(I - \alpha L)$ . Each mode scales by $(1 - \alpha \lambda_k)$ per step, so we need every one of those factors to have magnitude below 1:

0 < \alpha < \frac{2}{\lambda_{\max}(L)}

Step past that bound and the high-frequency mode flips sign and grows. That's the overshoot-into-divergence you can trigger in the demo. Stay inside it and the disagreement decays geometrically, governed by the slowest non-trivial mode, $\lambda_2$ :

\| x(t) - \bar{x}\,\mathbf{1} \| \;\le\; (1 - \alpha\lambda_2)^{t}\, \| x(0) - \bar{x}\,\mathbf{1} \|

A disconnected graph has $\lambda_2 = 0$ (a second zero eigenvalue, one per component), the decay factor becomes 1, and consensus stalls forever. Connected means $\lambda_2 > 0$ means guaranteed agreement. The entire theory rides on the second-smallest eigenvalue of a sparse symmetric matrix, which is why control theorists are quietly obsessed with it.

That same matrix $L$ has a surprising back-story. It is named after Pierre-Simon Laplace, but its first job in graph form had nothing to do with swarms or even computers: it was built to model electrical networks. Treat each edge as a resistor and the Laplacian is exactly the matrix that Kirchhoff's circuit laws hand you, which is why it also goes by "Kirchhoff matrix" and "admittance matrix." A swarm draining its disagreement away is, mathematically, current settling into a circuit.

Why averaging is secretly a random walk (and why that guarantees agreement)

Pull the averaging rule apart and a random walker falls out. Divide each agent's update by its own degree (how many neighbours it has) and the step becomes "replace my value with the average of my neighbours' values." Written as a matrix, that is multiplication by $P = D^{-1} A$ , where $A$ is the adjacency matrix and $D$ is the diagonal of degrees. And $P$ is exactly the transition matrix of a random walk on the graph: row $i$ is the probabilities of hopping from node $i$ to each of its neighbours.

The graph Laplacian sees this directly. Its random-walk-normalized form is

L^{\text{rw}} = I - P

so the eigenvalues of $L^{\text{rw}}$ and the random walk $P$ are locked together. Asking "does consensus converge?" is the same question as "does a random walker forget where it started?" On any connected, non-bipartite graph the walk mixes to a unique stationary distribution, every initial bias washes out, and the opinions do exactly the same thing for exactly the same reason. Diffusion, gossip, PageRank, and a settling swarm are all the same eigenvalue problem wearing different clothes.

The same trick, everywhere

Once you see average consensus, you find it running under half of distributed robotics. A sensor network agrees on a temperature estimate that beats any single noisy reading. A drone formation agrees on a common heading. A swarm splits a task list, or settles on a rendezvous point, all by the same local-averaging heartbeat. Replace "value" with "vote," add a quorum threshold, and you have something close to how the bees choose their home, or how a blockchain agrees on a ledger.

Key takeaways

Average consensus: each agent repeatedly averages its value toward its neighbours, and all converge to the global mean: no leader, no central tally.
The whole algorithm is one line: $x_i \leftarrow x_i + \alpha \sum_{j \in N_i} (x_j - x_i)$ . It conserves the total, so the mean is the only possible meeting point.
Connectivity decides everything: a connected graph guarantees agreement; how fast is set entirely by $\lambda_2$ , the network's algebraic connectivity.
Step size has a knife-edge: stay inside $0 < \alpha < 2/\lambda_{\max}(L)$ or the values overshoot and blow up.

Run the consensus yourself

Five agents in a ring, each one repeatedly nudging toward its two neighbours. They start far apart and should all settle on the global mean. The step size alpha is this lesson's knob: small is slow but safe, too large makes the values overshoot and ring instead of settling. Change it and run it again.

Average consensus editable · Python

vals = [10.0, 2.0, 7.0, 1.0, 5.0]
n, alpha = len(vals), 0.3
print("start:", [round(v,2) for v in vals], " global mean =", round(sum(vals)/n,2))
for step in range(16):
  new = vals[:]
  for i in range(n):
      left, right = vals[(i-1)%n], vals[(i+1)%n]
      new[i] = vals[i] + alpha*((left-vals[i])+(right-vals[i]))
  vals = new
  if step % 3 == 0:
      print(f"step {step:2d}:", [round(v,2) for v in vals])
print("final:", [round(v,3) for v in vals])

ready

A bee knows nothing of eigenvalues. It dances a little harder for a hole it liked, watches its sisters, and changes its mind. Multiply that by ten thousand and a decision emerges that no single bee ever made.

That is the quiet promise of consensus: agreement without authority, intelligence without a brain at the centre. Build a swarm with no boss, wire it so the gossip can reach every corner, and then simply let the disagreement drain away.