\input zb-basic
\input zb-ioport
\iteman{io-port 06055962}
\itemau{Berenbrink, Petra; Brinkmann, Andr\'e; Friedetzky, Tom; Nagel, Lars}
\itemti{Balls into bins with related random choices.}
\itemso{J. Parallel Distrib. Comput. 72, No. 2, 246-253 (2012).}
\itemab
Summary: We consider a variation of classical balls-into-bins games. We randomly allocate $m$ balls into $n$ bins. Following {\it P. B. Godfrey}'s model [in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms (SODA) 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 511--517 (2008; Zbl 1192.90225)], we assume that each ball $i$ comes with a $\beta $-balanced set of clusters $\mathcal{B}_{i}=\{B_{1},\dots ,B_{s_{i}}\}$, each containing a logarithmic number of balls. The condition of $\beta $-balancedness essentially enforces a uniform-like selection of bins for the clusters, where the parameter $\beta \ge 1$ governs the deviation from uniformity. Each ball $i=1,\dots ,m$, in turn, runs the following protocol: (i) it i.u.r. (independently and uniformly at random) chooses a cluster of bins $B_{i}\in \mathcal{B}_{i}$, and (ii) it i.u.r. chooses one of the empty bins in $B_{i}$ and allocates itself to it. Should the cluster not contain at least a single empty bin, then the protocol fails. If the protocol terminates successfully, that is, every ball has indeed been able to find at least one empty bin in its chosen cluster, then this will obviously result in a maximum load of one. The main goal is to find a tight bound on the maximum number of balls, $m$, so that the protocol terminates successfully with a high probability. In this paper, we improve on Godfrey's result and show that $m=\frac{n}{\Theta(\beta)}$. We use a more relaxed notion of balancedness than [loc. cit.] and show that our upper bounds hold for this type of balancedness. It even holds when we generalise the model and allow runs where each ball $i$ tosses a coin and it copies the previous ball's choice $B_{i - 1}$ with constant probability $p_{i}$ ($0<p_{i}\le 1$). With the remaining probability the ball uses the protocol as described above.
\itemrv{~}
\itemcc{}
\itemut{stochastic processes; load balancing; balls into bins; peer-to-peer}
\itemli{doi:10.1016/j.jpdc.2011.10.006}
\end