Abstract-This paper undersöker problemet med att bygga och underhålla distribuerade träd i dynamiska nätverk. I motsats till tidigare lösningar utgår vi inte från att det finns stabiliseringsperioder mellan topologiska förändringar, och tar itu med det mer allmänna fallet där sådana förändringar kan inträffa när som helst och koppla från nätverket. Därför presenterar vi en algoritm som bygger på en ständig alternering av topologi-framkallade uppdelningar och beräkning-framkallade sammanslagningar av en skog av spännande träd, med hjälp av slumpmässiga promenader av polletter. Den ursprungliga idén bakom denna algoritm är enkel: varje träd i skogen innehåller exakt en token, vars cirkulation är strikt begränsad till kanterna på trädet. När två polletter möts slås träden samman och en av de två polletterna förstörs. När en länk bryts genererar den intilliggande noden, som tillhör det tokenfria trädet, en ny token. Huvuddragen i detta tillvägagångssätt är att både sammanslagningar och uppdelningar är rent lokaliserade fenomen, vilket möjliggör en öppen och kontinuerlig användning av de berörda underträden (när det gäller ingen kommunikation på högre nivå). Den algoritm som presenteras här, medan kort introducerades i ett annat sammanhang, aldrig analyserades eller ordentligt diskuteras. Vi gör båda här, och ger analytiska uttryck för den förväntade sammanslagningstiden för två givna träd. Vi föreslår slutligen en betydande optimering av algoritmen som består i att använda en minnesbaserad partiskhet i symboliska promenader. Effekterna av denna optimering undersöks både analytiskt och experimentellt.
En ursprunglig algoritm föreslogs för att bygga och underhålla en skog av spanning träd i mycket dynamiska nätverk (asynkront fall) REF.
Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}