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 detta dokument fokuserar vi på problemet med att utföra slumpmässiga promenader effektivt i ett distribuerat nätverk. Med tanke på bandbredd begränsningar, är målet att minimera antalet rundor som krävs för att få en slumpmässig gångprov. Alla tidigare algoritmer som beräknar ett slumpmässigt gångprov av längd som en subrutin alltid göra så naivt, dvs. i O( ) rundor. Det viktigaste bidraget i detta papper är en snabb distribuerad algoritm för att utföra slumpmässiga promenader. Vi visar att ett slumpmässigt gångprov av längd kan beräknas i Õ( 2/3 D 1/3 ) rundor på ett oriktat oviktat nät, där D är nätets diameter. 1 När = (D log n) är detta en förbättring jämfört med den naiva O( ) bundna. (Vi visar att Min {D, }) är en lägre gräns och därför i allmänhet kan vi inte ha en körtid snabbare än diametern på grafen.) Vi visar också att vår algoritm kan tillämpas för att påskynda den mer allmänna MetropolisHastings provtagning. Vi utökar våra algoritmer för att utföra ett stort antal, k, av slumpmässiga promenader effektivt. Vi visar hur k destinationer kan provtas i Õ ((k ) 2/3 D 1/3 ) rundor om k ≤ 2 och Õ(k ) 1/2 ) rundor annars. Vi presenterar också snabbare algoritmer för att utföra slumpmässiga promenader av längd större än (eller lika med) blandningstiden för den underliggande grafen. Våra tekniker kan vara användbara för att påskynda distribuerade algoritmer för en mängd olika applikationer som använder slumpmässiga promenader som subrutin.
Den idé på hög nivå som används i Õ(l 2/3 D 1/3 )-round algoritmen i REF är att "preparera" några korta promenader i början (som utförs parallellt) och sedan försiktigt sy ihop dessa promenader senare vid behov.
Fast distributed random walks
{'venue': "PODC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}