Vi överväger problemet med att utföra en slumpmässig promenad i ett distribuerat nätverk. Med tanke på bandbredd begränsningar, är målet med problemet att minimera antalet rundor som krävs för att få en slumpmässig gångprov. Das Sarma m.fl. [PODC'10] visar att en slumpmässig längdgång på ett nät av diameter D kan utföras i Õ( En viktig fråga som lämnas öppen är om det finns en snabbare algoritm, särskilt om multiplikationen av ε och ε D är nödvändig. I detta dokument visar vi en snäv villkorslös lägre gräns för tids komplexiteten i distribuerad slumpmässig gångberäkning. Specifikt, Vi visar att för alla n, D, och, Utföra en slumpmässig gång av längd  på en n-node nätverk av diameter D kräver  och ( Ă D + D) tid. Denna gräns är ovillkorlig, d.v.s. den innehar för någon (eventuellt randomiserad) algoritm. Såvitt vi vet är detta den första nedre gränsen som diametern spelar en roll av multiplikativ faktor. Vår gräns visar att algoritmen för Das Sarma et al. är tiden optimal. Vår proof teknik introducerar en ny koppling mellan begränsad-round kommunikation komplexitet och distribuerad algoritm lägre gränser med D som en kompromiss-parameter, stärka den tidigare studien av Das Sarma et al. [STOC'11] I synnerhet använder vi oss av den begränsade kommunikations komplexiteten hos pekaren som jagar problemet. Vår teknik kan vara av oberoende intresse och kan vara användbar för att visa icke-triviala lägre gränser på komplexiteten i andra grundläggande distribuerade datorproblem. * En fullständig version av detta dokument finns tillgänglig som [28] på http: // arxiv.org/abs/1102.2906 †
Specifikt visas det i REF att för alla n, D och D ≤ n/ D 3 log n 1/4, utföra en slumpmässig gång av längd
A tight unconditional lower bound on distributed randomwalk computation
{'venue': "PODC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}