Vi studerar det grundläggande problemet med informationsspridning (även känd som skvaller) i dynamiska 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. Målet är att utföra uppgiften i så få omgångar distribuerade beräkningar som möjligt. Problemet är särskilt utmanande i dynamiska nätverk där nätverkets topologi kan ändras från rund till rund och styras av en on-line motståndare. Fokus i detta dokument är på kraften i token-spedition algoritmer, som inte manipulerar polletter på något annat sätt än att lagra och vidarebefordra dem. Vi betraktar först en värsta fall kontraversariell modell som först studerades av Kuhn, Lynch och Oshman [33] där kommunikationslänkarna för varje omgång väljs av en motståndare, och noder vet inte vilka deras grannar för den aktuella omgången är innan de sänder sina meddelanden. Vårt huvudresultat är en lägre gräns för antalet rundor som behövs för alla deterministiska token-speditionsalgoritm för att lösa k-gossip. Detta löser ett öppet problem som höjdes i [33], förbättra sin nedre gräns av  och (n log k), och matcha deras övre gräns för O (nk) till inom en logaritmisk faktor. Vår nedre gräns sträcker sig också till randomiserade algoritmer mot en motståndare som i varje omgång vet utfallet av den slumpmässiga myntkastningen i den omgången. Vårt resultat visar att man inte kan erhålla signifikant effektiva (dvs subquadratiska) token-speditionsalgoritmer för skvaller i den kontradiktoriska modellen av [33]. Vi visar nästa att token-forwarding algoritmer kan uppnå subkvadratisk tid i offline-versionen av problemet, där motståndaren måste göra alla topologi förändringar i förväg i början av beräkningen. Vi presenterar två polynom-tid offline token-forwarding algoritmer för att lösa k-gossip: (1) en O(min {nk, n ε k log n}) rund algoritm, och (2) en (O(n ), log n) bicriteria approximation algoritm, för alla > 0, vilket innebär att om L är antalet rundor som behövs för en optimal algoritm, då vår approximation algoritm kommer att slutföra i O(n L) rundor och antalet polletter som överförs på någon kant är O (log n) i varje runda. Våra resultat är ett steg mot att förstå kraften och begränsningen av token-speditionsalgoritmer i dynamiska nätverk.
Denna nedre gräns är avsevärt förbättrad i REF, där en nästan tight (nk/ log n) nedre gräns bevisas.
Information Spreading in Dynamic Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}