Consensus

"Nobody told me the answer. I just kept asking my neighbors what they thought, took the average, and somehow we all ended up agreeing on the same number."

A Sensor Node That Found the Mean Without a Manager

Up to this point in Chapter 29, agents have exchanged messages (Section 29.4), coordinated their actions (Section 29.5), and allocated tasks among themselves (Section 29.8). Each of those required agents to reach some common ground, but we treated the agreement informally. Consensus is the formal study of that agreement: given that every agent starts with its own number and can communicate only with a few neighbors, when and how fast can the whole population settle on a single shared value? The answer is one of the most reusable results in distributed intelligence, and it is the same averaging machinery that powers decentralized learning, so it ties this chapter back to the rest of the book.

1. The Consensus Problem on a Communication Graph Beginner

Model the agents as the nodes of a graph $G = (V, E)$, where $|V| = n$ agents and an edge $(i, j) \in E$ means agents $i$ and $j$ can exchange messages directly. This communication graph is the only structure an agent can see: it has no global address book, no broadcast channel, and no server. Each agent $i$ holds a scalar value $x_i$, which might be its current heading, a local temperature reading, an estimate of some quantity, or a vote. Collect these into a vector $x = (x_1, \dots, x_n)$. The agents reach consensus when all their values become equal, $x_1 = x_2 = \dots = x_n$. They reach average consensus, the case we care about most, when that common value is the global mean $\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i$ of the initial values, computed without any agent ever seeing all the values.

That last clause is the whole point. Computing an average is trivial if one machine can read every value; it is the textbook job of a central coordinator. Consensus asks the harder question: can a population compute that same average using only the local, peer-to-peer interactions allowed by the graph, with no node privileged over any other? When the answer is yes, the network has replaced a coordinator with a protocol, which is exactly the substitution that makes a swarm robust to the loss of any single agent. We distinguish this value-agreement problem sharply from the fault-tolerant log-agreement of Raft and Paxos, a different sense of "consensus" that we return to in Section 2 below.

2. Three Meanings of "Consensus", Kept Apart Intermediate

The word "consensus" names three related but distinct problems in distributed systems, and conflating them causes real confusion. It is worth fixing the boundaries before we derive anything, because the rest of this section treats only the first.

Average (or value) consensus is the subject here: agents holding real-valued data converge to a common value, typically the mean, through repeated local averaging. The agents are assumed cooperative and reliable; the challenge is purely the locality of communication. This is the version that appears across multi-agent systems and is mathematically the same object as the decentralized averaging that drives gossip-based learning, which we built in Section 14.8.

Fault-tolerant consensus is a different problem: a set of processes must agree on a single sequence of decisions (a replicated log) despite some of them crashing or messages being lost. This is the world of Paxos and Raft, where the value to agree on is discrete (the next log entry) and the adversary is failure, not locality. We covered leader election and this style of control-plane agreement in Section 2.6; it underpins schedulers and model registries rather than the numerical convergence we study here.

Byzantine consensus hardens fault-tolerant consensus against the worst case: some agents are malicious and may send arbitrary, even strategically inconsistent, messages. Agreement must still hold among the honest agents. This is the theoretical basis of robust aggregation, where a learner must combine updates from workers that may be actively trying to corrupt the result; we develop the Byzantine-robust machinery as part of reliable and secure distributed AI in Chapter 35.

The three share a name and a spirit (many parties, one outcome) but differ in what is being agreed on (a real number, a log, a log under attack) and in the adversary (locality, crashes, malice). Table 29.9.1 summarizes the split.

3. The Average-Consensus Protocol Intermediate

The protocol is one line. At each synchronous round $t$, every agent replaces its value with a weighted average of its own value and those of its neighbors:

where $\mathcal{N}(i)$ is the set of $i$'s neighbors and the weights $w_{ij} \ge 0$ on each agent sum to one, $w_{ii} + \sum_{j} w_{ij} = 1$. Stacking all $n$ updates into matrix form gives the compact recursion

where $W$ is the $n \times n$ matrix of weights, with $W_{ij} = w_{ij}$ if $j$ is a neighbor of $i$ (or $i$ itself) and zero otherwise. The matrix $W$ inherits the sparsity of the graph: agent $i$ only ever mixes in values from agents it can actually reach. The question of whether the agents converge, and to what, is now entirely a question about the powers $W^t$ of this one matrix.

For the agents to reach the average, the weight matrix must satisfy three conditions: each row sums to one (so $W\mathbf{1} = \mathbf{1}$, every agent keeps a convex combination and the all-ones vector is fixed), each column sums to one (so $\mathbf{1}^\top W = \mathbf{1}^\top$, which makes the sum $\sum_i x_i$ invariant and therefore preserves the mean), and the associated graph is connected. A symmetric, doubly stochastic $W$ such as the Metropolis weights, where $w_{ij} = 1/(1 + \max(d_i, d_j))$ for each edge and $d_i$ is the degree of node $i$, satisfies the first two automatically and is the standard choice. Under these conditions a classical result holds: $W^t \to \frac{1}{n}\mathbf{1}\mathbf{1}^\top$, so

Every agent converges to the exact global average, computed with nothing but local exchanges. Figure 29.9.1 shows the geometry: values held at the nodes of a connected graph relax, round by round, toward a common level.

4. Why It Converges: The Spectral Gap Advanced

The rate of convergence is not a mystery; it is an eigenvalue. Because $W$ is symmetric and doubly stochastic, its eigenvalues are real and lie in $[-1, 1]$, and they can be ordered as $1 = \lambda_1 > \lambda_2 \ge \dots \ge \lambda_n \ge -1$. The eigenvalue $\lambda_1 = 1$ has eigenvector $\mathbf{1}$, the consensus direction; it is exactly the component that $W$ leaves untouched, which is why the average survives. Every other eigenvalue has magnitude strictly less than one when the graph is connected, so every component of $x(0)$ orthogonal to $\mathbf{1}$ (that is, the disagreement among agents) is multiplied by a factor smaller than one each round and decays geometrically. Writing the disagreement as $x(t) - \bar{x}\mathbf{1}$, its norm shrinks as

where $\rho < 1$ is the second-largest eigenvalue magnitude. The convergence is geometric with ratio $\rho$, and the relevant quantity is the spectral gap $1 - \rho$: a larger gap means $\rho$ is smaller, so disagreement collapses faster. The number of rounds to reach a fixed tolerance scales like $1/(1 - \rho)$, the same mixing-time quantity that governs how fast a random walk on the graph forgets where it started, and the same quantity that sets the rate of gossip averaging in decentralized learning.

5. Communication Versus Convergence: A Runnable Demonstration Intermediate

The theory predicts two things we can check directly: every agent should converge to the exact global average regardless of the graph, and a graph with a larger spectral gap should converge in fewer rounds. The code below runs the protocol from Section 3 on $n = 24$ agents with random initial values, over two graphs: a sparse ring where each agent talks only to its two immediate neighbors, and a denser circulant graph where each agent talks to its eight nearest neighbors. It uses Metropolis weights for both, measures each graph's spectral gap, and counts the rounds needed to drive the maximum deviation from the mean below $10^{-3}$.

import numpy as np

def ring_adjacency(n):
    A = np.zeros((n, n))
    for i in range(n):
        A[i, (i - 1) % n] = 1
        A[i, (i + 1) % n] = 1
    return A

def dense_adjacency(n, k):                       # each node links k neighbors per side
    A = np.zeros((n, n))
    for i in range(n):
        for d in range(1, k + 1):
            A[i, (i - d) % n] = 1
            A[i, (i + d) % n] = 1
    return A

def metropolis_weights(A):                       # symmetric doubly stochastic W
    n = A.shape[0]
    deg = A.sum(axis=1)
    W = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if A[i, j] > 0:
                W[i, j] = 1.0 / (1.0 + max(deg[i], deg[j]))
        W[i, i] = 1.0 - W[i].sum()               # self-weight closes the row to 1
    return W

def spectral_gap(W):
    eig = np.sort(np.abs(np.linalg.eigvals(W)))[::-1]
    return float(1.0 - eig[1])                   # 1 - second-largest |eigenvalue|

def run_consensus(W, x0, rounds):
    x, target, hist = x0.copy(), x0.mean(), []
    for _ in range(rounds):
        hist.append(np.max(np.abs(x - target)))  # max deviation from the global mean
        x = W @ x                                 # the one-line update, applied to all
    return x, hist

n = 24
rng = np.random.default_rng(7)
x0 = rng.uniform(0.0, 100.0, size=n)
global_avg = x0.mean()

graphs = {
    "ring (deg 2)":  metropolis_weights(ring_adjacency(n)),
    "dense (deg 8)": metropolis_weights(dense_adjacency(n, 4)),
}

rounds = 400
print(f"agents               : {n}")
print(f"global average        : {global_avg:.6f}\n")
for name, W in graphs.items():
    gap = spectral_gap(W)
    xf, hist = run_consensus(W, x0, rounds)
    reached = next((r for r, e in enumerate(hist) if e < 1e-3), rounds)
    print(f"{name:14s} | spectral gap = {gap:.4f} | "
          f"final consensus = {xf.mean():.6f} | "
          f"max spread = {np.max(xf) - np.min(xf):.2e} | "
          f"rounds to 1e-3 = {reached}")

agents               : 24
global average        : 52.329889

ring (deg 2)   | spectral gap = 0.0227 | final consensus = 52.329889 | max spread = 1.11e-03 | rounds to 1e-3 = 375
dense (deg 8)  | spectral gap = 0.2135 | final consensus = 52.329889 | max spread = 0.00e+00 | rounds to 1e-3 = 36

The two results together are the entire lesson of consensus in one screen. The final value is identical because doubly stochastic averaging preserves the mean no matter how the edges are arranged; the number of rounds differs by an order of magnitude because the spectral gap differs by an order of magnitude. That is the communication-versus-convergence trade-off in concrete form: the dense graph converges roughly ten times faster, but it pays for it by sending four times as many messages per round (degree eight instead of degree two). Whether that trade is worth it depends on whether your bottleneck is rounds (latency) or messages (bandwidth), a decision the cost models of Chapter 3 are built to make.

import networkx as nx, numpy as np

G = nx.cycle_graph(24)                          # or any graph: random, small-world, real
L = nx.normalized_laplacian_matrix(G).toarray() # the consensus operator's close cousin
gap = np.sort(np.linalg.eigvalsh(L))[1]         # algebraic connectivity (Fiedler value)
print(f"spectral gap (rate of consensus): {gap:.4f}")

6. Where Consensus Shows Up in Multi-Agent Systems Beginner

Average consensus is not a niche trick; it is the computational backbone of a surprising range of multi-agent behaviors, because so many of them reduce to "everyone agree on one number, locally". Three families dominate. The first is motion coordination: in flocking, each agent steers its heading toward the average heading of its neighbors, and the consensus dynamics are precisely what align a flock into a common direction; in rendezvous, agents drive their positions toward the average position and meet at a common point. We treat flocking and its distributed-consensus core directly in the swarm chapter, Section 31.5. The second is distributed estimation: a field of sensors, each with a noisy local measurement, can fuse them into a single shared estimate (the average is the maximum-likelihood fuse for independent equal-variance noise) without any sensor reporting to a base station, which is consensus-based sensor fusion. The third is synchronization: distributed clocks or coupled oscillators agree on a common time or phase by the same neighbor-averaging rule. In every case the appeal is identical, robustness: there is no coordinator to lose, and the network keeps working as agents join, leave, or fail, as long as the graph stays connected.

7. The Trade-Off and the Coordinator It Replaces Intermediate

Consensus is the decentralized counterpart to a central coordinator, and the comparison is worth stating plainly because it recurs throughout distributed AI. A coordinator computes the aggregate in one shot but is a single point of failure, a bottleneck, and (in adversarial settings) a trust assumption. Consensus computes the same aggregate over many rounds but tolerates the loss of any agent, spreads the communication evenly, and needs no privileged node. The cost it pays is rounds, and the dial that sets that cost is the spectral gap. This produces a clean and unavoidable trade-off: a denser communication graph has a larger spectral gap and therefore converges in fewer rounds, but each round costs more messages because every agent talks to more neighbors. There is no free topology. A sparse ring is cheap per round and slow to converge; a fully connected graph converges almost instantly but reproduces the all-to-all communication cost that distribution was meant to avoid. Real deployments tune the graph to sit where the product of rounds and per-round cost is smallest, which is the same alpha-beta reasoning that Chapter 3 applies to collective communication, now applied to a network of agents instead of a fleet of workers.

With consensus, the agents of this chapter can now agree on a shared value using nothing but local interaction, which closes the loop opened by communication and coordination in the earlier sections. One assumption has quietly carried this entire section: that the agents are cooperative and that the values they report are honest. The moment some agents may lie, lag, or act in self-interest, average consensus alone is not enough, and the network needs a way to decide whom to believe. That is the subject of the next section, which turns from agreeing on a value to deciding which agents are worth listening to. We take up trust and reputation in Section 29.10.