Self-creating random walks for decentralised learning under Pac-Man attacks

Random walk (RW)-based algorithms have been popular in distributed systems due to low overheads and scalability. However, their reliance on local interactions makes them vulnerable to malicious behaviour. 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. To counter this threat, we propose the CREATE-IF-LATE algorithm, which is a fully decentralized, resilient mechanism. The proposed algorithm has 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 SGD even in the presence of Pac-Man with a quantifiable deviation from the true optimum. Extensive empirical results validate our theoretical findings.

Click here to join the seminar via Zoom
Meeting ID: 918 7152 1028
Passcode: 260999

Xingran Chen is a postdoctoral researcher at Rutgers University. He is also an assistant professor (currently on leave) in the School of Information and Communication Engineering at the University of Electronic Science and Technology of China (as of September 2023). He earned his BS in Statistics (2015) from Central South University, followed by an MA in Applied Mathematics and Computational Science (2018) and a PhD in Electrical and Systems Engineering (2023) from the University of Pennsylvania. His research explores the information-theoretic foundations and algorithm design for decentralised networked systems. In 2023, he received the IEEE Communications Society & Information Theory Society Joint Paper Award. He also served as a guest editor for China Communications in 2024, and Entropy in 2025.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg