Abstrakt. Högt dynamiska nätverk kännetecknas av frekventa förändringar i tillgången till kommunikationslänkar. Många av dessa nätverk är i allmänhet uppdelade i flera komponenter som fortsätter att dela upp sig och gå samman kontinuerligt och oförutsägbart. Vi presenterar en algoritm som strävar efter att upprätthålla en skog av spännande träd i sådana nätverk, utan någon form av antagande om graden av förändringar. Vår algoritm är anpassning av en grovkornig interaktionsalgoritm till den synkrona meddelandepasseringsmodellen (för dynamiska nätverk). Medan de höga principerna för grovkornsvarianten bevaras, visar sig den nya algoritmen vara betydligt mer komplex. I synnerhet innebär det en ny teknik som består av att upprätthålla en distribuerad permutation av uppsättningen av alla noder ID under hela utförandet. Algoritmen ärver också egenskaperna hos sin ursprungliga variant: Den bygger på rent lokaliserade beslut, för vilka ingen global information någonsin samlas in vid noderna, och ändå upprätthåller den ett antal kritiska egenskaper oavsett frekvensen och omfattningen av förändringarna. I synnerhet, nätverket förblir alltid täckt av en spännande skog där 1) ingen cykel någonsin kan visas, 2) varje nod tillhör ett träd, och 3) efter ett godtyckligt antal kant försvinner, alla maximala delträd omedelbart återställa exakt en token (på deras rot). Dessa egenskaper garanteras oavsett dynamik, även om det fortsätter under en godtycklig lång tidsperiod. Optimalitet är inte fokus här, men antalet träd per komponenter -måttet av intresse här - konvergerar till en om nätverket slutar förändras (som dock aldrig förväntas hända). Algoritmernas korrekthet är bevisad och dess beteende testas genom experiment.
M. Barjon m.fl. REF har behandlat konstruktion och underhåll av en spännande skog (synkronfallet), utan några som helst antaganden om förändringstakten.
Maintaining a Spanning Forest in Highly Dynamic Networks: The Synchronous Case
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}