A chain-binomial model for pull and push-based information diffusion

Abstract

We compare pull and push-based epidemic paradigms for information diffusion in large scale networks. Key benefits of these approaches are that they are fully distributed, utilize local information only via pair-wise interactions, and provide eventual consistency, scalability and communication topology-independence, which make them suitable for peer-to-peer distributed systems. We develop a chain-Binomial epidemic probability model for these algorithms. Our main contribution is the exact computation of message delivery latency observed by each peer, which corresponds to a first passage time of the underlying Markov chain. Such an analytical tool facilitates the comparison of pull and push-based spread for different group sizes, initial number of infectious peers and fan-out values which are also accomplished in this study. Via our analytical stochastic model, we show that push-based approach is expected to facilitate faster information spread both for the whole group and as experienced by each member.