Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Message-Passing Algorithms for Network Scheduling

Devavrat Shah

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 can 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 is based on joint work with Mohsen Bayati (Stanford) and Mayank Sharma (IBM).

Problems with this site should be emailed to