# Random Walk Learning and the Pac-Man Attack

Source: [Random Walk Learning and the Pac-Man Attack](<https://www.sota2.com/research/paper/68fa7aaf1e209131cea849d0>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-07-08T05:00:20.838Z

Authors: Xingran Chen, Parimal Parag, Rohit Bhagat, Zonghong Liu, Salim El Rouayheb

Published: 2025-08-01T02:27:02.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Image Classification on MNIST i.i.d. partitioning (test)](<https://www.sota2.com/research/sota/image-classification-on-mnist-i-i-d-partitioning-test.md>): Image Classification; MNIST i.i.d. partitioning (test); Accuracy (Complete): 97.32.

- [Image Classification on MNIST non-i.i.d. partitioning Dirichlet alpha=0.5 Regular graph (test)](<https://www.sota2.com/research/sota/image-classification-on-mnist-non-i-i-d-partitioning-dirichlet-alpha-0-5-regular-graph-test.md>): Image Classification; MNIST non-i.i.d. partitioning Dirichlet alpha=0.5 Regular graph (test); Accuracy: 96.11.

- [Image Classification on MNIST non-i.i.d. Dirichlet alpha=0.5 Ring graph (test)](<https://www.sota2.com/research/sota/image-classification-on-mnist-non-i-i-d-dirichlet-alpha-0-5-ring-graph-test.md>): Image Classification; MNIST non-i.i.d. partitioning, Dirichlet alpha=0.5, Ring graph (test); Accuracy: 96.17.

- [Image Classification on MNIST non-i.i.d. Dirichlet alpha=0.5 (Complete Graph)](<https://www.sota2.com/research/sota/image-classification-on-mnist-non-i-i-d-dirichlet-alpha-0-5-complete-graph.md>): Image Classification; MNIST non-i.i.d. partitioning, Dirichlet alpha=0.5, Complete graph (test); Accuracy: 96.13.

- [Image Classification on MNIST non-i.i.d. partitioning, Dirichlet alpha=0.5, Erdős–Rényi graph (test)](<https://www.sota2.com/research/sota/image-classification-on-mnist-non-i-i-d-partitioning-dirichlet-alpha-0-5-erd-s-r-nyi-graph-test.md>): Image Classification; MNIST non-i.i.d. partitioning, Dirichlet alpha=0.5, Erdős–Rényi graph (test); Accuracy: 95.96.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2508.05663>)

[PDF](<https://arxiv.org/pdf/2508.05663.pdf>)
