Balanced Allocations
From MaRDI portal
Publication:4268876
DOI10.1137/S0097539795288490zbMath0937.68053WikidataQ60960865 ScholiaQ60960865MaRDI QIDQ4268876
Anna R. Karlin, Andrei Z. Broder, Eli Upfal, Yossi Azar
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Stationary stochastic processes (60G10) Markov and semi-Markov decision processes (90C40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic processes (60G99)
Related Items
Efficient set intersection with simulation-based security, Balanced Allocation: Patience Is Not a Virtue, The power of two choices for random walks, Tight bounds for parallel randomized load balancing, D2B: A de Bruijn based content-addressable network, Sharp load thresholds for cuckoo hashing, Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables, The CNN problem and other \(k\)-server variants, Serving in the Dark should be done Non-Uniformly, New techniques and tighter bounds for local computation algorithms, Balanced allocation and dictionaries with tightly packed constant size bins, Practical load balancing for content requests in peer-to-peer networks, Choices and intervals, Fast flooding over Manhattan, Analysis of large urn models with local mean-field interactions, Unnamed Item, On weighted balls-into-bins games, Getting a Directed Hamilton Cycle Two Times Faster, Graphical balanced allocations and the (1 + β)-choice process, Random allocation of jobs with weights and precedence, Decentralized list scheduling, MDS coding is better than replication for job completion times, Decay of tails at equilibrium for FIFO join the shortest queue networks, Asymptotic independence of queues under randomized load balancing, The power of online thinning in reducing discrepancy, On the Power of Choice for Boolean Functions, NON-BACKTRACKING RANDOM WALKS MIX FASTER, The loss of serving in the dark, A geometric Achlioptas process, A lower bound on the queueing delay in resource constrained load balancing, The impact of line-sitting on a two-server queueing system, Long-term balanced allocation via thinning, Balanced allocation on hypergraphs, An improved version of cuckoo hashing: average case analysis of construction cost and search operations, On Accommodating Customer Flexibility in Service Systems, Unnamed Item, Given enough choice, simple local rules percolate discontinuously, The Power of Filling in Balanced Allocations, Orientability Thresholds for Random Hypergraphs, Convergence of Achlioptas Processes via Differential Equations with Unique Solutions, A Power-of-Two-Choices Unbalanced Allocation Process, Balls into bins with related random choices, Efficient set operations in the presence of malicious adversaries, Stability of join the shortest queue networks, Revisiting randomized parallel load balancing algorithms, Chains-into-bins processes, Balanced allocation: memory performance tradeoffs, A novel robust on-line protocol for load-balancing in structured peer-to-peer systems, A mean field model for a class of garbage collection algorithms in flash-based solid state drives, Self-stabilizing repeated balls-into-bins, Chains-into-Bins Processes, Choice-driven phase transition in complex networks, Analysis of randomized protocols for conflict-free distributed access, Balancing sums of random vectors, Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations, Randomized allocation processes, Balanced allocation on dynamic hypergraphs, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, Thresholds for extreme orientability, Cascade equilibrium strategies in a two-server queueing system with inspection cost, A generalization of multiple choice balls-into-bins: tight bounds, Layered hashing algorithm for real-time systems, Parallel randomized load balancing: a lower bound for a more general model, Scalable Multi-party Private Set-Intersection, Balls into bins via local search: Cover time and maximum load, Testing hypergraph colorability, Information spreading in dynamic graphs, The power of choice in growing trees, Anonymity and k-Choice Identities, Hamiltonicity thresholds in Achlioptas processes, Choice-memory tradeoff in allocations, Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses, Rumor spreading in random evolving graphs, Load balancing under \(d\)-thinning, Self-stabilizing balls and bins in batches. The power of leaky bins, Cuckoo hashing: Further analysis, Multiple choice tries and distributed hash tables, Balanced Allocation on Graphs: A Random Walk Approach, Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process, Power-of-d-Choices with Memory: Fluid Limit and Optimality, Throughput and delay optimality of power-of-\(d\) choices in inhomogeneous load balancing systems, On the \(k\)-orientability of random graphs, The power of thinning in balanced allocation, Revisiting Randomized Parallel Load Balancing Algorithms, A Generalized Coupon Collector Problem, Range minimum queries in minimal space, Singletons for simpletons revisiting windowed backoff with Chernoff bounds, Group service system with three queues and load balancing, Delaying satisfiability for random 2SAT, Two-way chaining for non-uniform distributions, On the power of two choices: balls and bins in continuous time, On the drift of short schedules., Power-of-two sampling in redundancy systems: the impact of assignment constraints, Balanced routing of random calls, Dynamic averaging load balancing on cycles
