[Colloq] Reminder: Devavrat Shah - Today 12pm

[Rachel Kalweit]

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.









_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq