Decomposing broadcast algorithms using abstract MAC layers

We first present a typical randomized contention-management algorithm for a standard graph-based radio network model and show that it implements both abstract MAC layers. Then we combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combinations, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ODlogn∊log(Δ) for the time to deliver a single message everywhere with probability 1 − ∊, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of OD+logn∊log(Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O(D+kΔ)logn∊log(Δ) using the basic layer and OD+kΔlogn∊log(Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages.