Controlling Gossip Protocol Infection Pattern Using Adaptive Fanout
Controlling Gossip Protocol Infection Pattern Using Adaptive Fanout
复制标题
DOI：
10.1109/icdcs.2005.20
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
S. Verma;Wei Tsang Ooi
中科院分区：
文献类型：
--
作者：
S. Verma;Wei Tsang Ooi
我们提出并评估了一种控制感染模式的模型，该模型在基于闲谈的协议中使用自适应扇出来控制感染模式。我们对基于八卦的协议的三个版本进行了建模：同步协议、伪同步协议和异步协议。我们的目标是确保组的成员在有限的延迟内以非常高的概率接收到所需的消息。我们认为控制消息传递延迟的最重要参数是八卦期间使用的扇出，即在特定八卦实例中选择的八卦目标的数量。对这三种协议进行了形式化分析，并给出了fanout的表达式。我们介绍了在同步协议的不同回合中使用可变扇出的思想。我们将fanout定义为异步协议的时间函数，以便以高概率观察到预期的感染模式。为了更好地理解理论模型，我们开发了一个伪同步协议来突出建模，以便导出与时间相关的扇出。我们证明了我们的协议生成Theta（n log n）消息，这对于八卦协议来说是最优的。我们的目标是将八卦机制用于具有软实时约束的大规模群体通信。这将减轻对通常缺乏可伸缩性的基于树的确定性协议的依赖
We propose and evaluate a model for controlling infection patterns defined over rounds or real time in a gossip-based protocol using adaptive fanout. We model three versions of gossip-based protocols: the synchronous protocol, the pseudosynchronous protocol and the asynchronous protocol. Our objective is to ensure that the members of a group receive a desired message within a bounded latency with very high probability. We argue that the most important parameter that controls the latency of message delivery is the fanout used during gossiping, i.e., the number of gossip targets chosen in a particular instance of gossip. We formally analyze the three protocols and provide expressions for fanout. We introduce the idea of using variable fanouts in different rounds in the synchronous protocol. We define fanout as a function of time for the asynchronous protocol such that an expected infection pattern is observed with high probability. For a better understanding of the theoretical model, we develop a pseudosynchronous protocol to highlight the modelling done in order to derive time dependent fanout. We show that our protocols generate Theta(n log n) messages, which is optimal for gossip protocols. We aim to use the gossiping mechanism for large-scale group communication with soft real time constraints. This would alleviate the dependence on tree-based deterministic protocols which usually lack scalability