| Abstract |
We consider a power of two choices based allocation pol- icy where both resources and users are located on a two- dimensional plane. First, we consider a “Spatial Power of two” (sPOT) policy which sequentially allocates a user to the least loaded resource among its two nearest resources. We show that sPOT maps to a classical balls and bins al- location policy with bins corresponding to the voronoi re- gions associated with the second order voronoi diagram of the set of resources. We provide closed form expression for the lower bound on the asymptotic maximum load on the resources and show that the classical Power of two (POT) benefits are not achieved by sPOT. Further, when resources are placed in an equidistant manner on a two-dimensional grid, sPOT maps to POT on the Delaunay graph associated with the voronoi tessellation of the set of resources. We show that the associated Delaunay graph is ∆-regular with ∆ = 4 and provide expressions for asymptotic maximum load using results from the literature. Finally, we propose a candidate set based sPOT policy (k-sPOT) in which a user uniformly at random selects two resources from a candidate set consisting of its k closest resources and gets allocated to the leastly loaded resource. Numerical results suggest that whenk=O(nα)withα>0andnbeingthenumberof users, k-sPOT provide POT benefits. |