Peer-to-peer-system förlitar sig på skalbara overlay-nätverk som möjliggör effektiv routing mellan sina medlemmar. Hyperkubiska topologier underlättar sådana operationer medan varje nod bara behöver ansluta till ett litet antal andra noder. I motsats till statiska kommunikationsnät, peer-to-peer nätverk tillåter noder att anpassa sin granne inställd över tid för att reagera för att gå med och lämna händelser och misslyckanden. Detta dokument visar hur man kan upprätthålla sådana nätverk på ett robust sätt. Konkret presenterar vi en distribuerad och självstabiliserande algoritm som konstruerar en (variant av) hoppa graf i polylogaritmisk tid från ett initialt tillstånd där överlagringsnätet fortfarande är svagt ansluten. Detta är en exponentiell förbättring jämfört med tidigare kända självstabiliserande algoritmer för overlay-nätverk. Dessutom hanteras enskilda fogar och blad lokalt och kräver lite arbete.
REF presenterade en självstabiliserande algoritm som konvergerar från någon svagt ansluten graf till en SKIP-graf (som är en expanderare med hög sannolikhet) i tid polylogaritmisk i nätverksstorleken.
A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
{'venue': "PODC '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}