Optimal Communication in Radio Networks

We survey recent results on optimal communication in radio networks

Radio Networks are synchronized broadcast networks in which in each round each node can decide to send to all its neighbors with the additional twist that that simultaneous transmissions at one node get received as a useless collision. 

We give a novel lower bound that exposes a quadratic gap in the broadcast throughput depending on whether one routes messages through a radio network or employs network coding. 

In two further works we provide new distributed algorithms solving various communication tasks optimally including leader election, multicast, multiple unicasts and aggregation. 

Our results are the first (almost) optimal bounds for these problems, challenge common approaches and resolve several questions that have been open for more than two decades. 

(based on joint works with M. Ghaffari and M. Khabbazian)