How asymmetry helps load balancing

By Berthold Vöcking. 1999

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “example, in left-hashing [73] the item is placed on the leftmost bucket.”
Theory and Practice of Bloom Filters for Distributed Systems (2012, methodology): “[18] elaborate on this observation and propose the always-g oleft algorithm (ord-left hashing scheme) to break ties when inserting (chained) elements to the least loaded one among t he d partitioned candidates.”
Simple Load Balancing for Distributed Hash Tables (2003, background): “Vocking uses an improved tiebreaking scheme to improve the d-choice balls and bins result [11]; his extension can also be applied here.”
FlowRadar: A Better NetFlow for Data Centers (2016, background): “It is impossible to mirror all the packets because it takes too much bandwidth to mirror the traffic, and too many storage and computing resources at the remote collector to analyze every packet.”
An Improved Construction for Counting Bloom Filters (2006, methodology): “Our approach makes use of d-left hashing, a variation of the balanced allocations paradigm [1] due to Vöcking [20], which we now recall.”
Heavy-Hitter Detection Entirely in the Data Plane (2016, background): “Along similar lines, hashing schemes like cuckoo hashing [33] and d-left hashing [43] can keep per-flow state memory-efficiently, while providing fast lookups on the state.”
An Analysis of Random-Walk Cuckoo Hashing (2009, methodology): “Cuckoo hashing [12] provides a useful methodology for building practical, high-performance hash tables by combining the power of schemes that allow multiple hash locations for an item (e.g., [1–3, 13]) with the power to dynamically change the location of an item among its possible locations.”
Balanced allocations: the weighted case (2007, background): “Vöcking [13] proved the surprising result that a similar process with an asymmetric tie breaking rule called GoLeft gives a better bound in the m = n case, and is majorized by Greedy[2] in the heavily loaded case ([4]).”