Removing the Server: Gossip and Decentralized SGD

Everything so far had a central server: it broadcasts the model, collects updates, aggregates, repeats. That is simple and it introduces four difficulties.

It is a bottleneck. Every client communicates with one machine each round, so the server's bandwidth is consumed in proportion to participant count. At large scale the coordinator saturates before the participants do.

It is a single point of failure. Server down, training stopped.

It is a point of trust. Somebody operates it, and that party sees every client's update. Among competing hospitals or banks, agreeing on who that party should be can be harder than the technical work.

It may not exist. Devices on a local network, vehicles in proximity, or sensors in the field may have no natural coordinator at all.

Decentralized learning removes it. Each node holds its own model, communicates only with neighbours in a communication graph, and there is no global view anywhere in the system. This is a research focus of Martin Jaggi's lab at EPFL, and the question it answers is whether coordination is actually necessary.

The building block is a classical algorithm for a deceptively simple problem: average consensus. Every node holds a number; make them all agree on the average, using only neighbour-to-neighbour communication.

The gossip protocol is one line. Repeatedly, each node replaces its value with a weighted average of its own and its neighbours':

$x_i \leftarrow \sum_{j \in \mathcal{N}(i) \cup \{i\}} W_{ij} \, x_j$

The matrix W encodes the graph and the mixing weights. Choose it doubly stochastic, with rows and columns summing to one, and two properties hold: the global average is exactly preserved at every step, and every node's value converges to it.

What makes this remarkable is that no node ever knows the average, how many nodes exist, or what the graph looks like. Purely local operations produce a global result.

Decentralized SGD is gossip plus gradients. Each node takes a local gradient step on its own data, then gossips with its neighbours, and repeats. Local progress and global mixing interleave, with no coordinator anywhere.

How fast does gossip mix? The answer is a single number from the graph, and it is the central quantity in this area.

The mixing matrix W has eigenvalues. The largest is exactly 1, corresponding to the consensus state where all nodes agree. Convergence speed is governed by the eigengap $\delta$: the separation between that top eigenvalue and the next largest in magnitude.

The interpretation is geometric. The second eigenvector describes the graph's most stubborn disagreement, typically a split into two weakly connected halves. A large gap means even that disagreement dies quickly. A small gap means information crosses the graph slowly.

Complete graph      every node talks to all   gap large, mixes in ~1 step
Expander / random   sparse but well-connected gap large, mixes fast
Grid                local neighbours only     gap moderate
Ring                two neighbours each       gap tiny, mixes very slowly

The practical lesson is that topology is a design parameter, not a given. Ring topologies are the classic trap: cheap per round, but information takes on the order of n steps to cross, so total time is worse. Expander graphs give near-complete-graph mixing at constant degree, which is usually the right choice.

The loop has two interleaved forces. Gradient steps pull each node toward its own data's optimum, and gossip pulls neighbours together. Convergence requires mixing to keep pace with divergence, which is exactly where the spectral gap enters the rate.

Removing the server does not remove the communication cost. Each round still ships a full model, and modern models are large.

The natural response is to send less: quantize the update to few bits, or sparsify by transmitting only the largest coordinates. Both work in centralised settings. Both are dangerous in decentralized ones, because gossip's correctness rests on exact averaging, and compression breaks the invariant that keeps the global average preserved. Naive compressed gossip can fail to reach consensus at all.

The fix came from Anastasia Koloskova, Sebastian Stich, and Martin Jaggi in "Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication", published at ICML 2019.

Their algorithms, CHOCO-GOSSIP and CHOCO-SGD, work by having each node maintain a replica of what its neighbours believe it holds, then transmit only a compressed correction to that replica. Errors introduced by compression are remembered and folded into later messages rather than lost.

The results are strong. CHOCO-SGD converges at a rate involving both the eigengap and a compression quality parameter, CHOCO-GOSSIP is described as the first gossip algorithm supporting arbitrary compressed messages while still converging linearly, and the reported communication reduction is at least two orders of magnitude.

The mechanism deserves unpacking, because it is a general and reusable idea.

Naive compression discards information. Send the top one percent of coordinates and the other ninety-nine percent of that update is gone permanently. Do this every round and systematic bias accumulates: coordinates that are individually small but consistently pointed the same way never get transmitted, even though their cumulative effect matters.

Error feedback keeps a memory instead. Each node tracks the difference between what it wanted to send and what it actually sent, and adds that residual to the next round's message.

round 1:  want to send u, send C(u), remember e = u - C(u)
round 2:  want to send v, send C(v + e), remember the new residual

A coordinate suppressed this round accumulates in the residual until it becomes large enough to survive compression, and then gets sent. Nothing is permanently lost; it is only delayed.

That is what converts compression from a source of bias into a source of latency, and latency is something convergence analysis can absorb. The same principle appears throughout communication-efficient optimisation.

The honest accounting, since decentralization is often oversold as strictly better.

Two gotchas matter in practice. First, decentralization does not eliminate the trust problem, it redistributes it: your neighbours see your updates, which is better than one party seeing everything, but it is not privacy, and the attacks from the previous lesson still apply.

Second, the topology penalty is real and often underestimated. A poorly connected graph can be slower in wall-clock terms than a centralised system, despite cheaper rounds, because information needs many hops to traverse the network.

The decision rule: choose decentralized when no party can legitimately act as coordinator, when the coordinator would saturate, or when no coordinator exists. Otherwise the centralised design is simpler and often faster.