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

Technische Samenvatting: Zelf-creërende Random Walks voor Gedecentraliseerd Leren onder Pac-Man Aanvallen

Probleemformulering
Het artikel behandelt de kwetsbaarheid van op Random Walk (RW)-gebaseerde gedecentraliseerde leeralgoritmen voor een specifieke klasse van sluipende aanvallen, getiteld de "Pac-Man aanval". In standaard RW-gebaseerde algoritmen (bijv. RW-SGD) bewegen tokens door een netwerkgraaf om lokale updates uit te voeren en globale informatie te aggregeren. De auteurs identificeren een dreiging waarbij een kwaadwillige knoop (de "Pac-Man") met een bepaalde waarschijnlijkheid elke RW die hem bezoekt, beëindigt zonder de vereiste berekening of doorsturing van de token uit te voeren. In tegen tegenstelling tot traditionele Byzantine of poisoning aanvallen, bootst de Pac-Man-knoop in andere aspecten normaal gedrag na (bijv. reageren op fouttolerantiecontroles), waardoor hij moeilijk te detecteren is via conventionele methoden.

Het kernprobleem is dat zelfs één enkele Pac-Man-knoop, door RW's met een positieve waarschijnlijkheid $\zeta \in (0, 1]$ te beëindigen, uiteindelijk met een waarschijnlijkheid van één tot de extinctie van alle actieve RW's in het netwerk kan leiden. Dit stopt het leerproces volledig zonder expliciete foutmeldingen te triggeren. Bestaande redundantie-gebaseerde benaderingen (bijv. starten met meerdere RW's) falen omdat statische redundantie de uiteindelijke extinctie in aanwezigheid van een persistente terminatie-adversary niet kan voorkomen. Bovendien blijken bestaande zelfregulerende mechanismen zoals DECAFORK en AC, die vertrouwen op het schatten van de populatiegrootte of bezoekintervallen om duplicatie te triggeren, gevoelig te zijn voor parametervariaties en kunnen ze nog steeds lijden onder permanente extinctie onder dit aanvalsmodel.

Methodologie: Het CREATE-IF-LATE (CIL) Algoritme
Om de Pac-Man aanval te bestrijden, stellen de auteurs CREATE-IF-LATE (CIL) voor, een volledig gedecentraliseerd mechanisme dat de langetermijnoverleving van de RW-populatie garandeert zonder dat globale coördinatie of systeemparameter-schatting vereist is.

• Mechanisme: Elke welwillende knoop $u$ houdt een lokale timer $L_t^{(u)}$ bij die de tijd registreert van het laatste bezoek door een RW. Als de verstreken tijd $t - L_t^{(u)}$ een vooraf bepaalde drempel $A_u$ overschrijdt, concludeert de knoop een potentiële RW-terminatie. Met een creatiewaarschijnlijkheid $q$ creëert de knoop probabilistisch een nieuwe RW door de meest recent bezochte RW uit de lokale cache te repliceren.
• Zelfregulatie: In tegen tegenstelling tot duplicatie-gebaseerde methoden die proberen een specifieke populatieomvang te handhaven, vertrouwt CIL op "creatie" getriggerd door inactiviteit. Als de RW-populatie wordt weggevaagd, zullen de welwillende knopen uiteindelijk de afwezigheid van bezoeken detecteren (overschrijding van $A_u$) en nieuwe RW's regenereren, wat ervoor zorgt dat de populatie nooit permanent uitgestorven blijft.
• Theoretisch Kader: De auteurs ontwikkelen een nieuw analytisch kader om het RW-populatieproces $\{Z_t\}$ te bestudelen. Ze merken op dat standaard vertakkingsproces-theorieën (bijv. Galton-Watson) niet direct van toepassing zijn omdat de RW-creatierate dichtheidsafhankelijk is en afhangt van de gezamenlijke systeemtoestand (locaties van alle RW's en bezoekgeschiedenissen). De analyse houdt rekening met deze complexe afhankelijkheden om stabiliteit en convergentie te bewijzen.

Belangrijkste Bijdragen

1. Veerkracht tegen Pac-Man Aanvallen: Het artikel demonstreert dat CIL de niet-extinctie van de RW-populatie bijna zeker garandeert, ongeacht de terminatiekans $\zeta$. Dit zorgt ervoor dat computationele taken doorgaan in adversariële omgevingen, een eigenschap die niet gegarandeerd wordt door eerdere duplicatie-gebaseerde methoden zoals DECAFORK.
2. Theoretische Garanties op Populatiedynamiek:
   • Geen Permanente Extinctie: De RW-populatie is gegarandeerd te herstellen van tijdelijke extinctie-events.
   • Geen Blowup: De auteurs bewijzen dat de RW-populatiegrootte bijna zeker begrensd blijft. Ze bieden een theoretisch regime voor het selecteren van de creatiewaarschijnlijkheid $q$ zodanig dat de verwachte piekpopulatie onder een voorgeschreven niveau blijft, onafhankelijk van de netwerkomvang $N$ (specifiek voor complete grafen, met uitbreidingen naar algemene verbonden grafen).
3. Convergentie van Gedecentraliseerd Leren: Het artikel bewijst dat RW-SGD geïntegreerd met CIL convergeert.
   • Convergentiepunt: Het algoritme convergeert naar een minimizer van een surrogaat-doelfunctie gedefinieerd door een quasi-stationaire distributie $\pi^{(\zeta)}_{chain}$, die de bias account voor de introductie door de Pac-Man-knoop.
   • Foutgrenzen: De auteurs karakteriseren de afwijking tussen het geconvergeerde punt $\tilde{x}^*$ en het ware globale optimum $x^*$, en tonen aan dat deze begrensd is.
   • Tijdvertraging: De analyse laat zien dat de inactieve tijd veroorzaakt door de adversary maximaal een constante fractie van de totale tijd is, wat ervoor zorgt dat het aantal effectieve leeriteraties lineair met de tijd groeit.

Experimentele Resultaten
De auteurs valideren hun theoretische bevindingen via uitgebreide simulaties op synthetische lineaire regressietaken en publieke benchmark-datasets (MNIST) onder zowel i.i.d. als non-i.i.d. datapartities.

• Populatiestabiliteit: Simulaties op diverse graaftopologieën (complete, random regular, ring, Erdős–Rényi) bevestigen dat de RW-populatie onder CIL begrensd blijft en herstelt van extinctie, terwijl de DECAFORK-baseline vaak last heeft van permanente extinctie afhankelijk van de parametertuning.
• Convergentieprestaties: CIL bereikt convergentie naar een stabiele verlieswaarde over verschillende graaftypen. Hoewel grotere creatiedrempels ($A$) leiden tot tijdelijke vlakke segmenten in de verliescurve (door extinctie en regeneratie), herstelt het algoritme uiteindelijk. In tegenstelling hiertoe kan DECAFORK mogelijk geheel niet convergeren als de parameters niet perfect zijn afgesteld.
• Trade-offs: De resultaten illustreren een afweging tussen convergentiesnelheid en communicatie-overhead. Kleinere drempels ($A$) leiden tot snellere convergentie maar hogere communicatiekosten door frequente RW-creatie, terwijl grotere drempels de overhead verminderen ten koste van tragere real-time progressie.
• Nauwkeurigheid: Op non-i.i.d. data is de uiteindelijke modelnauwkeurigheid onder CIL vergelijkbaar met DECAFORK, maar aanzienlijk robuuster, aangezien DECAFORK vaak faalt om de training te voltooien door extinctie.

Betekenis en Claims
Het artikel claimt dat CIL een robuuste, volledig gedecentraliseerde oplossing biedt voor een kritieke kwetsbaarheid in RW-gebaseerd leren: de stille terminatie van leer-tokens. Door de focus te verschuiven van populatie-estimatie en duplicatie naar lokale, tijd-gebaseerde creatie, zorgt het algoritme ervoor dat leerprocessen niet permanent gestopt kunnen worden door een enkele kwaadwillige knoop. De auteurs benadrukken dat hun aanpak geen kennis vereist van de terminatiekans van de adversary of de netwerkomvang, wat het praktisch maakt voor real-world gedecentraliseerde systemen. Het werk stelt vast dat hoewel de Pac-Man aanval een bias introduceert in de optimalisatie-doelfunctie, het leerproces convergent en effectief blijft, mits de RW-populatie zelf-gereguleerd wordt via het CIL-mechanisme.