Vi presenterar en fullt distribuerad självläkande algoritm dex som upprätthåller ett konstant gradexpander-nätverk i en dynamisk miljö. Såvitt vi vet tillhandahåller vår algoritm den första effektiva distribuerade konstruktionen av expanderare-vars expansionsegenskaper håller deterministiskt-som fungerar även under en allsmäktig adaptiv motståndare som styr de dynamiska förändringarna i nätverket (motståndaren har obegränsad beräkningskraft och kunskap om hela nätverkstillståndet, kan bestämma vilka noder som ansluter sig och lämnar och vid vilken tidpunkt, och vet de tidigare slumpmässiga val som gjorts av algoritmen). Tidigare distribuerade expansionskonstruktioner ger vanligtvis endast probabilistiska garantier för nätverksexpansion som snabbt bryts ned i en dynamisk miljö; i synnerhet kan expansionsegenskaperna brytas ned ännu snabbare under kontradiktoriska tillägg och raderingar. Vår algoritm ger effektivt underhåll och ådrar sig en låg overhead per insättning/deletion av en adaptiv motståndare: endast O(log n) rundor och O(log n) meddelanden behövs med hög sannolikhet (n är antalet noder för närvarande i nätverket). Algoritmen kräver bara ett konstant antal topologiförändringar. Dessutom möjliggör vår algoritm ett effektivt genomförande och underhåll av en distribuerad hashtabell ovanpå dex med endast en konstant extra overhead. Våra resultat är ett steg mot att implementera effektiva självläkande nätverk som har garanterat fastigheter (konstant begränsad grad och expansion) trots dynamiska förändringar.
I samma modell presenterar REF ett protokoll som upprätthåller konstant nodgrad och konstant expansion (båda med sannolikhet 1) mot en adaptiv motståndare, samtidigt som det endast kräver logaritmiska (i nätverksstorleken) meddelanden, tid och topologi förändringar per radering/inmatning.
DEX: self-healing expanders
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}