CS Paper Radar

Toward a decentralized design framework for discrete-time distributed algorithms via their emergent dynamics

Jinwook Heo, Hyungbo Shim, Jin Gyu Lee

eess.SY ·submitted 2026-10-21 12:36 UTC · v1

Abstract

This paper develops a procedure for designing discrete-time distributed algorithms to achieve a desired collective behavior. Each agent combines its node and coupling updates at every iteration, in either explicit or implicit form. For this structure, we derive necessary and sufficient conditions on the local parameters for realizing a desired continuous-time blended dynamics. These conditions yield a decentralized procedure for computing the parameters. A Tikhonov-type approximation result relates the resulting agent trajectories to the blended dynamics on a rescaled time axis. Under a stability condition imposed only on the blended dynamics, we further establish uniform-in-time approximation bounds. We also characterize the trade-off between approximation accuracy and the iteration count guaranteed by these bounds. The framework is illustrated through four applications in distributed computation and estimation.

Closest papers

Nearest neighbours by meaning across the whole index.

Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information

cs.DC math.OCcs.MAcs.NI+1 ·2026-09-23 ·Adrian Redder, Arunselvan Ramaswamy, Holger Karl
similarity 0.63
Abstract

Algorithms in multi-agent systems such as federated learning, mobile robotic swarming, and consensus control can be designed and analyzed as distributed stochastic approximation algorithms. Such algorithms involve information exchanges between agents for various computations. The freshness of the information can be quantified using the Age of Information (AoI) metric. Consider robotic teams operating in highly obstructed geographical settings, such as subterranean or dense urban environments. Because of spatial disconnections, AoI has empirically been observed to be heavy-tailed with unbounded moments. However, most analyses assume AoI with bounded moments, creating a gap between theory and practice. To the best of our knowledge, ours is the first analysis under general heavy-tailed AoI with potentially infinite mean. We study the stability (almost sure boundedness of the distributed iterates) and convergence of multi-agent systems that are strictly dissipative in the scaling limit (system at ``infinity''). Examples include most gradient-based and consensus algorithms under the Robbins-Monro step-size regime.

0.20

Budget-Constrained Multi-Consensus Decentralized Gradient Descent

eess.SY math.OC ·2026-10-06 ·Shuyi Ren, Nicol`o Michelusi, Erik G. Larsson
hot direction similarity 0.61
Abstract

We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. As a first step toward the broader communication-computation allocation problem, we consider and analyze a \textit{multi-consensus decentralized gradient descent} (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled consensus-allocation strategy under resource constraints, for which we show that equal allocation of consensus rounds across iterations is optimal under our stepsize rule, up to integer rounding. Numerical experiments corroborate the theoretical findings and demonstrate favorable communication-computation tradeoffs compared with existing multi-consensus decentralized optimization baselines.

0.30

Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective

eess.SY cs.ITmath.OC ·2026-09-23 ·Yuhang Deng, Zheng Chen, Erik G. Larsson
publishedtheory similarity 0.61
Abstract · 8 pages, 2 figures. Accepted to the 2026 IEEE 65th Conference on Decision and Control (CDC 2026)

We study the distributed average consensus problem under persistent link-level disturbances modeled as a martingale difference sequence with uniformly bounded conditional second moments. Under such disturbances, the standard stochastic-approximation-based linear iteration with diminishing stepsizes drives the network to consensus on an unbiased random variable with non-vanishing variance instead of the exact initial average. To understand and resolve this limitation, we develop an anchoring-based mechanism derived from a decentralized gradient descent formulation and study the effect of incorporating a decaying anchoring term that continuously pulls each agent state toward its initial value. This perspective provides an intuitive interpretation of how state anchoring counteracts disturbance accumulation. Under standard summability conditions, we prove that the resulting algorithm achieves exact average consensus almost surely. Furthermore, this decentralized gradient perspective offers a unifying framework for several related methods and an interpretable design principle for exact average consensus under persistent disturbances.

0.54

Skywing: A Platform for Decentralized Mathematical Computing in Unreliable Environments

cs.DC ·2026-09-02 ·Alyson Fox, Colin Ponce, Annika Mauro, Wayne Mitchell, Sarah Osborn +2 more
code/data similarity 0.58
Abstract

Emerging edge, autonomous, and cyber-physical systems increasingly require mathematical computation across heterogeneous devices connected by unreliable communication networks. Traditional high-performance computing and distributed data-processing frameworks provide powerful abstractions for managed environments but are less suited to decentralized settings where centralized coordination, reliable communication, and global synchronization cannot be assumed. This paper presents Skywing, an open-source platform for decentralized mathematical computing in unreliable environments. Its programming model consists of three abstractions: agents represent participants in a decentralized computation, processors encapsulate algorithm-specific update rules, and iterations manage distributed execution. Skywing supports asynchronous operation, publish-subscribe communication, managed message handling, and the composition of independent algorithms into complex decentralized workflows. We demonstrate Skywing using representative algorithms from consensus, optimization, and numerical linear algebra. Experiments on the native Skywing runtime include Push Sum and Max Consensus, a composed monitoring and control workflow, resilient Push Sum under delayed communication, and resilient asynchronous Jacobi under malevolent data corruption. These demonstrations show that Skywing supports diverse decentralized algorithms while separating mathematical logic from communication and execution infrastructure. Skywing serves as both a deployment framework for decentralized applications and a research platform for developing resilient mathematical algorithms.

0.39

Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

eess.SP cs.AIcs.LGeess.SY+1 ·2026-08-10 ·Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson
similarity 0.58
Abstract

Optimization theory is a widely used tool for intelligent decision-making. While classical optimization deals with fixed, time-invariant objective functions, many modern applications operate in dynamic environments where data arrive sequentially, and the learning objective evolves over time, often under decentralized data and communication constraints. Motivated by these trends, we study decentralized optimization from streaming data through a structured time-varying formulation in which the global objective is a temporally weighted average of losses observed across the network. We analyze multi-iteration decentralized first-order methods, including decentralized gradient descent. For strongly convex and smooth losses, we develop guarantees for the Euclidean-norm \emph{tracking error} through a contraction-mapping viewpoint. The resulting bounds decompose the tracking error into a fixed-point tracking component and a bias term induced by decentralization and data heterogeneity. We specialize our analysis to uniform and exponentially discounted weights, as well as their finite-memory \emph{windowed} counterparts. The bounds explicitly characterize the roles of the temporal weighting rule, per-step iteration budget, step size, and network connectivity. Uniform weighting yields a vanishing fixed-point tracking contribution of order $\mathcal O(1/t)$, whereas discounted and windowed strategies generally induce non-vanishing tracking floors governed by the discount factor and effective memory, respectively. In all cases, decentralization induces an additional non-zero bias floor under a constant step size. Numerical experiments illustrate the predicted trends.

0.04

Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis

cs.DC math.OCeess.SY ·2026-08-17 ·Sulaiman A. Alghunaim
similarity 0.58
Abstract

We study decentralized stochastic gradient tracking over a time-varying network of $N$ agents under a uniform window-mixing condition. Products of $τ$ consecutive doubly stochastic mixing matrices contract disagreement by a factor $λ<1$, although individual matrices need not contract disagreement strictly and individual communication graphs may be disconnected. We construct a time-varying quadratic norm that turns this window contraction into an exact one-step Lyapunov identity. This leads to coupled one-step recursions for the centroid and disagreement errors, without unrolling the dynamics over communication windows. For smooth strongly convex objectives, the leading stochastic term is $\widetilde{\mathcal O}(1/(NK))$; for smooth convex objectives, it is $\mathcal O(1/\sqrt{NK})$. Both match their centralized mini-batch counterparts and yield linear speedup after a network-dependent transient.

0.39

Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus

cs.AI math.OCcs.GTcs.LG+1 ·2026-09-07 ·Shao-An Yin
published similarity 0.58
Abstract · 6 pages, 1 figure. Accepted to CDC 2026

Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.

0.31

Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction

eess.SY math.OC ·2026-10-30 ·Silan Zhang, Yujie Tang
similarity 0.58
Abstract

We study decentralized composite finite-sum optimization over a fixed connected undirected network, where agents access local component functions through function evaluations and share a possibly nonsmooth convex regularizer. In this setting, standard two-point gradient estimators can retain nonvanishing variance at a solution, complicating their integration with gradient tracking. We propose Distributed Zeroth-Order Incremental Variance Reduction (Distributed ZIVR), which combines incrementally updated component-gradient estimates with a proximal gradient-tracking scheme. The method admits an implementation using a constant number of function evaluations per agent at every iteration, without intermittent full-component or full-coordinate refreshes. For convex smooth component functions and strongly convex local averages, we establish linear convergence up to a controllable finite-difference error. With the finite-difference radius chosen for the target accuracy, Chebyshev-accelerated mixing yields a per-agent oracle complexity of $\widetilde{O}(d(m+κ)\log(1/ε))$ for expected squared solution error $ε$, where $d$ is the dimension, $m$ is the number of components per agent, and $κ$ is the condition number. This matches the centralized ZIVR oracle bound, while the communication bound has only an inverse square-root dependence on the network spectral gap. Experiments on logistic and robust regression demonstrate rapid reduction of solution and consensus errors.

0.13