October 8, 2013
LIDS professor Devavrat Shah and alum Jinwoo Shin are awarded the 2013 Best Publication Award by the Applied Probability Society of INFORMS for their paper Random Scheduling Algorithm for Queueing Networks. The award recognizes an outstanding contribution to the field of Applied Probability during the years 2010--2013. From the citation:
The problem of dynamically allocating shared resources of limited capacity is fundamental to modern communication networks. It is difficult to design and analyze scheduling policies that address this problem in an optimal way. This has long been the subject of significant research in applied probability, leading to much progress in identifying optimal policies. Yet, most of these policies cannot be implemented in practice, due to algorithmic complexity and the need for coordinated scheduling decisions.
This paper develops a novel approach to the resource allocation problem by constructing randomized scheduling algorithms for two representative model classes: wireless networks and buffered circuit switched networks. These algorithms enable distributed implementation by requiring only local state information and few logical operations per scheduling decision. Moreover, it is shown that the algorithms are throughput optimal, meaning that the associated network Markov process is ergodic when the network is underloaded. These results are proved in part by making a fascinating connection between a Markovian dynamic on the space of schedules and mixing times of the Glauber dynamics on graphs.
Relying on deep insight into the nature of optimal scheduling policies, together with creative technical developments, the paper establishes an outstanding result in applied probability. As evidenced by a growing body of related work, the ideas in this paper are broadly applicable and can be expected to generate significant momentum in the area.
The APS Prize Committee:
Christian Gromoll, Chair
Assaf Zeevi
Bert Zwart