  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. We first investigate
one-sided protocols, where piece selection is based on the states of either the
transmitter or the receiver. We show that any such protocol relying only on
pushes, or alternatively only on pulls, is inefficient in disseminating all
pieces to all users. We propose a hybrid one-sided piece selection protocol --
INTERLEAVE -- and show that by using both pushes and pulls it disseminates $k$
pieces from a single source to $n$ users in $10(k+\log n)$ time, while obeying
the constraint that each user can upload at most one piece in one unit of time,
with high probability for large $n$. An optimal, unrealistic centralized
protocol would take $k+\log_2 n$ time in this setting. Moreover, efficient
dissemination is also possible if the source implements forward erasure coding,
and users push the latest-released coded pieces (but do not pull). We also
investigate two-sided protocols where piece selection is based on the states of
both the transmitter and the receiver. We show that it is possible to
disseminate $n$ pieces to $n$ users in $n+O(\log n)$ time, starting from an
initial state where each user has a unique piece.
