Gossiping With Multiple Messages

This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. The authors first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. They show that any such protocol relying only on pushes, or alternatively only on pulls, is inefficient in disseminating all pieces to all users.