Loading Events

« All Events

  • This event has passed.

GRASP Seminar: Devavrat Shah, Massachusetts Institute of Technology, “Network Algorithms: Decentralization and Efficiency,”

March 27, 2009 @ 11:00 am

Abstract: Contention resolution or resource allocation is a key operational (algorithmic) task that naturally arises in most of the networked scenarios. In most settings, such algorithms are required (or constrained) to be distributed and extremely simple while utilizing the resources efficiently. This tension between “implementability” and “performance” makes algorithm design (and analysis) quite challenging.

In this talk, I will discuss a novel method for designing distributed algorithms for a large class of (combinatorial) resource allocation problems that are provably efficient. As a special instance of our result, we resolve a long standing open problem about design of “Aloha-like” protocol for wireless networks. Key to our algorithm design is an “adiabetic theorem” (cf. quantum mechanics) like result for queuing networks.

Based on a joint work with J. Shin and S. Rajagopalan (both at MIT).


Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science at MIT. His research interests include statistical inference and network algorithms. He was co-awarded the IEEE INFOCOM best paper award in 2004 and ACM SIGMETRICS/Performance best paper award in 2006. He received 2005 George B. Dantzig best dissertation award from the INFORMS. He is the recipient of the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms.


March 27, 2009
11:00 am
Event Category: