提出自生成随机游走机制,抵御恶意节点中断学习的隐蔽攻击。
Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks
- 设计自创建随机游走算法,动态补充被恶意节点截断的路径。
- 理论证明游走种群不灭绝且可收敛,偏差可控,延迟线性增长。
- 适用于高风险去中心化学习场景,如区块链、物联网协作训练。
基于随机游走(RW)的算法因开销低、可扩展而广泛用于分布式系统,近年在去中心化学习中应用增多。然而其依赖局部交互的特性使其易受恶意行为影响。本文研究一种名为「吃豆人」(Pac-Man)的攻击:恶意节点以概率终止所有访问它的随机游走,悄然消减活跃游走,导致学习停滞却无告警。为此,我们提出完全去中心化的抗毁机制CIL(CREATE-IF-LATE),实现自创建随机游走,防止游走灭绝。理论分析表明,该算法保证:(i) 游走种群不灭绝,(ii) 种群几乎必然有界,(iii) 即使存在吃豆人攻击,基于游走的随机梯度下降仍可收敛,且与真实最优解的偏差可量化。学习过程最多产生线性时间延迟。大量实验在合成与公开基准数据集上验证了理论结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。