Gossiping in radio networks

Leszek Gasieniec

We consider the problem of efficient communication in (ad-hoc) radio networks. We will be especially interested in the design of efficient `broadcasting' (one-to-all communication) and `gossiping' (total information exchange) procedures. We will discuss several aspects of radio communication including: deterministic vs. randomised, fully distributed vs. centralised and oblivious vs. adaptive methods. Please note that despite strong reference to radio communication this talk is all about some interesting combinatorial structures (selective families) and several types of discrete algorithms. We conclude the presentation with a list of open problems.