Derandomized Load Balancing using Random Walks

Friday, April 26, 2019 - 1:00pm to Saturday, April 27, 2019 - 1:55pm

Event Calendar Category

Other LIDS Events

Speaker Name

Vijay Subramanian

Affiliation

University of Michigan

Building and Room Number

32-D677

Abstract

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 dresource 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 logn/logd+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 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 power-of-d choices where the sampling of the d resources at each time is based on the locations ofd 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 power-of-d, so that the maximum load is bounded by log log n/log d+ Θ(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 derandomization of power-of-d choices.

For the multi-server systems 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, and is based on https://arxiv.org/pdf/1810.02722.pdf, https://arxiv.org/pdf/1901.09094.pdf and a recently accepted paper at ACM SIGMETRICS 2019 and ACM POMACS.

Biography

Vijay Subramanian is an Associate Professor in the EECS Department at the University of Michigan. My main research interests are in stochastic modeling, communications, information theory, and applied mathematics. A large portion of my past work has been on probabilistic analysis of communication networks, especially the analysis of scheduling and routing algorithms. In the past, I have also done some work with applications in immunology and coding of stochastic processes. My current research interests are on game-theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.