[Colloq] Devavrat Shah 11/17

[Diane Keys]

CCIS Colloquium Fall 2006

Message-Passing Algorithms for Network Scheduling

Speaker: Devavrat Shah

Affiliation: Department of EECS, MIT

Date: Friday, November 17, 2006

Talk: 12:00 pm, 366 WVH

Abstract

A central operational problem in a network is the scheduling of 
resources to resolve contention between various entities accessing them. 
Some popular examples are switch scheduling, MAC scheduling in wireless 
network and bandwidth allocation in a flow network. Ideally, an 
implementor would like to have access to a parametrized class of 
algorithms so that by ‘tuning’ parameters a necessary trade-off between 
ease of implementation and performance be achieved.

In this talk, I will present such a parametrized class of simple, 
distributed message-passing algorithm for scheduling in switches and 
wireless network based on belief propagation. I will talk about the 
correctness and convergence properties of the algorithm in this context. 
I will discuss its relation to the dual (aka auction) algorithm as well 
as some extensions. The talk will be self-contained and an attempt will 
be made to provide sufficient background on the topic of belief 
propagation.

The talk is based on joint work with Mohsen Bayati (Stanford) and Mayank 
Sharma (IBM).

Biography

Devavrat Shah is currently an assistant professor with department of 
EECS at MIT. His primary research interests are in the algorithms for 
networks, stochastic networks, statistical inference and network 
information theory.

Devavrat received his BTech degree in Computer Science from IIT-Bombay 
in 1999 with the honor of the President of India Gold Medal. He received 
his Ph.D. from the Computer Science at Stanford University in 2004. He 
was a post-doc in the Statistics department at Stanford and MSRI, 
Berkeley in 2004-05. He was co-awarded the IEEE INFOCOM best paper award 
in 2004 and ACM SIGMETRIC/Performance best paper award in 2006. He 
received 2005 George B. Dantzig best desseration award from INFORMS and 
NSF CAREER in 2006.