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 way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2 n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.

Self-Stabilizing Repeated Balls-into-Bins / Becchetti, Luca; Andrea, Clementi; Emanuele, Natale; Francesco, Pasquale; Posta, Gustavo. - STAMPA. - 2015:(2015), pp. 332-339. (Intervento presentato al convegno SPAA '15 27th ACM Symposium on Parallelism in Algorithms and Architectures tenutosi a Portland; Oregon, USA) [10.1145/2755573.2755584].

### Self-Stabilizing Repeated Balls-into-Bins

#### Abstract

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 way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2 n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.
##### Scheda breve Scheda completa
2015
SPAA '15 27th ACM Symposium on Parallelism in Algorithms and Architectures
Balls into bins Markov chains; Parallel resource assignment; Analysis of Algorithmsand; Problem Complexity; Theory; Algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Self-Stabilizing Repeated Balls-into-Bins / Becchetti, Luca; Andrea, Clementi; Emanuele, Natale; Francesco, Pasquale; Posta, Gustavo. - STAMPA. - 2015:(2015), pp. 332-339. (Intervento presentato al convegno SPAA '15 27th ACM Symposium on Parallelism in Algorithms and Architectures tenutosi a Portland; Oregon, USA) [10.1145/2755573.2755584].
File allegati a questo prodotto
File
Becchetti_Self-Stabilizing-Repeated_2015.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Dimensione 555.34 kB
Becchetti_Frontespizio_Self-Stabilizing-Repeated_2015.pdf

accesso aperto

Tipologia: Altro materiale allegato
Dimensione 6.19 MB
Becchetti_Indice_Self-Stabilizing-Repeated_2015.pdf

accesso aperto

Tipologia: Altro materiale allegato
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/780594`