I tidningen undersöks effektiv distribuerad beräkning i dynamiska nätverk där nätverkets topologi ändras (delvis) från rund till rund. Random promenader är en grundläggande primitiv i en mängd olika nätverksapplikationer; den lokala och lätta karaktären av slumpmässiga promenader är särskilt användbar för att tillhandahålla enhetliga och effektiva lösningar för distribuerad kontroll av dynamiska nätverk. Med tanke på deras tillämplighet i dynamiska nätverk, fokuserar vi på att utveckla snabbt distribuerade algoritmer för att utföra slumpmässiga promenader i sådana nätverk. Vårt första bidrag är ett rigoröst ramverk för design och analys av distribuerade slumpmässiga gångalgoritmer i dynamiska nätverk. Vi utvecklar sedan en snabbt distribuerad slumpmässig gångbaserad algoritm som körs i Õ( ρ τ 0) rundor 1 (med hög sannolikhet), där τ är den dynamiska blandningstiden och 0 är nätverkets dynamiska diameter respektive, och returnerar ett prov nära en lämpligt definierad stationär distribution av det dynamiska nätverket. Vårt nästa bidrag är en snabbt distribuerad algoritm för det grundläggande problemet med informationsspridning (även kallat skvaller) i ett dynamiskt nätverk. I skvaller, eller mer allmänt, k-gossip, finns det k bitar av information (eller polletter) som initialt finns i vissa noder och problemet är att sprida k polletter till alla noder. Vi presenterar en slumpmässig-walk-baserad algoritm som körs i Õ(min {n 1/3 k 2/3 (τ 0) 1/3, k▶}) rundor (med hög sannolikhet). Detta är den första o(k▶)-tid fullt distribuerade token speditionsalgoritmen (på vissa graffamiljer) som förbättrar över den tidigare-bästa O(k▶) runda distribuerade algoritmen [Kuhn et al., STOC 2010], även om i en glömsk motståndare modell. Den ram för slumpmässiga promenader som utvecklats i detta dokument har därefter också visat sig användbar för att utveckla effektiva lagrings- och sökalgoritmer samt för att utveckla snabba bysantinska avtalsalgoritmer i dynamiska nätverk.
Sarma m.fl. REF introducerar distribuerade slumpmässiga gångalgoritmer i dynamiska nätverk.
Distributed computation in dynamic networks via random walks
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science']}