📊 statistics

Random Walk Learning and the Pac-Man Attack

This paper introduces the "Pac-Man" attack, a stealthy adversarial strategy that terminates random walks in decentralized learning, and proposes the Average Crossing algorithm to counteract this threat by duplicating walks, thereby ensuring system stability and convergence while revealing a phase transition in extinction probability.

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

Published 2026-04-16

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, decentralized team of 100 people trying to solve a giant puzzle together. They don't have a boss or a central computer to tell them what to do. Instead, they use a game of "telephone" called a Random Walk.

Here's how it works: One person holds a "token" (the puzzle piece or a math problem). They pass it to a random neighbor, who does a tiny bit of work on it and passes it on. This token hops from person to person, gathering information until the whole team has solved the puzzle.

The Villain: The "Pac-Man" Attack

Now, imagine there is a spy in the group, let's call him Pac-Man.

Pac-Man isn't trying to steal the puzzle or shout wrong answers. He's much sneakier. His only job is to eat the token whenever it lands on his desk.

If the token hits Pac-Man, it vanishes.
The person holding the token thinks, "Oh no, I lost it!" and the whole chain stops.
Because Pac-Man only eats the token sometimes (maybe 50% of the time), he doesn't look suspicious. He still passes the token along the other times, so no one suspects him.

The Result: Over time, every single token gets eaten. The team runs out of tokens, the work stops, and the puzzle is never solved. This is the "Pac-Man Attack."

The Hero: The "Average Crossing" (AC) Algorithm

The researchers in this paper asked: How do we stop the tokens from disappearing without needing a boss to watch everyone?

They invented a clever, self-regulating rule called Average Crossing (AC). Here is the simple logic:

The Watchful Eye: Every person in the group keeps a mental note: "When was the last time I saw a token?"
The Alarm: If a person hasn't seen a token for a very long time (longer than a set threshold), they get suspicious. They think, "Hey, something is wrong. Maybe a token got eaten by Pac-Man."
The Backup Plan: When this alarm goes off, the person doesn't just wait. They clone the token that just arrived.
- Imagine a token arrives at your desk. You look at your watch, realize you haven't seen one in ages, and say, "Just in case, I'll make a photocopy of this token and send both of them out!"
The Safety Net: Now there are two tokens moving around. Even if Pac-Man eats one, the other one keeps going. If he eats that one too, the system eventually triggers another clone elsewhere.

Why This is Brilliant

The paper proves three main things using math and computer simulations:

It Doesn't Explode: You might worry, "If everyone keeps copying tokens, won't we end up with a billion tokens clogging the network?"
- The Answer: No. The math shows the number of tokens stays within a safe, manageable limit. It's like a thermostat: if there are too many, the system naturally slows down the copying.
The "Goldilocks" Threshold: There is a sweet spot for how long you wait before making a copy.
- If you wait too long (the threshold is too high), Pac-Man eats them all before you react.
- If you copy too often (the threshold is too low), you waste energy.
- The researchers found a "phase transition": a specific point where, if you set the timer correctly, the tokens survive forever. If you set it wrong, they die out.
The Team Still Wins: Even with Pac-Man eating some tokens, the remaining tokens still manage to solve the puzzle.
- The final answer might be slightly different from the perfect answer (because Pac-Man ate a few data points), but it's close enough to be useful. The system converges to a solution despite the sabotage.

The Big Picture

This paper is about resilience. In a world where we can't trust every node in a network (like in blockchain, sensor networks, or decentralized AI), we can't rely on a central authority to fix problems.

Instead, we give the network a simple, local instinct: "If things feel quiet for too long, make more noise." By duplicating the work only when necessary, the network can survive a stealthy enemy that tries to silently kill its progress.

In short: It's like a game of "Keep Away" where, instead of just one ball, the players instinctively create backup balls whenever the game gets too quiet, ensuring the game never stops, even if a thief tries to steal the ball.

1. Problem Statement

The paper addresses a critical vulnerability in decentralized learning systems that rely on Random Walk (RW) algorithms. While RW-based methods are popular for their low communication overhead and scalability, they are inherently fragile against specific adversarial threats.

The Threat: The authors introduce the "Pac-Man Attack," where a malicious node (the "Pac-Man") probabilistically terminates any RW that visits it.
- Stealthiness: Unlike traditional attacks that disrupt communication or inject noise, the Pac-Man node does not broadcast failure signals. It simply "eats" the token (the RW) with a probability $\zeta \in (0, 1]$ .
- Consequence: Even a single Pac-Man node can cause the almost sure extinction of all active RWs over time. Since RWs carry the global task (e.g., model updates in Stochastic Gradient Descent), their extinction halts the entire decentralized learning process.
Limitations of Existing Solutions:
- Static Redundancy: Simply starting with multiple RWs is insufficient; given enough time, a probabilistic adversary will eventually terminate all of them.
- Previous Work (DECAFORK): Recent self-regulating approaches rely on maintaining visit histories but often rely on idealized assumptions or approximations that may not hold in rigorous adversarial settings.

2. Methodology: The Average Crossing (AC) Algorithm

To counter the Pac-Man attack, the authors propose the Average Crossing (AC) algorithm, a fully decentralized mechanism that adaptively duplicates RWs based on local timing information.

Core Mechanism:
- Each benign node $u$ maintains a variable $L_t^{(u)}$ , representing the time of its most recent visit by any RW.
- The node calculates the time interval since the last visit: $\Delta t = t - L_t^{(u)}$ .
- Duplication Rule: If $\Delta t$ exceeds a predefined threshold $A_u$ , the node infers that an RW may have been killed by the Pac-Man. With a probability $q$ , the node duplicates the currently visiting RW, creating a new identical copy to ensure the population does not vanish.
Key Features:
- Decentralized: Decisions are made locally without global coordination.
- Adaptive: The duplication rate responds dynamically to the "silence" of the network, effectively detecting the presence of the adversary without explicit signaling.

3. Key Contributions & Theoretical Analysis

The paper provides a rigorous theoretical framework analyzing the evolution of the RW population under the AC algorithm.

A. Population Boundedness (Stability)

Theorem 1: The authors prove that under the AC algorithm, the number of active RWs ( $Z_t$ ) remains almost surely bounded over time.
Significance: This ensures the system does not suffer from "blowup" (uncontrolled exponential growth of RWs) while still preventing total extinction. The algorithm is stable regardless of the specific thresholds chosen by benign nodes.

B. Phase Transition in Extinction

Observation: The survival of the RW population depends critically on the duplication threshold $A$ .
Proposition 1 (Soft Phase Transition): Using a simplified variant called Weak AC (W-AC), the authors demonstrate a phase transition:
- If the threshold $A$ is too large, the duplication rate is too low to counter the Pac-Man, leading to almost sure extinction ( $Z_t \to 0$ ).
- If the threshold $A$ is appropriately small, the duplication rate is sufficient to sustain the population with positive probability.
Implication: There exists a critical threshold value below which the system can survive the attack indefinitely.

C. Convergence of Decentralized Learning (RW-SGD)

Theorem 2: The authors prove that Random Walk Stochastic Gradient Descent (RW-SGD) integrated with AC converges even in the presence of the Pac-Man.
Chain of RWs: Since individual RWs die, the analysis treats a "chain" of RWs (parent $\to$ child $\to$ grandchild) as a single effective RW.
Convergence Point: The algorithm converges to a minimizer $\tilde{x}^*$ of a surrogate objective function.
Bias Analysis (Proposition 2):
- The presence of the Pac-Man alters the stationary distribution of the RWs.
- The algorithm converges to a point $\tilde{x}^*$ that deviates from the true global optimum $x^*$ .
- The paper provides bounds on this deviation ( $\|\tilde{x}^* - x^*\|$ ), showing it is bounded and depends on the termination probability $\zeta$ and the spectral gap of the transition matrix.

4. Experimental Results

The authors validated their theory using synthetic data and the MNIST benchmark dataset across various graph topologies (Complete, Regular, Ring, Erdős–Rényi).

Boundedness & Persistence: Simulations confirmed that the RW population remains bounded and persists over long time horizons when the threshold $A$ is set correctly. A "soft phase transition" in extinction probability was observed as $A$ varied.
Convergence Performance:
- Loss Curves: RW-SGD with AC achieved effective convergence, significantly outperforming a single RW (which fails quickly) and showing comparable performance to the DECAFORK baseline.
- Accuracy: On MNIST, the AC algorithm achieved high testing accuracy (e.g., ~97% on i.i.d. data), nearly matching the performance of a system without an adversary.
- Comparison: AC-based SGD converged significantly faster than Gossip-Based SGD in the adversarial setting, highlighting the efficiency of the RW approach even under attack.

5. Significance and Impact

Robustness: This work provides the first rigorous theoretical guarantee that decentralized RW learning can survive a stealthy, probabilistic "kill" attack without centralized coordination.
Mechanism Design: The AC algorithm offers a practical, low-overhead solution for maintaining system resilience. It transforms a vulnerability (local silence) into a trigger for self-healing (duplication).
Theoretical Insight: The identification of the phase transition in extinction probability offers deep insight into the trade-off between network overhead (duplication frequency) and survival probability.
Practical Application: The results suggest that RW-based learning is a viable candidate for secure, large-scale decentralized systems (e.g., IoT, edge computing) where nodes may be compromised, provided adaptive duplication mechanisms are employed.

In summary, the paper successfully bridges the gap between the efficiency of Random Walk algorithms and the necessity of security in decentralized systems, proving that with the Average Crossing mechanism, these systems can be made resilient to the Pac-Man attack while maintaining convergence guarantees.