Vi studerar problemet med all-till-alla informationsutbyte, även känt som skvaller, i dynamiska nätverk som kontrolleras av en motståndare som kan ändra nätverket godtyckligt från en runda till en annan, förutsatt att nätverket alltid är ansluten. I skvaller problem, det n polletter godtyckligt distribueras bland n nätverk noder, och målet är att sprida alla n polletter till varje nod. Vårt fokus ligger på token-speditionsalgoritmer, som inte manipulerar polletter på något annat sätt än att lagra, kopiera och vidarebefordra dem. Gossip kan slutföras i linjär tid i alla statiska nätverk, men en viktig och grundläggande öppen fråga för dynamiska nätverk är förekomsten av ett distribuerat protokoll som kan göra betydligt bättre än en lätt uppnåelig gräns för O(n 2 ) rundor. I tidigare arbete har det visat sig att under adaptiva motståndare - de som har full kunskap och kontroll över topologin i varje runda och även har kunskap om det distribuerade protokollet inklusive dess slumpmässiga val-varje token vidarebefordra algoritm kräver  på 2 / log n) rundor för att slutföra. I detta dokument studerar vi omedvetna motståndare, som skiljer sig från adaptiva motståndare i en avgörande aspekt - de är omedvetna om de slumpmässiga val som görs genom protokollet. Vi anser RAND-DIFF, en naturlig distribuerad algoritm där grannar utbyta en token som väljs jämnt slumpmässigt från skillnaden i deras token uppsättningar. Tidigare arbeten har visat att från och med en distribution där varje nod har en slumpmässig konstant bråkdel av tokens, avslutar RAND-DIFF i Õ(n) rundor. Däremot visar vi att en polynomisk avmattning är oundviklig under mer allmänna fördelningar: vi presenterar en (n 3/2 ) lägre gräns för RAND-DIFF under en glömsk motståndare. Vi presenterar också en (n 4/3 ) lägre bundet under en starkare uppfattning om glömska motståndare för en klass av randomiserade distribuerade algoritmer-symmetrisk kunskap-baserade algoritmer-i vilka noder gör symboliska överföringsbeslut baserat helt på de uppsättningar av polletter de har över tiden. På den positiva sidan presenterar vi en centraliserad algoritm som fullbordar skvaller i Õ(n 3/2 ) rundor med hög sannolikhet, under någon omedveten motståndare. Vi visar också en Õ(n 5/3 ) övre gräns för RAND-DIFF i en begränsad klass av omedvetna motståndare, som vi kallar ways-respekting, som kan vara av oberoende intresse.
Augustine m.fl. REF föreslår en centraliserad algoritm som fullbordar skvaller i O(n 3/2 ) rundor med hög sannolikhet, under någon glömsk motståndare.
Information Spreading in Dynamic Networks under Oblivious Adversaries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}