Balanced allocation on graphs

DOI10.1145/1109557.1109606MaRDI QIDQ3581542zbMATH OpenOpenAlexFDO

Authors Krishnaram Kenthapadi, Rina Panigrahy

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05)

Abstract: In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the graph is almost regular with degree $n^{e}psilon$, where $epsilon$ is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is $loglogn+O(1/epsilon)+O(1)$. For general $Delta$-regular graphs, we show that the maximum load is $loglogn+O(fraclognlog(Delta/lo{g}^{4}n))+O(1)$ and also provide an almost matching lower bound of $loglogn+fraclognlog(Deltalogn)$. V{"o}cking [Voc99] showed that the maximum bin size with $d$ choice load balancing can be further improved to $O(loglogn/d)$ by breaking ties to the left. This requires $d$ random bin choices. We show that such bounds can be achieved by making only two random accesses and querying $d/2$ contiguous bins in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of $d/2$ consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is $O(loglogn/d)$ with high probability.

Cited in

(17)

• Parallel load balancing on constrained client-server topologies
• Tight bounds for parallel randomized load balancing
• A power-of-two-choices unbalanced allocation process
• Chains-into-Bins Processes
• Graphical balanced allocations and the (1+ )-choice process
• Chains-into-bins processes
• A novel robust on-line protocol for load-balancing in structured peer-to-peer systems
• Stationary distribution analysis of a queueing model with local choice
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• On the power of choice for Boolean functions
• Balanced allocation on dynamic hypergraphs
• Long-term balanced allocation via thinning
• Balanced allocation on hypergraphs
• The Power of Filling in Balanced Allocations
• An improved drift theorem for balanced allocations
• Balanced allocations with the choice of noise
• Balls into non-uniform bins

This page was built for publication: Balanced allocation on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581542)