Jinwoo Shin, Georgia Tech

Event Details
  • Date/Time:
    • Friday October 8, 2010
      1:00 pm - 2:00 pm
  • Location: Executive Classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Shuangchi He
H. Milton Stewart School of Industrial and Systems Engineering
Contact Shuangchi He

Summary Sentence: Jinwoo Shin, Georgia Tech

Full Summary: Efficient Distributed Medium Access Algorithm

Jinwoo Shin
Algorithms & Randomness Center
Georgia Institute of Technology

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

Additional Information

In Campus Calendar

Hg Training

Invited Audience
No audiences were selected.
distributed algorithm, stochastics
  • Created By: Shuangchi He
  • Workflow Status: Published
  • Created On: Oct 3, 2010 - 8:00pm
  • Last Updated: Oct 7, 2016 - 9:56pm