Drift-Independent Gossip Deadlines for Decentralized Low-Communication Training

Training runs spread across loosely connected machines, such as several small clusters joined by slow or unreliable links, cannot afford the exact averaging step that standard data-parallel training performs after every batch. The usual workaround is local training. Each replica takes many optimizer steps on its own and only occasionally reconciles its weights with the others. When the network cannot perform a clean global average, reconciliation happens by gossip: each machine repeatedly nudges its weights toward those of its neighbors. Gossip has a problem that sets the communication cost. The longer replicas trained alone, the further apart they are, and the more gossip rounds are needed before they agree. Communication cost therefore grows with drift, which is exactly the quantity local training tries to increase.

Control theory offers a tool built for this situation. A fixed-time stable system is a dynamical system guaranteed to reach its target within a time bound that does not depend on how far away it started. It achieves this by combining a strong pull when far from agreement with a pull that does not fade when close. We propose to turn this idea into a gossip protocol for the synchronization phase of decentralized local training, so that a fixed, pre-budgeted number of gossip rounds brings replicas to agreement regardless of how far they drifted. The work then tests, at language-model scale, whether this continuous-time guarantee survives discretization, weight-message quantization, and link failures well enough to beat the obvious linear alternatives. We take seriously the possibility that it does not, and design the experiments so that a negative answer is also informative.

Core Claim

In decentralized local training over an unreliable or time-varying graph, a gossip rule with a disagreement-dependent gain (far-branch exponent $\beta>1$, near-branch exponent $\alpha<1$, a stability cap, and a dead zone matched to the quantizer) makes the residual disagreement after a fixed budget of $R$ gossip rounds approximately flat as a function of how far replicas drifted. Linear gossip at the same bit and round budget leaves a residual that grows with drift. If this holds, the number of local steps $H$ can be increased without paying extra synchronization rounds. That is the lever for cutting communication.

We write the gossip update for replica $i$ on tensor block $b$ as

$$x_i^b \leftarrow x_i^b + \gamma \sum_{j \in N_t(i)} w_{ij}\, \min\!\Big(\frac{a}{\max(\|z_{ij}\|,\delta)^{1-\alpha}} + b\,\|z_{ij}\|^{\beta-1},\ c_{\max}\Big)\, z_{ij}, \qquad z_{ij} = Q(x_j^b) - x_i^b.$$

Here $N_t(i)$ is the set of neighbors reachable in round $t$, $w_{ij}$ are mixing weights, and $Q$ is the message quantizer. The positive constants $a$ and $b$ weight the near and far branches, with $0<\alpha<1<\beta$. The cap $c_{\max}$ is set so that $\gamma\, c_{\max} \sum_j w_{ij} \le 1$, which prevents overshoot. The dead zone $\delta$ is set to the quantizer's resolution, so the near branch never amplifies quantization noise into chattering. With $a=0$, $b=0$ and a constant gain, the rule reduces to linear gossip. With $b=0$ and $\delta=0$, it resembles the finite-time Nonlinear Gossiping rule.

Why this intersection, and what is already done

Three pieces of prior work motivate the proposal. Distributed Optimization in Fixed-Time and its extension to time-varying graphs, Fixed-time Distributed Optimization: Consistent Discretization, Time-Varying Topology and Non-Convex Functions, give a two-phase fixed-time scheme: first gradient estimation, then consensus. They prove that forward-Euler discretization reaches a small neighborhood of the optimum in a predictable number of steps. Their experiments stop at a 2.8M-parameter MNIST CNN on 3 servers, communicate once per epoch, and use no compression. Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping replaces linear averaging with a sublinear power-law coupling. It shows that residual disagreement ("decentralized lag") slows training and that nonlinear coupling helps on CIFAR-10 and TinyImageNet. Its settling time still grows with initial disagreement, because it has only the near branch. Our proposal differs from all three in three ways. It places the nonlinear consensus inside the outer synchronization of a local-training method rather than every step. It targets transformer pretraining. And it treats the discrete-time, quantized, lossy-link implementation as the object of study rather than an afterthought.

Two more lines of work supply methods we reuse. DiLoCo scaling laws provide the local-training template: $H=30$ inner steps, then an outer Nesterov step on the averaged pseudo-gradient. The same paper shows this scales to 10B parameters with 10x–100x less bandwidth. It assumes exact averaging, however, which is unavailable when links fail. SDP4Bit supplies the message quantizer: 4-bit quantization of weight differences with a Hadamard transform to suppress outliers. We use it identically for every gossip variant.

Two further sources constrain the design. The file's summary of fixed-time optimization notes that non-Lipschitz fractional terms and super-linear terms cause chattering and overflow under constant-step discretization. That is why the cap and dead zone are part of the rule rather than tuning details. Nonlinear Consensus for Distributed Optimization shows that the best nonlinear transform depends on the initial state. This warns that our exponents may need per-layer calibration.

Research Program

The first part is analytical, and it contains the proposal's central risk. On a single edge, any capped nonlinear gain is bounded by the maximal stable linear gain. So in discrete time, the fixed-time rule cannot beat a well-tuned linear step edge by edge. Any advantage must come from the graph. The state-dependent gain reweights edges toward those carrying large disagreement, and this redistribution can speed the slow modes that dominate linear gossip, especially when the topology changes between rounds. We will derive a discrete-time bound on the post-$R$-round disagreement for the capped, dead-zoned rule over a sequence of connected graphs. The goal is to identify when it is independent of initial drift up to the dead-zone floor. We will compare it with the linear bound, whose round count grows like $\log(D_0/\varepsilon)$ divided by the spectral gap, where $D_0$ is the initial disagreement and $\varepsilon$ the target residual; this logarithm is where linear gossip's drift dependence comes from.

The second part is a systems implementation. We build a decentralized DiLoCo in which the outer all-reduce is replaced by $R$ gossip rounds over a sparse graph (ring and 2D torus, 8–16 replicas). Links drop independently with probability $p_{\text{drop}} \in \{0, 0.1, 0.3\}$ per round, and an emulated per-link bandwidth budget applies. The update rule is applied per tensor block using block norms, so the cost is one norm per block per round and not per-coordinate power functions. This matters because Agarwal et al. show that expensive compression kernels can erase network savings. The third part is empirical, described below.

Baselines

The naive reference point is decentralized DiLoCo with standard linear gossip: constant mixing weights, the same $R$, the same 4-bit quantizer, and the same graph and link-drop process. This is what a practitioner would build first. It isolates exactly the change we make.

The strongest competitor on the question of whether nonlinearity matters at all is linear gossip with a tuned maximal stable gain. It gets the same hyperparameter-search budget as our rule (an equal number of trials over gain, $R$ and $H$). It is also allowed extra rounds so that bits per outer step are matched rather than rounds. If this baseline matches our rule, the fixed-time advantage is a continuous-time artifact, and we will report it as such.

The strongest existing nonlinear method is the finite-time Nonlinear Gossiping rule of Chen et al., run inside the same outer loop. On non-i.i.d. CIFAR-10 over a ring, that paper reports 34.14% test accuracy for nonlinear gossip versus 32.49% for linear gossip. We will reproduce this setting first as a sanity check before moving to language models.

For communication-reduction by gating, we include event-triggered broadcasting in the style of DETSGRAD. It reports a 44.1% communication reduction on 8-agent ring CIFAR-10 relative to distributed SGD, with no explicit accuracy scalar quoted. We run it with its trigger threshold tuned on the same budget.

As an upper reference, exact-average DiLoCo with all-reduce is run on the same graph with no link drops. Under drops it stalls, and we will report its wall-clock under drops honestly rather than excluding it.

Three ablations isolate the key ingredients. Removing the far branch ($b=0$) tests whether super-linear pull is what flattens the drift dependence. Removing the near branch ($a=0$) tests the tail. Removing the dead zone ($\delta=0$) tests whether quantization-matched thresholding is what prevents chattering.

For decentralized DiLoCo on C4 with lossy gossip, no reported result was found on Lacuna. Our own linear-gossip and exact-average runs therefore define the numbers to beat. Beating the baselines means two things. First, for a fixed validation-loss target, our rule tolerates at least twice the $H$ of tuned linear gossip at equal bits per outer step. Second, the slope of post-gossip disagreement against initial drift is statistically indistinguishable from zero above the dead-zone floor.

Why not just…?

Why not just use exact all-reduce, as DiLoCo does? On a static, reliable ring, bandwidth-optimal ring all-reduce computes the exact average in about $2(N-1)$ steps. There our proposal has nothing to add, and we say so. DiLoCo's own analysis already cuts the bandwidth for 405B-scale training from a 222 Gbit/s link to 3 Gbit/s (DiLoCo scaling laws). The case for gossip is the regime where one dropped or slow link stalls the whole collective. The $p_{\text{drop}}$ sweep measures this directly. If all-reduce with simple retries matches our wall-clock at $p_{\text{drop}}=0.1$, the useful regime is narrower than claimed.

Why not just run more rounds of linear gossip? This is the main threat. Linear gossip's drift dependence is only logarithmic, so a few extra rounds may close the gap. The bits-matched, tuned-gain linear baseline above is designed to settle this. The per-round disagreement curves against $D_0$ show whether the gap is a constant (fixable by rounds) or grows with drift.

Why not just shrink $H$ or tune DiLoCo's outer learning rate? Smaller $H$ means more synchronization rounds, which is the cost we are trying to cut. A stronger outer step does not reduce disagreement between replicas, because the outer step applies the averaged pseudo-gradient after the replicas have already been reconciled. We will nevertheless include an $H$ sweep for every method. Then any claimed gain appears as a shift of the loss-versus-communication frontier, not as a single tuned point.

Proposed Experiments

We start by replicating the non-i.i.d. CIFAR-10 ring setting from Chen et al. to confirm our implementations of linear and nonlinear gossip reproduce its gap. We then train 150M- and 1B-parameter decoder-only transformers on C4 in the DiLoCo configuration, with 8 and 16 replicas on ring and torus graphs, sweeping $H \in \{30, 100, 300\}$, $R \in \{2, 4, 8\}$ and $p_{\text{drop}}$. Every message is quantized to 4 bits in SDP4Bit style. The metrics are:

  • validation cross-entropy against total bits communicated and against emulated wall-clock;
  • post-gossip disagreement as a function of pre-gossip drift;
  • the frequency of oscillation (chattering) across gossip rounds.

The decisive check is the drift-dependence plot at matched bits. Our rule must show a flat residual while tuned linear gossip shows a rising one, and that flatness must translate into a larger usable $H$ at equal final loss. The dead-zone ablation must show chattering reappearing when $\delta=0$ under 4-bit messages. If tuned linear gossip matches on both, the program has still produced a clear answer: fixed-time consensus buys nothing for discrete, quantized, decentralized training beyond what a well-chosen linear gain gives. That result would redirect the fixed-time literature's claims about distributed learning.