  We consider streaming over a peer-to-peer network with homogeneous nodes in
which a single source broadcasts a data stream to all the users in the system.
Peers are allowed to enter or leave the system (adversarially) arbitrarily.
Previous approaches for streaming in this setting have either used randomized
distribution graphs or structured trees with randomized maintenance algorithms.
Randomized graphs handle peer churn well but have poor connectivity guarantees,
while structured trees have good connectivity but have proven hard to maintain
under peer churn. We improve upon both approaches by presenting a novel
distribution structure with a deterministic and distributed algorithm for
maintenance under peer churn; our result is inspired by a recent work proposing
deterministic algorithms for rumor spreading in graphs. A key innovation in our
approach is in having redundant links in the distribution structure. While this
leads to a reduction in the maximum streaming rate possible, we show that for
the amount of redundancy used, the delay guarantee of the proposed algorithm is
near optimal. We introduce a tolerance parameter that captures the worst-case
transient streaming rate received by the peers during churn events and
characterize the fundamental tradeoff between rate, delay and tolerance. A
natural generalization of the deterministic algorithm achieves this tradeoff
near optimally. Finally, the proposed deterministic algorithm is robust enough
to handle various generalizations: ability to deal with heterogeneous node
capacities of the peers and more complicated streaming patterns where multiple
source transmissions are present.
