Home » Publication » 13879

Dettaglio pubblicazione

2019, DISTRIBUTED COMPUTING, Pages 59-68 (volume: 32)

Self-stabilizing repeated balls-into-bins (01a Articolo in rivista)

Becchetti L., Clementi A., Natale E., Pasquale F., Posta G.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary fashion. In every subsequent round, one ball is extracted from each non-empty bin according to some fixed strategy (random, FIFO, etc), and re-assigned to one of the n bins uniformly at random. We define a configuration legitimate if its maximum load is (Formula presented.). We prove that, starting from any configuration, the process converges to a legitimate configuration in linear time and then only takes on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). This implies that the process is self-stabilizing and that every ball traverses all bins within (Formula presented.) rounds, w.h.p.
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma