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

arXiv:2601.07674 · cs.MA, cs.LG · Submitted 2026-01-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks".

Tom: The gist Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks proposes the CREATE-IF-LATE (CIL) algorithm to maintain the resilience of random walk algorithms against stealthy termination attacks by enabling…

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So, we're diving into this paper now. It’s titled "Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks." The authors are Xingran Chen, Parimal Parag, Rohit Bhagat, Salim El Rouayheb. They're tackling a problem where random walk algorithms in decentralized learning get shut down by something called a Pac-Man attack.

Jane: That sounds intense. Pac-Man attacks are basically malicious nodes that pick any random walk and terminate it with some probability every time they visit it, without the neighbors even noticing <ref:2601.07674#pg2>.

Lu: It's about how these algorithms can stay alive without needing some global coordination or parameter estimation, which is usually a big deal in decentralized systems.

Meng: So we're talking about keeping learning going when someone actively tries to stop the process completely <ref:2601.07674#pg3>.

Lalam: It seems like the focus is on building resilience right into the mechanism itself, rather than just patching it up later.

The paper's summary: Tom: Okay, so they propose an algorithm called CREATE-IF-LATE, or CIL. This is supposed to be a fully decentralized way to stop those termination attacks by letting the random walks create themselves again <ref:2601.07674#pg2>.

Jane: So instead of just getting stuck when a walk stops, each benign node looks at how long it’s been since the last visit to any walk <ref:2601.07674#pg2>.

Lu: If that time interval passes a certain threshold, the node guesses that some walk might have been terminated and then it probabilistically creates a new random walk by copying the one it most recently saw <ref:2601.07674#pg2>.

Meng: That’s interesting because it's all based on local timing information, not some central controller telling everyone when to start a new walk <ref:2601.07674#pg2>.

Lalam: It’s about using the past behavior of the system—the timing of visits—to predict and proactively counter the attack by self-generating activity <ref:2601.07674#pg2>.

Tom: Exactly, it’s a local trigger for creation that makes the walks resilient against those stealthy termination behaviors <ref:2601.07674#pg1>.

Jane: So the main idea is that this local, timing-based mechanism allows for resilient RW creation in a fully decentralized manner <ref:2601.07674#pg2>.

The paper's improvements: Tom: The theoretical analysis shows some really strong guarantees here. They prove that CIL ensures non-extinction of the random walk population, which means it won't just vanish <ref:2601.07674#pg1>.

Jane: And they show it stays almost surely bounded, meaning the total number of walks doesn't explode to infinity <ref:2601.07674#pg3>.

Lu: They also link the RW population process to classical branching processes like the Galton-Watson process, but they point out that the standard assumptions for those models don't really apply in this setting <ref:2601.07674#pg2>.

Meng: So they’re saying the standard mathematical tools we use for modeling these systems aren't perfectly fitting here, which is a key finding <ref:2601.07674#pg2>.

Lalam: And because of this, they show that RW-SGD converges even when there's an adversary present, meaning it finds some kind of solution even with the attack happening <ref:2601.07674#pg3>.

Tom: That convergence means that even if the Pac-Man is messing things up, the learning process doesn't just crash or get stuck forever <ref:2601.07674#pg3>.

Jane: It also characterizes the error between this skewed optimizer and the true optimizer, which gives us insight into how good our approximation actually is <ref:2601.07674#pg3>.

Conclusion: Tom: So to wrap up, CIL is a decentralized duplication mechanism that only needs local timing info to stay resilient against Pac-Man attacks <ref:2601.07674#pg2>. It solves the problem of permanent extinction for RW-based SGD under termination attacks.

Jane: The paper establishes that this approach guarantees long-term survivability of the walk population and prevents it from dying out permanently under a Pac-Man node present <ref:2601.07674#pg3>.

Lu: It’s a robust solution because it doesn't rely on guessing system parameters or needing global coordination for its operation <ref:2601.07674#pg2>.

Meng: From an engineering standpoint, the analysis shows we can select parameters to keep the expected peak population below any level you set, which helps us manage resource usage <ref:2601.07674#pg3>.

Lalam: It really shifts how we think about adversarial environments in distributed learning because it shows how local decisions can lead to global stability against these kinds of attacks <ref:2601.07674#pg2>.

Tom: It’s a solid piece of work on Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks. We've got some big implications here about making distributed learning more robust.

Singapore University of Technology and Design · Rutgers University

cs.MA, cs.LG

Submitted: 2026-01-12

Updated: 2026-10-12

Comments: arXiv admin note: substantial text overlap with arXiv:2508.05663

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks proposes the CREATE-IF-LATE (CIL) algorithm to maintain the resilience of random walk algorithms against stealthy

Key concepts

CREATE-IF-LATE (CIL) Algorithm: A fully decentralized mechanism where nodes independently decide to create a new random walk based only on local timing. If the time since the last visit to any walk exceeds a threshold, the node probabilistically replicates the most recent walk, effectively 'creating' a new one to prevent termination.
Pac-Man Attacks: A type of adversarial attack in decentralized learning where malicious nodes attempt to cause random walk algorithms to terminate prematurely. The CIL algorithm is specifically designed to counteract these attacks by ensuring the random walk population survives even when such hostile nodes are present.
Random Walk (RW) Population: The set of active random walks distributed across the network. The paper analyzes how this population behaves under attack, proving that CIL maintains its non-extinction and almost sure boundedness, meaning the number of walks stays manageable over time.
RW-SGD Convergence: Stochastic Gradient Descent performed using random walks as a mechanism. The analysis shows that even when facing an adversary, this method still converges to a 'biased optimum,' characterizing the error between this skewed result and the true optimal solution.

Terminology

Decentralized Learning — 2× in this paper · explained in 2 episodes
Benchmark — 1× in this paper · explained in 2 episodes

Summary

The gist Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks proposes the CREATE-IF-LATE (CIL) algorithm to maintain the resilience of random walk algorithms against stealthy termination attacks by enabling self-creation.

How it works

The CIL algorithm is a fully decentralized mechanism that is resilient to terminationbased Pac-Man attacks by enabling the self-creation of RWs and preventing RW extinction under such attacks. Each benign node independently decides whether to create a new RW using only local timing information, namely the time elapsed since the last visit of any RW. If this interval exceeds a predetermined threshold, the node infers a possible RW termination and probabilistically creates a new RW by replicating the most recently visited one. This locally triggered mechanism enables resilient RW creation in a fully decentralized manner.

Key Theoretical Guarantees

The 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. Specifically, CIL guarantees long-term survivability of the RW population and prevents permanent extinction. The algorithm ensures that the RW population size remains bounded with probability one under a Pac-Man node present. Furthermore, CIL guarantees that RW-SGD converges even in the presence of an adversary.

Analysis of Population Dynamics and Convergence

The analysis shows that the RW population under CIL is almost surely bounded (Theorem 1) and provides a theoretical regime for selecting the algorithm parameter such that the expected peak population stays below any prescribed level (Theorem 2). The convergence of RW-SGD is shown to hold under the CIL mechanism, meaning it converges to a biased optimum, and it characterizes the error between this skewed optimizer and the true optimizer. The effective transition probability matrix P(ζ)chain depends explicitly on the termination probability ζ.

Empirical Validation

Extensive empirical results on both synthetic and public benchmark datasets validate our theoretical findings. Simulations demonstrate that CIL outperforms baseline algorithms like DECAFORK in terms of robustness against permanent extinction, regardless of the creation threshold A. The performance comparison shows that CIL achieves faster convergence under the same level of communication overhead compared to gossip-based SGD.

Scalability and Trade-offs

The algorithm's design directly affects resource consumption, such as communication cost. When the creation threshold A is large or the creation probability q is small, new RWs are created less frequently, which reduces resource consumption but requires a longer time to complete computational tasks. Conversely, when the creation threshold A is small or the creation probability q is large, new RWs are created more frequently, resulting in faster task completion at the expense of higher communication cost. The paper also provides a practical rule for selecting the creation probability q according to the desired RW population scaling.

Conclusion

The proposed CIL algorithm is a fully decentralized duplication mechanism based solely on local visitation intervals and hence does not need to depend on system parameter estimation. The CIL mechanism improves the resilience of RW-based SGD under termination-based Pac-Man attacks. Extensive experiments on synthetic and public benchmark datasets validate our findings. The paper suggests that while a rigorous adaptive selection rule for A is an open problem, the CIL algorithm provides a robust solution to this threat. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism. The paper also explores extensions to multiple Pac-Man nodes and general connected graphs. The work establishes that the RW-SGD converges to a surrogate optimization problem under the CIL mechanism<ref:

Improvements for AI systems

A fully decentralized learning system can be built that maintains long-term resilience against Pac-Man attacks without relying on system parameter estimation or global coordination. This allows for operational computational tasks to continue even in an adversarial environment and do not depend on an accurate estimation of the number of alive RWs, specifically by utilizing the CREATE-IF-LATE (CIL) algorithm.
The AI system can be designed to ensure no permanent extinction of its active learning population, as CIL guarantees that the RW population process bears resemblance to classical branching processes, such as the Galton-Watson process [22], but the standard assumptions underlying these models do not hold in our setting. This prevents the complete halting of the learning process caused by a malicious node.
The system can be optimized to maintain stability by ensuring no blowup, with CIL guaranteeing that the RW population remains bounded almost surely (Theorem 1). Furthermore, under specific parameters, such as when the creation thresholds satisfy Au = 1 for all u ∈ B, the expected peak population is bounded by a function of network size and parameters, providing a way to control growth.
The AI's learning process can be proven to converge even in the presence of an adversary by integrating CIL with RW-SGD, where RW-SGD converges under the CIL mechanism, even in the presence of an adversary (Theorem 3). The resulting limit point is characterized as a surrogate optimization problem where convergence is guaranteed to a minimizer of a modified objective function.
The system can utilize real-time performance monitoring to dynamically adjust its learning rate or communication strategy, leveraging the findings that a smaller threshold A or a larger q leads to more aggressive regeneration, which increases the fraction of time slots used for learning but also increases the communication cost. This allows for a tradeoff between convergence speed and communication overhead.

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 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.