An analytical framework for self-organizing peer-to-peer anti-entropy algorithms

作者：Ozkasap Oznur; Caglar Mine^*; Yazici Emine Sule; Kucukcifci Selda

来源：Performance Evaluation, 2010, 67(3): 141-159.

DOI：10.1016/j.peva.2009.09.009

• Peer-to-peer
• Epidemic
• Anti-entropy
• Self-organizing
• Counting
• Overhead
• Delay
• Markov chain

An analytical framework is developed for establishing exact performance measures for peer-to-peer (P2P) anti-entropy paradigms used in biologically inspired epidemic data dissemination. Major benefits of these paradigms are that they are fully distributed, self-organizing, utilize local data only via pair-wise interactions, and provide eventual consistency, reliability and scalability. We derive exact expressions for infection probabilities through elaborated counting techniques on a digraph. Considering the first passage times of a Markov chain based on these probabilities, we find the expected message delay experienced by each peer and its overall mean as a function of initial number of infectious peers. Further delay and overhead analysis is given through simulations and the analytical framework. The number of contacted peers at each round of the anti-entropy approach is an important parameter for both delay and overhead. These exact performance measures and theoretical results would be beneficial when utilizing the models in several P2

• 出版日期2010-3