Optimal serial broadcast of successive chunks

This paper considers the problem of broadcasting successive chunks to all nodes in a communication network under the assumption that every node can upload a chunk to exactly one adjacent node at a time. This problem models the delivery of video streams in Peer-to-Peer (P2P) networks in which a stream of chunks is continuously given from an external media server. We propose two schemes for solving the problem. The first scheme attains an optimum broadcast time of ⌈lg⁡n⌉ steps using an overlay network in which each node has O(lg2⁡n) children, where n is the number of nodes in the network. The second scheme reduces the number of children by slightly increasing the broadcast time. More concretely, it completes each broadcast in lg⁡n+o(lg⁡n) steps when the number of children is bounded by O((f(n))2) for any function f satisfying f(x)=ω(1) and f(x)=o(lg⁡x).