Speaker
Jinwoo Shin
Algorithms & Randomness Center
Georgia Institute of Technology

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.).