*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.).
