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 Oplog nq. 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(nlog2 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.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Posta, G. (2015). Self-stabilizing repeated balls-into-bins. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp.332-339). Association for Computing Machinery [10.1145/2755573.2755584].

Self-stabilizing repeated balls-into-bins

CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
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 Oplog nq. 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(nlog2 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.
27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
usa
2015
ACM Special Interest Groups on Algorithms and Computation Theory (SIGACT)
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
Settore MAT/06 - Probabilita' e Statistica Matematica
English
Balls into bins; Markov chains; Parallel resource assignment; Self-stabilizing systems;
Intervento a convegno
Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Posta, G. (2015). Self-stabilizing repeated balls-into-bins. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp.332-339). Association for Computing Machinery [10.1145/2755573.2755584].
Becchetti, L; Clementi, A; Natale, E; Pasquale, F; Posta, G
File in questo prodotto:
File Dimensione Formato  
bcnpp_spaa15.pdf

accesso solo dalla rete interna

Licenza: Copyright dell'editore
Dimensione 555.34 kB
Formato Adobe PDF
555.34 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/2108/187100
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact