000148544 001__ 148544
000148544 005__ 20190316234804.0
000148544 037__ $$aREP_WORK
000148544 245__ $$aHow Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)
000148544 269__ $$a2010
000148544 260__ $$c2010
000148544 300__ $$a19
000148544 336__ $$aReports
000148544 520__ $$aGossip, also known as epidemic dissemination, is becoming an increasingly popular technique in distributed systems. Yet, it has remained a partially open question: how robust are such protocols? We consider a natural extension of the random phone-call model (introduced by Karp et al. [KarpFOCS-2000]), and we analyze two different notions of robustness: the ability to tolerate adaptive failures, and the ability to tolerate oblivious failures. For adaptive failures, we present a new gossip protocol, TrickleGossip, which achieves near-optimal $O(n \log^3{n})$ message complexity. To the best of our knowledge, this is the first epidemic-style protocol that can tolerate adaptive failures. We also show a direct relation between resilience and message complexity, demonstrating that gossip protocols which tolerate a large number of adaptive failures need to use a super-linear number of messages with high probability. For oblivious failures, we present a new gossip protocol, CoordinatedGossip, that achieves optimal $O(n)$ message complexity. This protocol makes novel use of the universe reduction technique to limit the message complexity.
000148544 6531_ $$agossip
000148544 6531_ $$afault-tolerance
000148544 6531_ $$adistributed algorithms
000148544 6531_ $$ainformation exchange
000148544 6531_ $$alower bound
000148544 700__ $$0242985$$aAlistarh, Dan$$g177872
000148544 700__ $$0240435$$aGilbert, Seth$$g176464
000148544 700__ $$0240335$$aGuerraoui, Rachid$$g105326
000148544 700__ $$aZadimoghaddam, Morteza
000148544 8564_ $$s345749$$uhttps://infoscience.epfl.ch/record/148544/files/Robust-Gossip-TR.pdf$$yn/a$$zn/a
000148544 909C0 $$0252114$$pDCL$$xU10407
000148544 909CO $$ooai:infoscience.tind.io:148544$$pIC$$preport$$qGLOBAL_SET
000148544 917Z8 $$x177872
000148544 937__ $$aEPFL-REPORT-148544
000148544 973__ $$aEPFL$$sPUBLISHED
000148544 980__ $$aREPORT