{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:30:29Z","timestamp":1777105829967,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,12,18]],"date-time":"2017-12-18T00:00:00Z","timestamp":1513555200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Max Planck Institute for Informatics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00446-017-0320-4","type":"journal-article","created":{"date-parts":[[2017,12,18]],"date-time":"2017-12-18T14:43:56Z","timestamp":1513608236000},"page":"59-68","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Self-stabilizing repeated balls-into-bins"],"prefix":"10.1007","volume":"32","author":[{"given":"L.","family":"Becchetti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8755-3892","authenticated-orcid":false,"given":"E.","family":"Natale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Pasquale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Posta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,18]]},"reference":[{"issue":"3","key":"320_CR1","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1137\/S0097539703437831","volume":"34","author":"A Anagnostopoulos","year":"2005","unstructured":"Anagnostopoulos, A., Kirsch, A., Upfal, E.: Load balancing in arbitrary network topologies with stochastic adversarial input. SIAM J. Comput. 34(3), 616\u2013639 (2005)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"320_CR2","doi-asserted-by":"publisher","first-page":"1260","DOI":"10.1137\/S0097539701399551","volume":"32","author":"P Berenbrink","year":"2003","unstructured":"Berenbrink, P., Friedetzky, T., Goldberg, L.A.: The natural work-stealing algorithm is stable. SIAM J. Comput. 32(5), 1260\u20131279 (2003)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"320_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"EW Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643\u2013644 (1974)","journal-title":"Commun. ACM"},{"key":"320_CR4","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-Stabilization","author":"S Dolev","year":"2000","unstructured":"Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)"},{"key":"320_CR5","doi-asserted-by":"crossref","unstructured":"Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 119\u2013131. ACM (1990)","DOI":"10.1145\/93385.93409"},{"key":"320_CR6","doi-asserted-by":"publisher","DOI":"10.1002\/0470072644","volume-title":"Design and analysis of distributed algorithms","author":"N Santoro","year":"2006","unstructured":"Santoro, N.: Design and analysis of distributed algorithms. Wiley, Hoboken (2006)"},{"key":"320_CR7","volume-title":"Distributed algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed algorithms. Morgan Kaufmann, Burlington (1996)"},{"key":"320_CR8","doi-asserted-by":"crossref","unstructured":"Cooper, C.: Random walks, interacting particles, dynamic networks: randomness can be helpful. In: Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS, vol. 6796, pp. 1\u201314. Springer (2011)","DOI":"10.1007\/978-3-642-22212-2_1"},{"issue":"4","key":"320_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1109\/71.995817","volume":"13","author":"S Ikeda","year":"2002","unstructured":"Ikeda, S., Kubo, I., Okumoto, N., Yamashita, M.: Fair circulation of a token. IEEE Trans. Parallel Distrib. Syst. 13(4), 367\u2013372 (2002)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"320_CR10","volume-title":"Markov chains and mixing times","author":"DA Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Society, Providence (2009)"},{"key":"320_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and computing: randomized algorithms and probabilistic analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge (2005)"},{"key":"320_CR12","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R.: Plurality consensus in the gossip model. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 371\u2013390. SIAM (2015)","DOI":"10.1137\/1.9781611973730.27"},{"key":"320_CR13","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czyzowicz, J., Els\u00e4sser, R., Gasieniec, L.: Efficient information exchange in the random phone-call model. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), LNCS, vol. 6198, pp. 127\u2013138. Springer (2010)","DOI":"10.1007\/978-3-642-14162-1_11"},{"key":"320_CR14","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Kaaser, D.: On the influence of graph density on randomized gossiping. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 521\u2013531 (2015)","DOI":"10.1109\/IPDPS.2015.32"},{"key":"320_CR15","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201312. ACM (1987)","DOI":"10.1145\/41840.41841"},{"key":"320_CR16","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 565\u2013574. IEEE (2000)"},{"key":"320_CR17","doi-asserted-by":"crossref","unstructured":"Becchetti L., Clementi A., Natale E., Pasquale F., Posta G.: Self-stabilizing repeated balls-into-bins. In: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 332\u2013339. ACM (2015)","DOI":"10.1145\/2755573.2755584"},{"key":"320_CR18","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., Wastell, C.: Self-stabilizing balls and bins in batches: the power of leaky bins (extended abstract). In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 83\u201392. ACM (2016)","DOI":"10.1145\/2933057.2933092"},{"issue":"1","key":"320_CR19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y Azar","year":"1999","unstructured":"Azar, Y., Broder, A.Z., Karlin, A., Upfal, E.: Balanced allocations. SIAM J. Comput. 29(1), 180\u2013200 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"320_CR20","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: the heavily loaded case. SIAM J. Comput. 35(6), 1350\u20131385 (2006)","journal-title":"SIAM J. Comput."},{"key":"320_CR21","doi-asserted-by":"crossref","unstructured":"Raab, M., Steger, A.: \u201cBalls into bins\u201d a simple and tight analysis. In: Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), LNCS, vol. 1518, pp. 159\u2013170. Springer (1998)","DOI":"10.1007\/3-540-49543-6_13"},{"issue":"4\u20135","key":"320_CR22","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/BF01940878","volume":"16","author":"RM Karp","year":"1996","unstructured":"Karp, R.M., Luby, M., auf\u00a0der Heide, F.Meyer: Efficient pram simulation on a distributed memory machine. Algorithmica 16(4\u20135), 517\u2013542 (1996)","journal-title":"Algorithmica"},{"key":"320_CR23","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via xorsat. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), LNCS, vol. 6198, pp. 213\u2013225. Springer (2010)","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"320_CR24","doi-asserted-by":"crossref","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 238\u2013247. ACM (1995)","DOI":"10.1145\/225058.225131"},{"key":"320_CR25","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Khodamoradi, K., Sauerwald, T., Stauffer, A.: Balls-into-bins with nearly optimal load distribution. In: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 326\u2013335. ACM (2013)","DOI":"10.1145\/2486159.2486191"},{"issue":"10","key":"320_CR26","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1109\/71.963420","volume":"12","author":"M Mitzenmacher","year":"2001","unstructured":"Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst. 12(10), 1094\u20131104 (2001)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"320_CR27","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Prabhakar, B., Shah, D.: Load balancing with memory. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 799\u2013808. IEEE (2002)","DOI":"10.1109\/SFCS.2002.1182005"},{"issue":"4","key":"320_CR28","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1145\/792538.792546","volume":"50","author":"B V\u00f6cking","year":"2003","unstructured":"V\u00f6cking, B.: How asymmetry helps load balancing. J. ACM 50(4), 568\u2013589 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"320_CR29","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/s00224-008-9099-9","volume":"45","author":"B Awerbuch","year":"2009","unstructured":"Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. Theory Comput. Syst. 45(2), 234\u2013260 (2009)","journal-title":"Theory Comput. Syst."},{"key":"320_CR30","volume-title":"Applied Probability and Queues","author":"S Asmussen","year":"2003","unstructured":"Asmussen, S.: Applied Probability and Queues. Springer, Berlin (2003)"},{"issue":"2","key":"320_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1214\/aoap\/1177005704","volume":"2","author":"JM Harrison","year":"1992","unstructured":"Harrison, J.M., Williams, R.J.: Brownian models of feedforward queueing networks: quasireversibility and product form solutions. Ann. Appl. Probab. 2(2), 263\u2013293 (1992)","journal-title":"Ann. Appl. Probab."},{"issue":"1","key":"320_CR32","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/363647.363659","volume":"48","author":"A Borodin","year":"2001","unstructured":"Borodin, A., Kleinberg, J., Raghavan, P., Sudan, M., Williamson, D.P.: Adversarial queuing theory. J. ACM 48(1), 13\u201338 (2001)","journal-title":"J. ACM"},{"key":"320_CR33","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Friedetzky, T., Vedenskaya, N.D.: Infinite parallel job allocation. In: Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 99\u2013108. ACM (2000)","DOI":"10.1145\/341800.341813"},{"key":"320_CR34","doi-asserted-by":"crossref","unstructured":"Adler, M., Berenbrink, P., Schr\u00f6der, K.: Analyzing an infinite parallel job allocation process. In: Proceedings of the European Symposium on Algorithms (ESA), LNCS, vol. 1461, pp. 417\u2013428. Springer (1998)","DOI":"10.1007\/3-540-68530-8_35"},{"key":"320_CR35","doi-asserted-by":"crossref","unstructured":"Czumaj, A.: Recovery time of dynamic allocation processes. In: Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 202\u2013211. ACM (1998)","DOI":"10.1145\/277651.277686"},{"key":"320_CR36","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Stemann, V.: Randomized allocation processes. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 194\u2013203 (1997)","DOI":"10.1109\/SFCS.1997.646108"},{"key":"320_CR37","doi-asserted-by":"crossref","unstructured":"Cole, R., Frieze, A., Maggs, B., Mitzenmacher, M., Richa, A.W., Sitaraman, R., Upfal, E.: On balls and bins with deletions. In: Randomization and Approximation Techniques in Computer Science, LNCS, pp. 145\u2013158. Springer (1998)","DOI":"10.1007\/3-540-49543-6_12"},{"issue":"2","key":"320_CR38","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"DP Dubhashi","year":"1998","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99\u2013124 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"320_CR39","doi-asserted-by":"publisher","first-page":"502","DOI":"10.2307\/1426671","volume":"14","author":"B Hajek","year":"1982","unstructured":"Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3), 502\u2013525 (1982)","journal-title":"Adv. Appl. Probab."},{"issue":"3","key":"320_CR40","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1002\/rsa.20621","volume":"48","author":"B Haeupler","year":"2016","unstructured":"Haeupler, B., Pandurangan, G., Peleg, R., Rajaraman, D., Sun, Z.: Discovery through gossip. Random Struct. Algorithms 48(3), 565\u2013587 (2016)","journal-title":"Random Struct. Algorithms"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0320-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0320-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0320-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T23:32:01Z","timestamp":1751153521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0320-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,18]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["320"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0320-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,18]]},"assertion":[{"value":"14 September 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}