hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM,Mathematics, Probability, math.PR
Abstract:
In this paper we propose an algorithm for allocating $n$ sequential balls
into $n$ bins that are organized as a $n$-vertex $d$-regular graph $G$, where
$d\ge3$ can be any integer. Let $L$ be a given positive integer. In each round
$t$, $1\leq t\leq n$, ball $t$ picks a node of $G$ uniformly at random and
performs a non-backtracking random walk (NBRW) of length $L$ from the chosen
node. Then it deterministically selects a subset of the visited nods as the
potential choices and allocates itself on one of the choices with minimum load
(ties are broken uniformly at random). Suppose that $G$ has girth at least
$\Omega(L(\log L+\log\log d))$. We establish an upper bound for the maximum
number of balls at any bin after allocating $n$ balls by the algorithm, called
{\it maximum load}, in terms of $L$ with high probability. We also show that
the upper bound is at most an $O(\log L+\log\log d)$ factor above the lower
bound that is proved for the algorithm. In particular we show that if $G$ has
girth at least $(\log n)^{\frac{1+\epsilon}{2}} $, for any constant
$\epsilon\in(0,1]$ and we set $L=\lfloor (\log n)^{\frac{1+\delta}{2}}
\rfloor$, where $0<\delta<\epsilon$ is a constant, then the maximum load is
bounded by $O(1/\delta)$ with high probability. Finally, we present some more
general results which hold for a variant of this algorithm.
