Self-stabilizing repeated balls-into-bins

DOI10.1007/s00446-017-0320-4zbMath1451.60080arXiv1501.04822OpenAlexW2779046011WikidataQ58219111 ScholiaQ58219111MaRDI QIDQ1733393

Gustavo Posta, Francesco Pasquale, Andrea E. F. Clementi, Emanuele Natale, Luca Becchetti

Publication date: 21 March 2019

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.04822

zbMATH Keywords

Markov chainsballs into binsparallel resource assignmentself-stabilizing systems

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Related Items

Mixing time for the repeated balls into bins dynamics ⋮ Propagation of chaos for a balls into bins model ⋮ Self-stabilizing repeated balls-into-bins ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Propagation of chaos for a general balls into bins dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a scalable and robust DHT
• Brownian models of feedforward queueing networks: Quasireversibility and product form solutions
• Self-stabilizing repeated balls-into-bins
• Efficient PRAM simulation on a distributed memory machine
• Randomized allocation processes
• Discovery Through Gossip
• Adversarial queuing theory
• Design and Analysis of Distributed Algorithms
• How asymmetry helps load balancing
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Efficient Information Exchange in the Random Phone-Call Model
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Self-stabilizing systems in spite of distributed control
• Balanced Allocations
• The Natural Work-Stealing Algorithm is Stable
• Balls and bins: A study in negative dependence
• Applied Probability and Queues
• Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input
• Self-stabilizing Balls & Bins in Batches
• Plurality Consensus in the Gossip Model
• Probability and Computing
• Balanced Allocations: The Heavily Loaded Case