Low latency group communication over broadcast erasure channels

  • Mark A Graham

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


Group communication allows a collection of transceivers to mutually share messages, from either a single or multiple sources to multiple sinks. This form of communication has numerous applications, including vehicular networking, content distribution and multimedia streaming. Reliability and low latency are highly desirable for these applications. This thesis addresses the problem of low latency group communication by developing lightweight distributed algorithms. Most previous work in this area focuses on wired point-to-point links. Motivated by the increased prevalence of wireless networks, this thesis focuses on broadcast channels.

The first problem addressed in this thesis is broadcasting from a single source
to large numbers of receivers. The channels to distinct receivers are assumed to be independent discrete memoryless erasure channels. Random Linear Network Coding (RLNC) is shown to achieve non-vanishing throughput, unachievable by ARQ, in exchange for delay scaling with the number of receivers n as O(log(n)). The tradeoff between its throughput and delay is quantified.

The next problem considered is all-to-all (allcast) communication in which agents take it in turns to broadcast packets. Each broadcast is received correctly by only a subset of the agents, and is erased at the others. The network of correct receptions at each time-step is modelled by a random graph, and these graphs are correlated over time.

Three algorithms to address this problem are proposed: one in which messages
are randomly forwarded, and two RLNC algorithms in which random linear combinations of messages are broadcast. A rigorous mathematical analysis of these algorithms is presented for graphs which are constant over time. The RLNC algorithms are shown to complete in a constant number of time-steps, as opposed to O(log(n)) for the baseline, enabling better scalability to large networks. Finally the analysis is supplemented by simulations, which address the more general setting of graphs evolving as Markov chains.
Date of Award28 Sept 2021
Original languageEnglish
Awarding Institution
  • University of Bristol
SupervisorA J Ganesh (Supervisor) & Robert J Piechocki (Supervisor)


  • Network coding
  • Fountain coding
  • Allcast
  • Throughput-delay trade-off

Cite this