Vi studerar hur man sprider k tokens av information till varje nod på ett n-node dynamiskt nätverk, vars kanter förändras vid varje runda. Detta grundläggande skvallerproblem kan slutföras i O(n+k) rundor i alla statiska nätverk, och att bestämma dess komplexitet i dynamiska nätverk är centralt för att förstå algoritmiska gränser och funktioner i olika dynamiska nätverksmodeller. Vårt fokus ligger på token-flowing algoritmer, som inte manipulerar polletter på något annat sätt än att lagra, kopiera och vidarebefordra dem. Vi betraktar först den starkt adaptiva motståndaren modell där i varje omgång, varje nod först väljer ett tecken för att sända till alla sina grannar (utan att veta vilka de är), och sedan en motståndare väljer en godtycklig ansluten kommunikationsnät för den omgången med kunskap om de tokens valda av varje nod. Vi visar att det behövs rundor (nk/ log n + n) för eventuella randomiserade (centraliserade eller distribuerade) token-speditionsalgoritm för att sprida k polletterna, vilket löser ett öppet problem som lyfts upp i [KLO10]. Gränsen gäller för en bred klass av initiala symboliska fördelningar, inklusive de där varje token hålls av exakt en nod och väl blandade sådana där varje nod har varje token oberoende med en konstant sannolikhet. Vårt resultat för den starkt adaptiva motståndaren modell motiverar oss att studera den svagt adaptiva motståndaren modell där i varje runda, motståndaren krävs att lägga ner nätverket först, och sedan varje nod skickar en möjligen distinkt symbol till var och en av sina grannar. Vi föreslår en enkel randomiserad distribuerad algoritm där i varje runda, längs varje kant (u, v), en token samplas jämnt slumpmässigt från den symmetriska skillnaden mellan de uppsättningar tokens som hålls av node u och node v byts. Vi bevisar att med början från en väl blandad distribution av polletter där varje nod har varje token oberoende med en konstant sannolikhet, löser denna algoritm k-gossip problemet i O (n + k) log n log k) rundor med hög sannolikhet över den ursprungliga token fördelningen och slumpmässigheten i protokollet. Vi visar sedan hur ovanstående enhetliga provtagningsproblem kan lösas med hjälp av Õ(log k) bitar av kommunikation, vilket gör den övergripande algoritm kommunikation-effektiv. * College of Computer and Information Science, Northeast University, Boston, 02115, USA. E-post: {chinmoy,raj,austin,viola}@ccs.neu.edu. Chinmoy Dutta stöds delvis av NSF-bidrag CCF-0845003 och Microsoft-bidrag till Ravi Sundaram; Rajmohan Rajaraman och Zhifeng Sun stöds delvis av NSF-bidrag CNS-0915985; Emanuele Viola stöds av NSF-bidrag CCF-0845003. † Avdelningen för matematisk vetenskap, Nanyang Technological University, Singapore 637371 och Institutionen för datavetenskap, Brown University, Providence, RI 02912, USA. E-post: gopalpandurangan@gmail.com. Stöds delvis av följande forskningsanslag: Nanyang Technological University bidrag M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 bidrag MOE2010-T2-2-082, och ett bidrag från US-Israel Binational Science Foundation (BSF). Därefter presenterar vi en centraliserad algoritm som löser skvallerproblemet för varje initial distribution i O(n + k) log 2 n) rundor i offline-inställningen där hela sekvensen av kommunikationsnät är känd för algoritmen i förväg. Slutligen presenterar vi en O(n min{k, В k log n})-runt centraliserad offline algoritm där varje nod bara kan sända en enda token till alla sina grannar i varje runda.
Såvitt vi vet ger det den första subquadratiska, helt distribuerade, token speditionsalgoritmen i dynamiska nätverk, delvis svar på en öppen fråga som tas upp i REF.
On the Complexity of Information Spreading in Dynamic Networks
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}