In decentralized machine learning, a network of agents collaboratively trains a model without relying on a central server. Early frameworks, such as the Consensus-based Distributed SGD (CDSGD) introduced by Jiang et al. or the communication-efficient algorithms proposed by Kovalev et al., operate under a foundational assumption: the communication network is static, undirected, and reliably connected.
However, this static assumption collapses in real-world deployments like mobile robotics, edge computing, and autonomous vehicle swarms. As highlighted by Tolstaya et al. and Zhou et al., physical proximity changes, communication links fluctuate, and channels are often inherently directed or one-way. When nodes frequently join or leave the network—a phenomenon known as node churn—traditional consensus mechanisms fail to converge.
To build decentralized systems capable of learning in fluid environments, we must understand why dynamic topologies break standard optimization algorithms, and how modern frameworks overcome these challenges.
Why Dynamic Topologies Break Standard Consensus
At the heart of standard decentralized optimization is the consensus step. To ensure all agents eventually agree on the same model parameters, each agent updates its local parameter vector $x_i$ by taking a weighted average of its neighbors' parameters:
$$x_i^{t+1} = \sum_{j} W_{ij} x_j^t$$
For this averaging process to converge to the true global average, the mixing matrix $W$ must be doubly stochastic. This means two things must be true simultaneously:
- Row Stochasticity ($\sum_j W_{ij} = 1$): Each agent computes a valid weighted average of the incoming information from its neighbors.
- Column Stochasticity ($\sum_i W_{ij} = 1$): The total "mass" or influence of any single agent's parameters is preserved across the network. No agent's data is arbitrarily amplified or diluted.
In a static, undirected graph, constructing a doubly stochastic matrix is straightforward. But as Xi et al. and Di Lorenzo et al. point out, doing so over directed or time-varying graphs requires global coordination and continuous re-balancing.
If the network topology changes at every time step, an agent cannot know its out-degree (how many neighbors are receiving its message) in advance. Consequently, the matrix $W$ can easily be made row-stochastic, but it will fail to be column-stochastic. Information from highly connected "hub" nodes will disproportionately dominate the network, while rare information from poorly connected edge nodes will be diluted, as observed by Valerio et al..
The Push-Sum Protocol: Restoring Balance to Asymmetric Graphs
To circumvent the impossibility of maintaining doubly stochastic weights in dynamic environments, researchers rely on a mechanism known as Push-Sum or Subgradient-Push. Developed by Nedic et al. and extended to stochastic optimization in Nedic et al., this approach decouples the consensus mechanism from the requirement of column-stochasticity.
Instead of tracking just the parameter vector $x_i$, each node maintains an auxiliary scalar variable $y_i$, which represents the virtual "mass" or influence weight of that node. The protocol proceeds as follows:
- Push: Each node updates its parameters and its mass using a purely row-stochastic matrix (which only requires knowing who you are receiving data from), and "pushes" both values to its neighbors.
- Sum: Neighbors sum the incoming parameters and the incoming mass independently.
- De-bias: The actual model estimate used for the local gradient step is computed as the ratio:
$$\hat{x}_i^{t+1} = \frac{x_i^{t+1}}{y_i^{t+1}}$$
Why does this work? Because both the parameter vector $x_i$ and the mass $y_i$ accumulate the exact same topological distortions as they flow through the time-varying directed graph. By taking their ratio, the structural imbalances of the network cancel out mathematically. This allows agents to achieve exact consensus on the true average, even over highly asymmetric, changing topologies.
Gradient Tracking: Taming Drift in Fluid Networks
While Push-Sum solves the consensus problem for asymmetric graphs, a second failure mode emerges when data is heterogeneous (non-IID) across devices. When the network topology changes, agents can become temporarily isolated or clustered into local subnets.
As Chen et al. demonstrate, this causes subnet drift: isolated groups of nodes optimize solely for their local data distributions, causing their model parameters to drift rapidly away from the global optimum. Standard decentralized SGD cannot correct for this drift quickly enough when links are transient.
The solution is Gradient Tracking, a mechanism integrated into non-convex learning frameworks like GT-STORM by Zhang et al.. Gradient tracking introduces a second consensus loop that runs parallel to the parameter consensus loop. Instead of averaging parameters alone, agents maintain and average an auxiliary vector that tracks the global average gradient.
By communicating changes in local gradients and mixing them across time-varying edges, the tracker provides each node with an estimate of the global optimization direction. Even if a node's local connectivity drops or shifts, its gradient tracker retains memory of the broader network's objective, effectively taming client drift across volatile topologies.
B-Connectivity: The Speed Limit of Information Diffusion
If a network graph can change completely at every iteration, how can we mathematically guarantee that it will ever converge? The answer lies in relaxing the definition of connectivity.
Traditional optimization requires the graph to be connected at every single iteration $t$. In a unified theory of decentralized SGD, Koloskova et al. relaxed this constraint by utilizing the concept of $B$-connectivity. A time-varying network is said to be $B$-connected if the union of the graphs over a finite window of time steps $[t, t+B]$ is connected.
Iteration t: (A) (B)---(C) (Disconnected)
Iteration t+1: (A)---(B) (C) (Disconnected)
-------------------------------------------------
Union [t, t+1]: (A)---(B)---(C) (Connected!)
This insight changes the theoretical landscape. It implies that information does not need to diffuse across the entire network instantaneously. As long as there is a bounded time window $B$ within which every node can eventually influence every other node, the consensus and gradient tracking mechanisms will successfully drive the system to a global optimum.
By establishing these theoretical boundaries, Yuan et al. determined the exact communication and computation complexity lower bounds—the theoretical "speed limit"—for non-convex learning over time-varying graphs. This ensures that modern decentralized architectures remain robust, predictable, and scalable, even when the underlying communication infrastructure is completely in flux.