Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast
This paper addresses two primary questions: how much faster can one disseminate information in a large wireless network if one has multiple communication channels available (as compared to relying on only a single communication channel)? Can one still disseminate information reliably, even if some subsets of the channels are disrupted? In answer to the first question, the authors reduce the cost of broadcast to O (log log n) rounds/hop, approximately, for sufficiently many channels. They answer the second question in the affirmative, presenting two different algorithms, while at the same time proving a lower bound showing that disrupted channels have unavoidable costs.