Decomposing Broadcast Algorithms Using Abstract MAC Layers

Date Added: Feb 2011
Format: PDF

In much of the theoretical literature on global broadcast algorithms for wireless networks, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to more difficult communication problems. In this paper, the authors present results aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate contention management. They use two different abstract MAC layers: The basic layer of [1, 2] and a new probabilistic layer.