The Power of Two Choices on Graphs: the Pair-Approximation is Accurate

Nicolas Gast 1, *
* Corresponding author
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : The power of two-choice is a well-known paradigm to improve load balancing where each incoming task is allocated to the least loaded of two servers picked at random among a collection of n servers [6, 4]. We study the power of two-choice in a setting where the two servers are not picked independently at random but are connected by an edge in an underlying graph. Our problem is motivated by systems in which choices are geometrically constrained (see the model of bike-sharing systems introduced in [1, Section 4]). We study a dynamic setting in which jobs leave the system after being served by a server to which is was allocated. Our focus is when each server has few neighbors (typically 2 to 4) for which an mean-field approximation is not accurate. The static counterpart of our model is studied in [2] in which it is shown by counting the number of arrivals on an edge that the power of two-choice does not hold when the degree is small. This technique cannot be used for studying the dynamic setting as the departures induce long-range dependence. The process is N-dimensional and has no product-form stationary distribution. An exact analytic solution seems out of reach. We use pair-approximation, a technique widespread in biology [5]. We build the equations and show that they describe accurately the steady-state of the system. Our results show that, even in a graph of degree 2, choosing between two neighboring improve dramatically the performance compared to a random allocation. 1. GEOMETRIC TWO-CHOICE MODEL Our system is composed of n identical servers that are connected by an undirected graph (V, E), where the set of vertexes is the set of servers V = {1. .. n}. Each server serves jobs at rate µ and uses a first-come first-serve discipline. Jobs arrive in the system at rate nλ. For each incoming job, one server, say s1, is picked uniformly at random among the n servers. Then, another server s2 is picked uniformly at random among the neighbors of s1. The job is then allocated to the server s1 or s2 that has the least number of jobs (ties are broken at random). This allocation scheme is similar to the one of [2]. We denote the load by ρ = λ/µ and assume that ρ < 1. We now describe a few examples that we will explore numerically in Section 3.
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download
Contributor : Nicolas Gast <>
Submitted on : Tuesday, September 15, 2015 - 11:10:00 AM
Last modification on : Thursday, October 11, 2018 - 8:48:02 AM
Long-term archiving on : Tuesday, December 29, 2015 - 7:06:28 AM


Files produced by the author(s)


  • HAL Id : hal-01199271, version 1



Nicolas Gast. The Power of Two Choices on Graphs: the Pair-Approximation is Accurate. Workshop on MAthematical performance Modeling and Analysis, Jun 2015, Portland, United States. ⟨hal-01199271⟩



Record views


Files downloads