Devavrat Shah – Selected projects/publications
Optimal queue-based myopic policy: fluid model and heavy traffic
The primary goal of this collection of works is to identify optimal scheduling
policies for stochastic resource allocation modeled as stochastic processing
networks (Harrison (2000)). The maximum weight policy proposed by Tassiulas
and Ephremides (1992) has been of central attention due to they being myopic and
throughput optimal for a large class of stochastic processing networks including
switched networks. Their heavy traffic optimality was established under the so
called ‘resource pooling’ condition in a collection of works (by Stolyar (2004),
Dai and Lin (2005, 08)).
Our work attempts to go beyond these results by developing fluid and heavy traffic
approximation for the maximum weight policy for switched networks. In particular, we
find that a particular member of the maximum weight class of policy (we call MW-0+)
is optimal with respect to critical fluid model and overloaded fluid model for a
large class of network instances. The following papers provide detailed description
of these results.
Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse, D. Shah and D. J. Wischik, accepted to appear in Annals of Applied Probability, 2011.
Fluid models of congestion collapse in overloaded switched networks, D. Shah and D. J. Wischik, accepted to appear in Queueing Systems, 2011.
An interesting interplay between queue-size, complexity and capacity in such constrained
queueing networks is at play. The following work explores the tension between average queue-size
and complexity of scheduling algorithm:
Hardness of Low Delay Network Scheduling, accepted to appear in IEEE Transactions on Information Theory, 2011.
Medium access using queues
The search for myopic, queue-based policy with excellent performance has
resulted in identification of (a member of) maximum weight policy (class)
as desirable. However, implementing such a policy in a network requires
solving a network-wide optimization problem in each time instance. An
important instance of this is scheduling or medium access in a wireless
network (or the so call MAC protocol). Indeed, the maximum weight policy
suggests solving the maximum weight independent set in the network graph
which is computationally hard (and hard to approximate) problem. In practice,
one wishes to design a MAC protocol that is as simple as the standard
randomized back-off protocol.
To address this acute tension between performance and implementability,
we have developed a method for designing a randomized, back-off MAC
protocol that utilizes a function of its own queue-size as the back-off
probability to access medium. The appropriate choice of function (see
discussion in papers below) leads to a throughput optimal algorithm
for any network. This distributed protocol is oblivious to network
structure or the imposed demand. The protocol guarantees positive recurrence
of the underlying network Markov process which provides strong throughput
optimality, e.g. it is robust against variations in traffic demand rates.
The protocol is shown to posses such desireable properties in presence of
perfect carrier sense (first paper) or delayed carrier sense (second paper)
information (collision model).
This work embodies the following philosophy: a pragmatic way to develop
theory of high-performance implementable algorithms is to search for
provably efficient algorithm in the design space of already implemented
protocols (this collection of works received ACM Sigmetrics 2009 Student
Paper Award and MIT's George Sprowl's Best Thesis Award):
Randomized scheduling algorithms for queueing networks, D. Shah and J. Shin, accepted to appear in Annals of Applied Probability, 2011.
Efficient Distributed Medium Access, D. Shah, J. Shin and P. Tetali, accpted to appear in Proceedings of IEEE FOCS, 2011.
Independent to this work, another exciting algorithmic method (distinctly different from
the above) has been developed by Libin Jiang
and Jean Walrand. However, proof techniques do
have similarities. See, for example
Distributed Random Access Algorithm: Scheduling and Congestion Control,
L. Jiang, D. Shah, J. Shini and J. Walrand, IEEE Transactions on Information Theory, December, 2010.
Gossip algorithms have played an important role in architecting
infrastructure-less communication networks such as the peer-to-peer
network, developing framework for distributed control and understanding
behavioral models for societal networks. One of the key question
concerns how does the network structure play role in determining the
computation time for randomized gossip-like algorithms for information
diffusion, computing network-wide optimization for networked control or
reaching consensus. This line of inquiry has been central to variety
of disciplines over decades. For example, thesis of Tsitsiklis (1984),
book by Bertsekas and Tsitsiklis (1989), model of Vicsek (1993) and
a flurry of recent results.
Our main results in addressing the above intellectual challenges are
two folds: first, we establish that the time for a single piece of information
to spread in the network (one piece broadcast) scales inversely proportional
to “conductance” of the network; second, the time it takes for spread of
one piece of information is essentially what it takes to computer summation
of numbers or averaging or equivalently separable functions. Given that
this is primary “sub routine” in various distributed optimization problems,
in all such scenarios, (inverse of) conductance determines the dependence of
gossip-based network computation on the network structure.
Randomized gossip algorithms, S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, IEEE Transaction on Information Theory & IEEE/ACM Transaction on Networking, 2006.
Fast distributed algorithms for computing separable functions, D. Mosk-Aoyama and D. Shah, IEEE Transaction on Information Theory, 2008.
Maximizing throughput in wireless networks via Gossip,
Proceedings of ACM SIGMETRICS/Performance,2006 received Best Paper Award.
Gossip Algorithms, D. Shah, Foundations and Trends in Networking, 2008.
Dynamics in Congestion Games, D. Shah and J. Shin, Proceedings of ACM SIGMETRICS, 2010.
Recent sequence of follow on works by Flavio Chierichetti, Silvio Lattanzi and
Alessandro Panconesi (2010) investigates relation between diffusion time and inverse of
conductance (defined somewhat differently) for uniform gossip. It also establishes
curious connection between such qualitative relation of information diffusion time
under randomized gossip and graph sparsification.
Belief propagation for optimization
Graphical model has served as an excellent (universal) abstraction for
representing joint distributions over a collection of variables in a succint manner.
Two computational problems that are of primary interest are (a) computing marginals,
of variables, and (b) computing assignment to variables with maximal probability.
These problems are computationally hard in general. The Belief propagation (BP)
has emerged as a successful heuristic for these problems. Despite the fact that
BP has been designed to work primarily for tree graphical models, the excellent
performance of BP for many practical scenarios has been quite surprising.
The goal of this work to understand why BP algorithm works well for graphical
models cycles. The primarily conclusion of our work listed below is that for
a large class of optimization problems (equivalently finding assignment with
maximal probability), BP is an exact algorithm for any graphical structure.
This class of problems include the network flow problems. Primarily BP
finds correct answers despite the presence of cycles because the optimal
assignment is characterized by “cycle conditions”. And for these problems,
BP can find such an assignment in polynomial time (with minor modification,
it results in strongly polynomial time algorithm).
Maximum weight matching via max-product belief propagation, M. Bayati, D. Shah and M. Sharma, IEEE Transaction on Information Theory, 2008.
Message passing for maximum weight independent set, S. Sanghavi, D. Shah and A. Willsky, IEEE Transaction on Information Theory, 2009.
Belief propagation for min-cost network flow: convergence and correctness, D. Gamarnik, D. Shah and Y. Wei, accepted to appear in Operations Research, 2011.
As discussed above, a good myopic policy for a large class of
stochastic resource allocation problems arising in networks require solving
network-wide optimization problem while implementation concerns require such
algorithm to be simple and distributed. On one hand, BP is a generic, of-the-shelf
heuristic and makes it easy to utilize for a network architect. On the other
hand, it seems to perform really well for reasons discussed above. The following
survey discusses role of BP like message-passing algorithm in stochastic
Message-passing in stochastic processing networks, D. Shah, Surveys in Operations Research and Management Science, 2011.
Scaling laws for wireless networks
The basic question of network information theory is to determine
the capacity region of arbitrary wireless network. The prior work in scaling
laws starting with that of Gupta and Kumar (2000) has primarily
been about determining the capacity region scaling along one direction
(projection of n^2 dimensional convex set on one particular dimension
for an n node wireless network). Our result characterizes the entire
capacity region up to scaling for a network when nodes are placed
randomly and wireless channels are models as Gaussian Fading Channels.
Key insight is that capacity of wireless network is equivalent to a
wired tree network.
On capacity scaling in arbitrary wireless networks, U. Niesen, P. Gupta and D. Shah, IEEE Transaction on Information Theory, 2009.
The balanced unicast and multicast capacity regions of large wireless networks, U. Niesen, P. Gupta and D. Shah, IEEE Transaction on Information Theory, 2010.
Earlier work on scaling law, under protocol communication model, allows precise
characterization of tradeoff between capacity scaling and delay scaling for static
and mobile wireless networks.
Throughput and delay in wireless networks – Part I: Fluid case, A. El Gamal, J. Mammen, D. Shah and B. Prabhakar, IEEE Transaction on Information Theory & IEEE/ACM Transaction on Networking, 2006. Preliminary version received IEEE Infocom 2004 Best Paper Award.
Throughput and delay in wireless networks – Part II: constant-size packet, A. El Gamal, J. Mammen, D. Shah and B. Prabhakar, IEEE Transaction on Information Theory, 2006.
A designer of a social system faces challenge due to the uncertainty in people’s preferences. Classically,
expensive census or polls been used to combat this uncertainty and understand people’s choice for making
business decisions or finalizing policies. These days, all form of social information gets recorded instantly.
This provides us with tremendous opportunity to track people’s choice dynamically, at a much finer scale,
so that we can run businesses better or provide accurate personal recommendations. For example, a transaction
representing car purchase from a dealership or clicking on one of the ad reveals liking
for that particular car or ad over others “on display”. Therefore, challenge lies in learning people’s
preferences over all possible choices from such partial preferences. Formally, the question boils down
to learning choice model, i.e. distribution over permutations (preferences) of objects of interest,
from partial comparisons. The celebrated theory of choice modeling spanning psychology, social sciences
and economics is concerned with the same quest but restricts itself to learning distributions from
a specific parametric class (e.g. Thurstone (1927)). To overcome limitations of parametric models,
we have initiated a formal inquiry of learning non-parametric choice models from its marginal
information or more generally from partial Fourier coefficients. Key contribution is discovery of
what we call “signature condition” (SC): when it holds, sparsest choice model consistent with
observations can be recovered exactly in computationally efficient manner. An important intellectual
byproduct is this discovery of the SC condition as a distinct alternative to the Restricted Null Space
(RNS) condition for sparse model recovery from few observations; RNS or its variants are the primary
conditions utilized in the popular compressive sensing literature (we have proved that RNS is not
useful in our setting). We have taken theory of non-parametric choice models to practice by developing
a robust approach for revenue estimation based on transactions. In addition to establishing theoretical
soundness, we have verified it on real data suggesting significant improvement over the state-of-art
alternatives. We have also developed a collaborative decision making tool Celect
encapsulating the philosophy that partial preferences do have a lot of useful information.
Inferring rankings using constrained sensing, S. Jagabathula and D. Shah, accepted to appear in IEEE Transaction on Information Theory, 2011. Preliminary version received NIPS 2008 Outstanding Paper Award.
V. Farias, S. Jagabathula and D. Shah, A Nonparametric Approach to Modeling Choice with Limited Data, Under review for Management Science, Submitted in October 2009, revised in October 2010 and June 2011. Preliminary version received INFORMS MSOM Student Paper Competition Award.
V. Farias, S. Jagabathula and D. Shah, Sparse Choice Model, Preprint, 2011.
Searching The Source
Uncontrolled or diffusive spread of information in society is natural – it is how a Tweet becomes viral, or
malware like Stuxnet infects nuclear reactors. Given such importance of information diffusion, it is natural
to understand role played by the network topology in source detection given trail of information diffusion,
e.g. can source of Stuxnet be found using knowledge of infected nodes, or can its spreading be engineered so
that it remains hidden. Our key finding is the following Meta-principle: if network topology expands faster than
a line-graph, then source can be detected with high enough probability irrespective of the size of the network.
That is, to keep a source hidden, it is necessary to spread information slowly or effectively spread it along
line-like topology. Formally, we have developed an exciting theory for source estimation based on “rumor infected”
nodes, which draws connections to classical theory of Generalized Polya’s Urn, counting linear extensions of a
partial order and network centrality. We have taken it to practice by building a Twitter search
Rumors in a network: who's the culprit?, D. Shah and T. Zaman, IEEE Transaction on Information Theory, 2011.
Statistics for circuits
The advent of deep submicron technology for VLSI circuit design and subsequently lack of deterministic circuit
models has made the task of efficient algorithm design for evaluating yield (probability of failure) of a statistical
circuit of utmost importance in the CAD industry. I have developed such a method built on intuition “rare events happen
only in a typical manner” derived from the classical Large Deviations Theory. It uses importance sampling and
optimization for accurate evaluation of yield of a large circuit – for the prototypical case of SRAM cell,
the simulation speed up is 10000 times – 2 months of simulation time reduced to 2 minutes! The end product
is a MATLAB based “simulation tool”.
Breaking the simulation barrier: SRAM evaluation through Norm minimization, L. Dolecek, M. Qazi, D. Shah and A. Chandrakasen, proceedings of IEEE ICCAD, 2008.
Loop flattening and spherical importance sampling: a highly efficient model reduction technique for SRAM yield analysis, M. Qazi, M. Titekar, L. Dolecek, D. Shah and A. Chandrakasen, proceedings of DATE, 2010.