Provably Optimal Decentralised Broadcast Algorithms

In this paper we consider the problem of broadcasting information from a source node to a set of receiver nodes. In the context of edge-capacitated networks, we consider the “random useful” packet forwarding algorithm. We prove that it yields a stable system, provided the data injection rate at the source node is less than the (min(min-cut)) of the graph. As a corollary we retrieve a famous theorem of Edmonds. We next consider node-capacitated networks. In this context we introduce the “random useful to most deprived neighbour” packet forwarding scheme. We show that it yields a stable system in the particular case where the network graph is the complete graph, whenever the node capacities are large enough for centralised schemes to achieve successful broadcast of the data injection rate.