Devavrat Shah – Selected projects/publications

  1. 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.

    1. 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.

    2. 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:

    3. Hardness of Low Delay Network Scheduling, accepted to appear in IEEE Transactions on Information Theory, 2011.

  2. 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):

    1. Randomized scheduling algorithms for queueing networks, D. Shah and J. Shin, accepted to appear in Annals of Applied Probability, 2011.

    2. 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

    3. Distributed Random Access Algorithm: Scheduling and Congestion Control, L. Jiang, D. Shah, J. Shini and J. Walrand, IEEE Transactions on Information Theory, December, 2010.

  3. Gossip algorithms

    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.

    1. Randomized gossip algorithms, S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, IEEE Transaction on Information Theory & IEEE/ACM Transaction on Networking, 2006.

    2. Fast distributed algorithms for computing separable functions, D. Mosk-Aoyama and D. Shah, IEEE Transaction on Information Theory, 2008.

    3. Maximizing throughput in wireless networks via Gossip, Proceedings of ACM SIGMETRICS/Performance,2006 received Best Paper Award.

    4. Gossip Algorithms, D. Shah, Foundations and Trends in Networking, 2008.

    5. 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.

  4. 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).

    1. Maximum weight matching via max-product belief propagation, M. Bayati, D. Shah and M. Sharma, IEEE Transaction on Information Theory, 2008.

    2. Message passing for maximum weight independent set, S. Sanghavi, D. Shah and A. Willsky, IEEE Transaction on Information Theory, 2009.

    3. 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 networks.

    4. Message-passing in stochastic processing networks, D. Shah, Surveys in Operations Research and Management Science, 2011.

  5. 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.

    1. On capacity scaling in arbitrary wireless networks, U. Niesen, P. Gupta and D. Shah, IEEE Transaction on Information Theory, 2009.

    2. 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.

    3. 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.

    4. 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.

  6. People's Choice

    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.

    1. 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.

    2. 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.

    3. V. Farias, S. Jagabathula and D. Shah, Sparse Choice Model, Preprint, 2011.

  7. 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 engine Trumor.

    1. Rumors in a network: who's the culprit?, D. Shah and T. Zaman, IEEE Transaction on Information Theory, 2011.

  8. 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”.

    1. Breaking the simulation barrier: SRAM evaluation through Norm minimization, L. Dolecek, M. Qazi, D. Shah and A. Chandrakasen, proceedings of IEEE ICCAD, 2008.

    2. 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.