Abstract
Efficient scheduling to resolve contention among multiple entities, also known as Medium Access Control (MAC), is the fundamental algorithmic problem that needs to be resolved for designing a high-performance communication network architecture. MAC algorithms are required to be extremely simple and distributed in order to be implementable while utilizing limited network resources efficiently. Despite a long history starting from the Aloha network in 1970's, a satisfactory simple, distributed MAC algorithm of high performance has remained illusive till recently.

In this talk, I will present such a satisfactory MAC protocol for arbitrary wireless networks. Our solution blends the classical Metropolis Hastings sampling mechanism with insights obtained from analysis of time-varying queuing dynamics or Markov process to obtain a desired protocol. Methodologically, our theoretical framework is applicable to design of efficient distributed scheduling algorithms for a wide class of combinatorial resource allocation problems, including switch scheduling and optical network scheduling.

This is a joint work with Devavrat Shah (EECS, MIT) and Prasad Tetali (Math, Georgia Tech.).