On Collaborative Content Distribution using Multi-Message Gossip

Coby Fernandess and Dahlia Malkhi

We study epidemic schemes in the context of collaborative data
delivery. In this context, multiple chunks of data reside at
different nodes, and the challenge is to simultaneously deliver
all chunks to all nodes.

Here we explore the inter-operation between the gossip of multiple,
simultaneous message-chunks. In this setting, interacting nodes must
select which chunk, among many, to exchange in every communication
round.

We provide an efficient solution that possesses the inherent
robustness and scalability of gossip. Our approach maintains the
simplicity of gossip, and has low message, connections and
computation overhead. Because our approach differs from solutions
proposed by network coding, we are able to provide insight into the
tradeoffs and analysis of the problem of collaborative content
distribution. We formally analyze the performance of the algorithm,
demonstrating its efficiency with high probability.