Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Provably optimal decentralised broadcast algorithms

Christos Gkantsidis, Laurent Massoulié, Pablo Rodriguez, and Andy Twigg

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2006-105
Pages14
InstitutionMicrosoft Research
> Publications > Provably optimal decentralised broadcast algorithms