Vi anser att problemet med självläkande i omkonfigurerbara nätverk (t.ex. peer-to-peer och trådlösa mesh nätverk) som är under upprepad attack av en allvetande motståndare och föreslå en fullt distribuerad algoritm, Xheal, som upprätthåller god expansion och spektral egenskaper i nätverket, också hålla nätverket ansluten. Dessutom gör Xheal detta samtidigt som det endast tillåter låg stretch och grad ökning per nod. Algoritmen läker globala egenskaper som expansion och stretch samtidigt som den bara gör lokala förändringar och använder endast lokal information. Vi använder en modell liknande den som användes i det senaste arbetet med självläkning. I vår modell, över en sekvens av rundor, infogar en motståndare antingen en nod med godtyckliga anslutningar eller tar bort en godtycklig nod från nätverket. Nätverket svarar med snabba "reparationer", som består av att lägga till eller ta bort kanter på ett effektivt lokaliserat sätt. Dessa reparationer bevara kanten expansion, spektral gap, och nätverk stretch, efter motstående raderingar, utan att öka nod grader med för mycket, i följande bemärkelse. När som helst i algoritmen kommer utbyggnaden av grafen att vara antingen "bättre" än utbyggnaden av grafen som bildas genom att endast beakta de kontradiktoriska ingångarna (inte de kontradiktoriska raderingarna) eller expansionen kommer åtminstone att vara en konstant. Även sträckningen d.v.s. Avståndet mellan varje par noder i den botade grafen är inte mer än en O(log n) faktor. På samma sätt, vid varje punkt, en nod v vars grad skulle ha varit d i grafen med kontradiktoriska ingångar endast, kommer att ha grad som mest O(σd) i den faktiska grafen, för en liten * parameter σ. Vi tillhandahåller också gränser på det näst minsta eigenvärdet av Laplacian som fångar viktiga egenskaper såsom blandningstid, ledning, trängsel i routing etc. Vår distribuerade datastruktur har låga amorteringsfria latens- och bandbreddskrav. Vårt arbete förbättrar över självläkande algoritmer Forgeing tree [PODC 2008] och Forgeing graf [PODC 2009] på så sätt att vi kan ge garantier på grad och stretch, samtidigt som vi bevarar nätverkets expansions- och spektralegenskaper.
Den självläkande algoritmen Xheal av REF upprätthåller spektral egenskaper av nätverket (samtidigt som det bara tillåter en liten ökning av sträcka och grad), men den förlitade sig på en randomiserad expansioner konstruktion och därmed de spektral egenskaper bryts snabbt.
Xheal: localized self-healing using expanders
{'venue': "PODC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}