Pac-Man Attack Silently Kills Decentralized AI Training and AC Fights Back
A stealthy adversary can silently kill random walks and halt decentralized training. A new duplication rule keeps the network alive.
Takeaways
- The Pac-Man attack is a stealthy adversary that probabilistically kills random walks in decentralized learning networks.
- Even one malicious node causes every walk to eventually die with probability one, halting training silently.
- Average Crossing lets each benign node fork a walk when the gap since the last visit exceeds a threshold.
- The authors prove bounded walk population, a phase transition in extinction, and RW-SGD convergence under attack.
- Experiments on MNIST and synthetic regression match DeCaFork in loss curves but with simpler local logic.
- Accepted to IEEE ISIT 2026; no public code release accompanies the paper.
Decentralized learning likes random walks because they are cheap: a single token hops from node to node, carrying gradients across the graph without every peer broadcasting to every neighbor. That efficiency is also the weak spot. If a malicious node quietly kills tokens as they pass through, the whole learning process winds down without any alarm going off. A new paper accepted to IEEE ISIT 2026 formalizes this threat as the Pac-Man attack and proposes a fully decentralized defense called Average Crossing (AC).
A network killer that hides in plain sight
The attack is deliberately unglamorous. A malicious node probabilistically terminates any random walk that visits it, gradually eliminating active walks from the network and halting learning without triggering failure alarms. Because the Pac-Man node still responds to retransmissions and timeouts, standard fault-tolerance checks see nothing wrong.
Launching many walks at once does not save you. For any positive kill probability, every walk is eventually absorbed with probability one, so static redundancy just delays the extinction. The authors prove this and use it to motivate a mechanism that keeps regenerating walks based on what nodes actually observe locally.
Duplicate when the silence gets too long
Average Crossing is essentially a suspicion timer running at every benign node. Each node u tracks L_t, the last time it was visited by any walk. If the gap since that last visit exceeds a threshold