How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)
How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)
复制标题
八卦能有多有效？
DOI：
10.1007/978-3-642-14162-1_10
复制
发表时间：
2010
影响因子：
9.8
通讯作者：
Morteza Zadimoghaddam
中科院分区：
文献类型：
--
作者：
Dan Alistarh;Seth Gilbert;R. Guerraoui;Morteza Zadimoghaddam
八卦，也称为流行病，正在成为分布式系统中日益流行的技术。但是，这仍然是一个部分开放的问题：这种协议的稳健性如何？我们考虑了随机电话模型的自然扩展（由Karp等人[1]引入），我们分析了两个不同的鲁棒性概念：耐受适应性失败的能力，以及耐受遗忘失败的能力。
对于自适应失败，我们提出了一个新的八卦协议，即Tricklegossip，它实现了近乎最佳的O（N log3 n）消息复杂性。据我们所知，这是第一个可以忍受适应性失败的流行病风格的方案。我们还显示了弹性和消息复杂性之间的直接关系，表明八卦协议可以容忍大量自适应失败，需要使用具有很高概率的超级线性消息。
对于遗忘的失败，我们提出了一个新的八卦协议，即协调gossip，该协议可实现最佳的o（n）消息复杂性。该协议使使用宇宙减少技术的新颖使用以限制消息复杂性。
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 log3 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.