Self-stabilizing balls and bins in batches. The power of leaky bins

DOI10.1007/s00453-018-0411-zzbMath1401.68018OpenAlexW2296336213MaRDI QIDQ1799218

Lars Nagel, Frederik Mallmann-Trenn, Tom Friedetzky, Petra Berenbrink, Peter Kling, Chris Wastell

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0411-z

zbMATH Keywords

positive recurrentmaximum loadself-stabilizing2-choiceballs-into-bins

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14)

Cites Work

• Unnamed Item
• Unnamed Item
• Randomized allocation processes
• Multiple-Choice Balanced Allocation in (Almost) Parallel
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Balanced Allocations
• Algorithmic analysis of the BMAP/D/k system in discrete time
• Parallel randomized load balancing
• Topics in the Constructive Theory of Countable Markov Chains
• Balanced Allocations: A Simple Proof for the Heavily Loaded Case
• Balanced Allocations: The Heavily Loaded Case

This page was built for publication: Self-stabilizing balls and bins in batches. The power of leaky bins