In decentralized optimization, a network of machines jointly minimizes a sum of local losses by repeatedly mixing its parameters with those of its neighbors. Methods that tolerate slow or delayed links still need one number that no single machine can see: the worst message delay anywhere in the network. The step size is then shrunk in proportion to that bound. Every node pays for the most congested link in the system, and if the bound is guessed wrong the method can diverge. Recent parameter-free methods have removed the other hidden global constants, namely smoothness and the spectral gap (how fast information spreads across the graph). They did so by assuming messages arrive instantly.
This note proposes that the missing delay bound can be replaced by something every node already observes: the age of the freshest message it holds from each neighbor, meaning how long ago that message was generated. Two design choices make this work. The first is queueing. Model parameters are status updates, not goods to be consumed, so each link should keep only the newest message. A deeper buffer only makes messages older. Under this rule, age stays bounded by the gap between sends plus the in-flight delay, without any global tuning. The second is the step size. Each node scales its own locally chosen step by its observed neighbor ages, so nodes on fresh links move quickly and nodes behind congested hubs move cautiously. The claim to test is that this per-node, age-scaled step size beats the best hand-tuned fixed step size on networks where congestion is uneven or changes over time. It should match that step size when congestion is uniform.
Core Claim
Delay-tolerant decentralized methods such as DTAC-ADDOPT (Delay-Tolerant Augmented-Consensus-based Distributed Directed Optimization) prove linear convergence for strongly convex costs over directed graphs with bounded heterogeneous delays. Their step size, however, must be set from a global maximum delay $\bar{\tau}$ that agents know in advance. Parameter-free methods such as DATOS (Adaptive Decentralized Composite Optimization via Three-Operator Splitting; conference version A Parameter-free Decentralized Algorithm for Composite Convex Optimization) remove the need for global smoothness and spectral-gap constants by having each agent backtrack its step size against a local descent test. DATOS assumes delay-free, non-blocking channels.
The two lines are complementary, and neither covers the case that matters in practice: delays that arise from queues filling on shared links, so that their size depends on how much the algorithm itself transmits.
We define the age of node $j$'s information at node $i$ as $a_{ij}(t) = t - u_{ij}(t)$. Here $u_{ij}(t)$ is the generation time of the newest message from $j$ that $i$ holds at time $t$. The proposed step-size rule is
$$ \alpha_i(t) = \frac{\beta_i(t)}{1 + c \, \max_{j \in \mathcal{N}_i} a_{ij}(t)}, $$
where the symbols are as follows. $\beta_i(t)$ is node $i$'s step from a local backtracking test of the DATOS type. $\mathcal{N}_i$ is its set of neighbors, and $c$ is a scale-free constant shared by all nodes; we fix it by a theoretical argument rather than per instance. The form $1/(1+c\,\tau)$ mirrors the delay-step-size tradeoff in the DTAC-ADDOPT analysis. The difference is that the worst-case $\bar{\tau}$ is replaced by the age each node actually observes, measured at the time and place where it matters.
The theoretical target is linear convergence for strongly convex smooth-plus-composite objectives. Delays may be bounded but unknown, and the rate should depend on a time-average of realized ages rather than on $\bar{\tau}$. We regard this as a conjecture to be proved. The plan is a delay-augmented Lyapunov function that sums errors over each node's own age window, a standard device for delayed iterations.
Why Queueing Is Part of the Algorithm
The queueing theory in the file points in two opposite directions, and resolving the conflict is part of the contribution.
On one side, Huang and Modiano (Optimizing Age-of-Information in a Multi-class Queueing System) show that first-come-first-served queues suffer an "age blow-up" as the send rate rises. A one-slot queue that discards waiting updates avoids this. With such a queue, peak age splits into mean time between arrivals plus mean system delay. This is the motivating result: it says first-in-first-out buffering of neighbor models in asynchronous gossip is the wrong default.
On the other side, Huang and Neely (Utility Optimal Scheduling in Processing Networks) show that driving queues to zero starves processors that need several inputs at once. Their Perturbed Max-Weight scheduler therefore keeps a deliberate safety stock. The file raises this as an objection to dropping packets in consensus.
We argue the objection does not apply to model states, and the experiments check this. A node that overwrites its single slot per neighbor never runs out after the first delivery. It always holds some neighbor model, possibly an old one, and age measures exactly how old. Underflow arises only when messages are consumed.
That exception is real for one class of methods. Push-sum and gradient-tracking methods over directed graphs, including DTAC-ADDOPT's column-stochastic weights, send increments whose mass must be conserved, so dropping one corrupts the sum. For these methods we send running totals instead of increments. The receiver then keeps only the latest total, and overwriting loses nothing. This turns a consumed commodity back into a status update. It is a known style of construction, not a contribution here, but it is what lets one queueing rule serve both undirected (DATOS-style) and directed (DTAC-style) methods.
The sender keeps one slot per outgoing link as well. It transmits as fast as the link drains, and always sends its freshest state. This is where the throughput-delay tradeoff enters. Huang and Neely's frontier says a larger backlog buys higher link use at the cost of $O(V)$ queueing delay, where $V$ is the scheduler's weight on throughput. With one-slot queues on both ends, backlog cannot grow, so throughput beyond what keeps the slot full buys nothing for optimization. Dense virtual topologies still congest the shared medium. That congestion now appears as larger observed ages at specific nodes rather than as hidden, growing buffers, and the age-scaled step size responds to it.
Research Program
The work has three parts.
The first is analysis. We extend the DATOS convergence argument and the delay-augmented argument of DTAC-ADDOPT to time-varying, node-specific ages with an unknown bound. The aim is a rate expressed in realized ages. A second analytical question is whether the descent test can stay purely local. Ideally the backtracking test triggers no extra communication rounds, which would remove the circular effect where retried steps inject packets that raise age, which forces smaller steps and more retries. If an extra round turns out to be necessary, we will quantify the packets it adds.
The second part is a simulator that makes delay depend on the algorithm's own traffic. Links have finite rates and interface queues. Propagation delays come from the 87-node Ebone backbone and from the uniform $8{,}000 \times 8{,}000$ km geometric network used in Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning. On top of these we add a shared-medium contention model, so that a node with more neighbors fills its outgoing queue faster.
The third part is the algorithm itself. It is age-scaled local DATOS for undirected graphs, plus an age-scaled variant of DTAC-ADDOPT using running-total messages for directed graphs. Each comes with the two-ended one-slot queueing rule.
Topology enters as the setting where uneven ages arise. Exponential graphs improve the spectral gap, but the BTSP-MSR paper shows they create bottleneck links when mapped onto real networks. Rings suffer from large diameter and the performance collapse that Which mode is better for federated learning? Centralized or Decentralized reports as networks grow. Sparse topologies also widen the stability-based generalization bound under staleness (Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD). Our hypothesis is that the method's advantage grows with how much ages vary across nodes, which depends on both the topology and how it maps onto physical links.
Baselines
The naive reference point is asynchronous decentralized stochastic gradient descent, as analyzed by Deng et al., with first-in-first-out neighbor buffers and a fixed step size. The Deng et al. analysis predicts degraded stability on rings and stars under staleness. Huang and Modiano predict age blow-up as send rates rise. If our method does not clearly beat this reference, the problem is not worth the machinery.
The strongest existing method for delayed networks is DTAC-ADDOPT. To make the comparison fair, we deliberately give it an advantage: an oracle supplies the true $\bar{\tau}$ measured after the run. Its step size is then grid-searched over the same budget of eight values used for every fixed-step method, on the same data, graph, delay trace, and wall-clock budget. The file reports no accuracy or optimality-gap number for it. Its experiment used 16 agents, $\bar{\tau}=5$, and MNIST logistic regression, and states only that "final accuracy and stability … remain uncompromised." There is therefore no reported result found on Lacuna for DTAC-ADDOPT's optimality gap, and we will reproduce its setting first.
For the parameter-free line, we run local_DATOS over the congested simulator with first-in-first-out buffers, unchanged. No convergence figure under delay is reported; the file says only that DATOS beats manually tuned SONATA and PG-EXTRA and that local and global DATOS perform "almost identically" on delay-free Erdős–Rényi graphs. Again, there is no reported result found on Lacuna for DATOS under queueing delay.
As a topology-level competitor, we pair the best fixed-step method with a BTSP-MSR mapping of its exponential or ring graph onto Ebone. The paper reports roughly 23% lower bottleneck delay for rings and 6–16% for exponential graphs versus random assignment. This tests whether a good static mapping removes the need for adaptation.
Two ablations isolate the key ingredient. In the first, every baseline gets our one-slot overwrite queues, so any remaining gap is due to the step-size rule alone. In the second, we replace each node's local maximum age with a network-wide maximum age obtained by min-consensus, analogous to global_DATOS. This separates the benefit of using measured ages from the benefit of using local ones.
Beating the baselines means two things. Against the oracle-tuned DTAC-ADDOPT with overwrite queues, our method must reach a fixed optimality gap in less wall-clock time on high-dispersion settings. It must also be within noise of that baseline on uniform-delay settings, and do so with zero tuning.
Why not just…?
Why not just give the fixed-step method a good delay bound and tune it? On a static, uniform network this probably works as well as our method, and we predict exactly that. Under such conditions we expect parity, which is the honest null result. The threat breaks down when congestion is uneven or bursty. A single step size must then protect the worst node at its worst moment, which slows every fresh node all the time. The dispersion sweep and the burst experiment below test this directly, with the oracle bound given to the baseline.
Why not just fix the queues and leave the step size alone? This is the most serious alternative. Huang and Modiano's discarding result suggests the overwrite rule alone may remove most of the staleness. For this reason, the first ablation gives every baseline the same queues. If the age-scaled step size adds nothing once queues are fixed, the contribution reduces to queueing advice, and we would report it as such. Our expectation that it does add something rests on DTAC-ADDOPT's delay-step-size tradeoff: bounded age still requires a smaller step, and only the size of the bound is changed by the queue.
Why not just let local backtracking absorb the delay, as DATOS already backtracks? The descent test checks a node's own loss, and that loss cannot detect consensus error caused by mixing with an old neighbor model. Backtracking therefore has no reason to shrink the step when neighbor messages go stale. Running unmodified local_DATOS in the congested simulator shows whether it diverges, slows down, or copes. If it copes, that would itself be a new finding about DATOS.
Why not just send less, using random walks or triggered updates? Multi-Walk (A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip) cut traffic from about 600 GB to about 50 GB when fine-tuning OPT-125M. It loses to gossip on dense graphs with very uneven data, however, and it mixes all walks through a single node, which becomes a congestion point. Triggered updates cut traffic too, but either approach still leaves the receiver with stale models, and so still needs some way to set the step size. We include Multi-Walk on the ring and the Ebone settings as a traffic-efficiency reference. Sending less and scaling by age are compatible, so a positive result for Multi-Walk would not rule out ours.
Proposed Experiments
The convex core reuses the DATOS and DTAC-ADDOPT task: $\ell_1$-regularized logistic regression on MNIST. We run it with 16 agents to reproduce DTAC-ADDOPT and with 87 agents on Ebone. Topologies are Erdős–Rényi graphs with edge probability from 0.1 to 0.9 (the DATOS range), rings, and exponential graphs. Metrics are optimality gap against wall-clock time, total transmitted bytes, the distribution of per-node ages, and, for $\ell_1$, the time until the sparsity pattern is correctly identified. DATOS claims finite-time recovery of the sparsity pattern, and we test whether stale messages delay it.
The nonconvex check is CIFAR-10 with ResNet-18 on Dirichlet-partitioned data, measuring test accuracy against wall-clock time and the generalization gap across ring, star, and complete graphs, following Deng et al.
Three tests decide the question. The first is a dispersion sweep. We vary how unequally congestion falls across nodes, from a uniform channel to a single bottlenecked hub, and plot the wall-clock speedup over oracle-tuned DTAC-ADDOPT with overwrite queues. The hypothesis predicts near-zero speedup at uniform congestion and growing speedup with dispersion; a flat curve rejects it.
The second is a burst test. We inject temporary congestion on a few Ebone links. The prediction is that the tuned fixed-step method either diverges during bursts or must be tuned so conservatively that it is slower than our method overall, while ours shrinks steps only at the affected nodes.
The third is a feedback-loop test. We count the packets per iteration that backtracking adds and check whether age and step size reach a steady state rather than spiraling. Spiraling would be the circular dependency of retried steps raising age and forcing more retries. If it occurs, the step-size rule would need an explicit damping term, which would change the design.
References
- Delay-tolerant augmented-consensus-based distributed directed optimization
- Adaptive Decentralized Composite Optimization via Three-Operator Splitting
- A Parameter-free Decentralized Algorithm for Composite Convex Optimization
- Optimizing age-of-information in a multi-class queueing system
- Utility optimal scheduling in processing networks
- Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning
- Which mode is better for federated learning? Centralized or Decentralized
- Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD
- A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip