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

BECCHETTI, Luca
;
Gustavo Posta
2015

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.
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 Dimensione Formato  
Becchetti_Self-Stabilizing-Repeated_2015.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 555.34 kB
Formato Adobe PDF
555.34 kB Adobe PDF   Contatta l'autore
Becchetti_Frontespizio_Self-Stabilizing-Repeated_2015.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 6.19 MB
Formato Adobe PDF
6.19 MB Adobe PDF
Becchetti_Indice_Self-Stabilizing-Repeated_2015.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 67.5 kB
Formato Adobe PDF
67.5 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/780594
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact