Loading Events

« All Events

  • This event has passed.

CESG Fishbowl Seminar: “Derandomized Load Balancing Using Random Walks”

May 9 @ 11:00 am - 12:00 pm


Fishbowl, Room 333, Wisenbaker Engineering Building


Dr. Vijay Subramanian
Associate Professor in EECS Department at the University of Michigan



Load balancing resources with algorithms that have low communication complexity, low computation complexity and low memory utilization is the Holy Grail for many large-scale and distributed systems, such as distributed hash-tables and large-scale cloud computing systems. A well-known scheme in the area is the power-of-d choices scheme, wherein $d$ resource elements from a total of $n$ are sampled independently and uniformly at random, and an assignment is made to the least loaded resource. In the standard ball-in-bins experiment, that models the distributed hash-tables problem, it was shown by Azar et al. that this scheme yields a maximum load of $\log\log n/\log d+O(1)$ with high probability. Similar performance is obtained for the dynamic version of the problem by Vvedenskaya et al. and Mitzenmacher, which models assignment in large-scale multi-server systems.

Subsequent work analyzed the model when at each time the $d$ resources are sampled through some correlated or non-uniform way. However, the case when the sampling for different resources are correlated in time has rarely been investigated. In this work, we present analysis of a new scheme for both the allocation problems. We assume that there is an underlying $k$-regular graph $G$ connecting the resources. Then the new scheme is a variant of \emph{power-of-$d$ choices} where the sampling of the $d$ resources at each time is based on the locations of $d$ independently moving non-backtracking random walkers on the graph $G$.

For the balls-in-bins problem, we show that under some conditions for the underlying graph that can be summarized as the graph being a high girth expander, the scheme can perform as well as \emph{power-of-$d$}, so that the maximum load is bounded by $\frac{\log\log n}{\log d}+O(1)$ with high probability. We further characterize the conditions of the graph in which the maximum load is bounded by $\Theta(\log \log n)$. Our results resolve Alon et al.’s open question in the balls-in-bins setting, and thus the random walk based assignment can be seen as a \emph{derandomization} of \emph{power-of-$d$ choices}.

For the mlti-server system’s setting, with similar assumptions on the graph as above, we show that under the random-walk based sampling scheme, as $n$ increases without bound, the dynamics of the queuing system converges to the same deterministic ordinary differential equation (ODE) system that is the mean-field limit for the power-of-$d$ choices scheme. We also show that the system is stable under the proposed scheme for each $n$, and the stationary distribution of the system converges to the fixed point of the ODE system. The proof of each step involves several methodological challenges as the processes being studied are non-Markovian.

This is joint work with Dengwang Tang at the University of Michigan.



Vijay Subramanian is an Associate Professor in the EECS Department at the University of Michigan since 2014. After graduating with his Ph.D. from UIUC in 1999, he did a few stints in industry, research institutes and universities in the US and Europe before his current position. His main research interests are in stochastic modeling, communications, information theory and applied mathematics. A large portion of his past work has been on probabilistic analysis of communication networks, especially analysis of scheduling and routing algorithms. In the past, he has also done some work with applications in immunology and coding of stochastic processes. His current research interests are on game theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.










Light Snacks Provided


May 9
11:00 am - 12:00 pm