# Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks

arXiv: https://arxiv.org/abs/2601.07674 · HTML: https://mlsanity.com/paper/2601.07674/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 12 Jan 2026.

## Builds on (most cited first, 17 of 17)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity](https://mlsanity.com/paper/2012.14453/) (2020)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Straggler-Resilient Personalized Federated Learning](https://mlsanity.com/paper/2206.02078/) (2022)
- [Towards Straggler-Resilient Split Federated Learning: An Unbalanced Update Approach](https://mlsanity.com/paper/2510.21155/) (2025)
- [Robustness of Decentralised Learning to Nodes and Data Disruption](https://mlsanity.com/paper/2405.02377/) (2024)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [Random Walk Learning and the Pac-Man Attack](https://mlsanity.com/paper/2508.05663/) (2025)
- [Coupled-Space Attacks against Random-Walk-based Anomaly Detection](https://mlsanity.com/paper/2307.14387/) (2023)
- [Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs](https://mlsanity.com/paper/2407.11762/) (2024)
- [Packet Drop Attack Detection Techniques in Wireless Ad hoc Networks: A Review](https://mlsanity.com/paper/1410.2023/) (2014)

## Built on by (most cited first, 2 of 2)

- [RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks](https://mlsanity.com/paper/2609.00078/) (2026)
- [Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange](https://mlsanity.com/paper/2610.14716/) (2026)

## Abstract (arXiv)

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 CREATE-IF-LATE (CIL) algorithm, which is a fully decentralized, resilient mechanism that enables self-creating RWs and prevents RW extinction in the presence of Pac-Man. Our theoretical analysis shows that the CIL algorithm guarantees several desirable properties, such as (i) non-extinction of the RW population, (ii) almost sure boundedness of the RW population, and (iii) convergence of RW-based stochastic gradient descent even in the presence of Pac-Man with a quantifiable deviation from the true optimum. Moreover, the learning process experiences at most a linear time delay due to Pac-Man interruptions and RW regeneration. Our extensive empirical results on both synthetic and public benchmark datasets validate our theoretical findings.