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

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

Problem Formulation
The paper addresses the vulnerability of Random Walk (RW)-based decentralized learning algorithms to a specific class of stealthy attacks termed the "Pac-Man attack." In standard RW-based algorithms (e.g., RW-SGD), tokens traverse a network graph to perform local updates and aggregate global information. The authors identify a threat where a malicious node (the "Pac-Man") probabilistically terminates any RW that visits it without performing the required computation or forwarding the token. Unlike traditional Byzantine or poisoning attacks, the Pac-Man node mimics benign behavior in other respects (e.g., responding to fault-tolerance checks), making it difficult to detect via conventional means.

The core problem is that even a single Pac-Man node, by terminating RWs with a positive probability $\zeta \in (0, 1]$, can eventually cause the extinction of all active RWs in the network with probability one. This halts the learning process entirely without triggering explicit failure alarms. Existing redundancy-based approaches (e.g., starting with multiple RWs) fail because static redundancy cannot prevent eventual extinction in the presence of a persistent termination adversary. Furthermore, existing self-regulation mechanisms like DECAFORK and AC, which rely on estimating population size or visit intervals to trigger duplication, are shown to be sensitive to parameter choices and can still suffer permanent extinction under this attack model.

Methodology: The CREATE-IF-LATE (CIL) Algorithm
To counter the Pac-Man attack, the authors propose CREATE-IF-LATE (CIL), a fully decentralized mechanism that ensures the long-term survival of the RW population without requiring global coordination or system parameter estimation.

• Mechanism: Each benign node $u$ maintains a local timer $L_t^{(u)}$ recording the time of its last visit by any RW. If the elapsed time $t - L_t^{(u)}$ exceeds a predetermined threshold $A_u$, the node infers a potential RW termination. With a creation probability $q$, the node probabilistically creates a new RW by replicating the most recently visited RW stored in its local cache.
• Self-Regulation: Unlike duplication-based methods that attempt to maintain a specific population count, CIL relies on "creation" triggered by inactivity. If the RW population is wiped out, the benign nodes will eventually detect the absence of visits (exceeding $A_u$) and regenerate new RWs, ensuring the population never remains permanently extinct.
• Theoretical Framework: The authors develop a novel analytical framework to study the RW population process $\{Z_t\}$. They note that standard branching process theories (e.g., Galton-Watson) do not directly apply because the RW creation rate is density-dependent and relies on the joint system state (locations of all RWs and visitation histories). The analysis accounts for these intricate dependencies to prove stability and convergence.

Key Contributions

1. Resilience to Pac-Man Attacks: The paper demonstrates that CIL guarantees the non-extinction of the RW population almost surely, regardless of the termination probability $\zeta$. This ensures that computational tasks continue even in adversarial environments, a property not guaranteed by prior duplication-based methods like DECAFORK.
2. Theoretical Guarantees on Population Dynamics:
   • No Permanent Extinction: The RW population is guaranteed to recover from temporary extinction events.
   • No Blowup: The authors prove that the RW population size remains almost surely bounded. They provide a theoretical regime for selecting the creation probability $q$ such that the expected peak population stays below a prescribed level, independent of the network size $N$ (specifically for complete graphs, with extensions to general connected graphs).
3. Convergence of Decentralized Learning: The paper proves that RW-SGD integrated with CIL converges.
   • Convergence Point: The algorithm converges to a minimizer of a surrogate objective function defined by a quasi-stationary distribution $\pi^{(\zeta)}_{chain}$, which accounts for the bias introduced by the Pac-Man node.
   • Error Bounds: The authors characterize the deviation between the converged point $\tilde{x}^*$ and the true global optimum $x^*$, showing it is bounded.
   • Time Delay: The analysis shows that the inactive time caused by the adversary is at most a constant fraction of the total time, ensuring that the number of effective learning iterations grows linearly with time.

Experimental Results
The authors validate their theoretical findings through extensive simulations on synthetic linear regression tasks and public benchmark datasets (MNIST) under both i.i.d. and non-i.i.d. data partitions.

• Population Stability: Simulations on various graph topologies (complete, random regular, ring, Erdős–Rényi) confirm that the RW population under CIL remains bounded and recovers from extinction, whereas the DECAFORK baseline often suffers permanent extinction depending on parameter tuning.
• Convergence Performance: CIL achieves convergence to a stable loss value across different graph types. While larger creation thresholds ($A$) lead to temporary flat segments in the loss curve (due to extinction and regeneration), the algorithm eventually recovers. In contrast, DECAFORK may fail to converge entirely if parameters are not perfectly tuned.
• Trade-offs: The results illustrate a trade-off between convergence speed and communication overhead. Smaller thresholds ($A$) lead to faster convergence but higher communication costs due to frequent RW creation, while larger thresholds reduce overhead at the cost of slower real-time progress.
• Accuracy: On non-i.i.d. data, the final model accuracy under CIL is comparable to DECAFORK but significantly more robust, as DECAFORK frequently fails to complete training due to extinction.

Significance and Claims
The paper claims that CIL provides a robust, fully decentralized solution to a critical vulnerability in RW-based learning: the silent termination of learning tokens. By shifting from population estimation and duplication to local, time-based creation, the algorithm ensures that learning processes cannot be permanently halted by a single malicious node. The authors emphasize that their approach does not require knowledge of the adversary's termination probability or the network size, making it practical for real-world decentralized systems. The work establishes that while the Pac-Man attack introduces a bias in the optimization objective, the learning process remains convergent and effective, provided the RW population is self-regulated through the CIL mechanism.