I detta papper studerar vi PUSH-PULL stil rykte sprider algoritmer i mobiltelefonmodellen, en variant av den klassiska telefonmodellen där varje nod kan delta i högst en anslutning per runda; d.v.s. kan du inte längre ha flera noder dra information från samma källa i en enda runda. Vår modell innehåller också två nya parameteriserade generaliseringar: (1) nätverket topologi kan genomgå en begränsad hastighet av förändring (för en parameteriserad hastighet som sträcker sig från inga förändringar till förändringar i varje runda); och (2) i varje runda, varje nod kan annonsera en begränsad mängd information till alla sina grannar innan anslutningsbeslut fattas (för ett parameteriserat antal bitar som sträcker sig från ingen annons till stora annonser). Vi bevisar att i mobiltelefonmodellen utan reklam och inga topologiförändringar, PUSH-PULL stil algoritmer presterar dåligt med avseende på en grafs vertex expansion och grafledning jämfört med de kända tighta resultaten i den klassiska telefonmodellen. Vi bevisar dock att om noder tillåts att annonsera en enda bit i varje runda, en naturlig variation av PUSH-PUL avslutas i tid som matchar (inom logaritmiska faktorer) denna strategi prestanda i den klassiska telefonmodellen-även i närvaro av frekventa topologi förändringar. Vi analyserar också hur prestandan hos denna algoritm försämras när förändringstakten ökar mot maximalt möjliga belopp. Vi hävdar att vår modell väl matchar egenskaperna hos framväxande peer-to-peer kommunikationsstandarder för mobila enheter, och att vår effektiva PUSH-PULL variation som utnyttjar små annonser och anpassar sig väl till topologi förändringar är ett bra val för rykte sprids i denna allt viktigare miljö.
I detta dokument studerar och utökar vi både mobiltelefonmodellen som infördes 2016 av Ghaffari och Newport REF.
How to Discreetly Spread a Rumor in a Crowd
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}