Att utföra slumpmässiga promenader i nätverk är en grundläggande primitiv som har hittat tillämpningar inom många områden av datavetenskap, inklusive distribuerad dator. I den här artikeln fokuserar vi på problemet med provtagning slumpmässiga promenader effektivt i ett distribuerat nätverk och dess tillämpningar. Med tanke på bandbredd begränsningar, är målet att minimera antalet rundor som krävs för att få slumpmässiga gångprover. Alla tidigare algoritmer som beräknar ett slumpmässigt gångprov av längd som en subrutin alltid göra så naivt, det vill säga i O( ) rundor. Det viktigaste bidraget i denna artikel är en snabb distribuerad algoritm för att utföra slumpmässiga promenader. Vi presenterar en sublinjär tid distribuerad algoritm för att utföra slumpmässiga promenader vars tid komplexitet är sublinear i längden på promenaden. Vår algoritm utför en slumpmässig längdgång i Õ D-rundor (Õ döljer polylog n-faktorer där n är antalet noder i nätverket) med hög sannolikhet på ett oriktat nätverk, där D är nätverkets diameter. För grafer med liten diameter är detta en betydande förbättring jämfört med de naiva O( ) bundna. Dessutom är vår algoritm optimal inom en poly-logaritmisk faktor eftersom det finns en matchande lägre gräns [Nanongkai et al. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Vi utökar vidare våra algoritmer för att effektivt utföra k oberoende slumpmässiga promenader i Õ K D + k rundor. Vi visar också att vår algoritm kan tillämpas för att påskynda den mer allmänna Metropolis-Hastings provtagning. Våra slumpmässiga algoritmer kan användas för att påskynda distribuerade algoritmer i applikationer som använder slumpmässiga promenader som subrutin. Vi presenterar två huvudsakliga ansökningar. För det första ger vi en snabb distribuerad algoritm för beräkning av ett slumpmässigt spanning träd (RST) i ett godtyckligt (oriktat oviktat) nätverk som körs i Õ ε mD rundor med hög sannolikhet (m är antalet kanter). Vår andra applikation är en snabb decentraliserad algoritm för att uppskatta blandningstid och relaterade parametrar för det underliggande nätverket. Vår algoritm är helt decentraliserad och kan fungera som en byggsten i designen av topologiskt-medvetna nätverk.
Ett viktigt bidrag till detta arbete är att bygga vidare på Ref-metoden ger snabbare resultat i slumpmässiga gångberäkningar även i dynamiska nätverk.
Distributed Random Walks
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}