conference paper published Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Seth Gilbert author Rachid Guerraoui author Morteza Zadimoghaddam author ICALP: International Colloquium on Automota, Languages and Programming Gossip, 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. [1]), 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. Springer2010 eng 10.1007/978-3-642-14162-1_10 6199 LNCSPART 2115 - 126 yes D.-A. Alistarh, S. Gilbert, R. Guerraoui, M. Zadimoghaddam, in:, Springer, 2010, pp. 115–126. Alistarh, D.-A., Gilbert, S., Guerraoui, R., &#38; Zadimoghaddam, M. (2010). How efficient can gossip be? (On the cost of resilient information exchange) (Vol. 6199 LNCS, pp. 115–126). Presented at the ICALP: International Colloquium on Automota, Languages and Programming, Springer. <a href="https://doi.org/10.1007/978-3-642-14162-1_10">https://doi.org/10.1007/978-3-642-14162-1_10</a> Alistarh D-A, Gilbert S, Guerraoui R, Zadimoghaddam M. 2010. How efficient can gossip be? (On the cost of resilient information exchange). ICALP: International Colloquium on Automota, Languages and Programming, LNCS, vol. 6199 LNCS, 115–126. D.-A. Alistarh, S. Gilbert, R. Guerraoui, and M. Zadimoghaddam, “How efficient can gossip be? (On the cost of resilient information exchange),” presented at the ICALP: International Colloquium on Automota, Languages and Programming, 2010, vol. 6199 LNCS, no. PART 2, pp. 115–126. Alistarh, Dan-Adrian, et al. <i>How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)</i>. Vol. 6199 LNCS, no. PART 2, Springer, 2010, pp. 115–26, doi:<a href="https://doi.org/10.1007/978-3-642-14162-1_10">10.1007/978-3-642-14162-1_10</a>. Alistarh D-A, Gilbert S, Guerraoui R, Zadimoghaddam M. How efficient can gossip be? (On the cost of resilient information exchange). In: Vol 6199 LNCS. Springer; 2010:115-126. doi:<a href="https://doi.org/10.1007/978-3-642-14162-1_10">10.1007/978-3-642-14162-1_10</a> Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Morteza Zadimoghaddam. “How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange),” 6199 LNCS:115–26. Springer, 2010. <a href="https://doi.org/10.1007/978-3-642-14162-1_10">https://doi.org/10.1007/978-3-642-14162-1_10</a>. 7552018-12-11T11:48:20Z2023-02-23T13:10:40Z