  In this paper, we study local and global broadcast in the dual graph model,
which describes communication in a radio network with both reliable and
unreliable links. Existing work proved that efficient solutions to these
problems are impossible in the dual graph model under standard assumptions. In
real networks, however, simple back-off strategies tend to perform well for
solving these basic communication tasks. We address this apparent paradox by
introducing a new set of constraints to the dual graph model that better
generalize the slow/fast fading behavior common in real networks. We prove that
in the context of these new constraints, simple back-off strategies now provide
efficient solutions to local and global broadcast in the dual graph model. We
also precisely characterize how this efficiency degrades as the new constraints
are reduced down to non-existent, and prove new lower bounds that establish
this degradation as near optimal for a large class of natural algorithms. We
conclude with a preliminary investigation of the performance of these
strategies when we include additional generality to the model. These results
provide theoretical foundations for the practical observation that simple
back-off algorithms tend to work well even amid the complicated link dynamics
of real radio networks.
