Decentralized Learning via Random Walk with Jumps

Random walk (RW)-based algorithms are widely used in decentralized learning due to their low communication overhead and scalability. While most existing methods rely on a single token, multiple tokens can explore the network in parallel and exchange information upon meeting. However, the fundamental benefits of such meeting-triggered interactions remain unclear. In this work, we investigate multi-token RW learning under two information exchange policies: Average-Gradient and Average-Model, which average stochastic gradients and updated models, respectively, when tokens meet. We establish iteration complexity lower bounds for non-convex, convex, and strongly convex objectives on complete graphs, which apply to both exchange policies. Compared with single-token RW learning, the scaling factor in these bounds is reduced by a factor of $m^2$ for non-convex and convex objectives, and by an exponentially in $m$ for strongly convex objectives, where $m$ denotes the number of tokens. Numerical experiments reveal distinct behaviors of the two policies under two performance criteria: mean-token loss (the average loss across all tokens) and best-token loss (the minimum loss across all tokens). Average-Model achieves lower mean-token loss and is relatively insensitive to the network-to-token ratio $N/m$, where $N$ is the number of nodes. In contrast, Average-Gradient achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as $N/m$ decreases.

Decentralized learning is a promising paradigm for collaborative training in mobile and pervasive systems, as it avoids a central coordinator and does not require sharing raw data. Yet, most analyses rely on idealized communication assumptions that break down in wireless settings, where connectivity is intermittent, topology changes due to mobility, and bandwidth is limited. We study decentralized averaging under client asynchrony, time-varying contact graphs, and technology-dependent throughput constraints. We implement a fully decentralized protocol that overlaps synchronization with local training and supports partial tensor-level transfers when contacts end early. Using Random Waypoint mobility and multiple wireless technologies (Bluetooth LE, LTE, and Wi-Fi), we quantify how network dynamics and link capacity impact convergence. We identify three operating regimes: (i) inter-contact time largely dictates convergence via mixing, (ii) partial updates are often well tolerated when contacts are frequent, and (iii) very dense contact patterns can trigger contention, reducing effective throughput. These findings provide a practical lens to reason about decentralized learning deployments over realistic wireless systems, highlighting when improving connectivity, increasing bandwidth, or mitigating contention is most impactful.

Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.