Date Added: Feb 2010
The authors analyze greedy algorithms for broadcasting messages throughout a multi-hop wireless network, using a slot-based model that includes message collisions without collision detection. The algorithms are split formally into two pieces: A high-level piece for broadcast and a low-level piece for contention management. They accomplish the split using abstract versions of the MAC layer to encapsulate the contention management. They use two different abstract MAC layers: a basic non-probabilistic one, which the contention management algorithm implements with high probability, and a probabilistic one, which the contention management algorithm implements precisely.