Random Access Can Be Optimal

Mung Chiang
Princeton University

In contrast to other distributed scheduling algorithms in wireless networks that require communication overhead, random access without message passing is truly simple, although its performance is often believed to be inferior after more than thirty years of study. In collaboration with UBC and Microsoft Research, we develop an Aloha-type algorithm that is utility-optimal for certain topologies and then a CSMA-type algorithm that is utility-optimal in general. Unique combinations of optimization theory, learning theory, and probability theory are used to construct the proofs of these surprising results.

Back to Workshops IV: New Mathematical Frontiers in Network Multi-Resolution Analysis