  Broadcasting systems such as P2P streaming systems represent important
network applications that support up to millions of online users. An efficient
broadcasting mechanism is at the core of the system design. Despite substantial
efforts on developing efficient broadcasting algorithms, the following
important question remains open: How to achieve the maximum broadcast rate in a
distributed manner with each user maintaining information queues only for its
direct neighbors? In this work, we first derive an innovative formulation of
the problem over acyclic overlay networks with arbitrary underlay capacity
constraints. Then, based on the formulation, we develop a distributed algorithm
to achieve the maximum broadcast rate and every user only maintains one queue
per-neighbor. Due to its lightweight nature, our algorithm scales very well
with the network size and remains robust against high system dynamics. Finally,
by conducting simulations we validate the optimality of our algorithm under
different network capacity models. Simulation results further indicate that the
convergence time of our algorithm grows linearly with the network size, which
suggests an interesting direction for future investigation.
