The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm

Pierre Bertrand, Christoph Lenzen

In this work, we examine a generic class of simple distributed balls-into-bins algorithms. Exploiting the strong concentration bounds that apply to balls-into-bins games, we provid…