  We consider a class of power of two choice based assignment policies for
allocating users to servers, where both users and servers are located on a
two-dimensional Euclidean plane. In this framework, we investigate the inherent
tradeoff between the communication cost, and load balancing performance of
different allocation policies. To this end, we first design and evaluate a
Spatial Power of two (sPOT) policy in which each user is allocated to the least
loaded server among its two geographically nearest servers sequentially. When
servers are placed on a two-dimensional square grid, sPOT maps to the classical
Power of two (POT) policy on the Delaunay graph associated with the Voronoi
tessellation of the set of servers. We show that the associated Delaunay graph
is 4-regular and provide expressions for asymptotic maximum load using results
from the literature. For uniform placement of servers, we map sPOT to a
classical balls and bins allocation policy with bins corresponding to the
Voronoi regions associated with the second order Voronoi diagram of the set of
servers. We provide expressions for the lower bound on the asymptotic expected
maximum load on the servers and prove that sPOT does not achieve POT load
balancing benefits. However, experimental results suggest the efficacy of sPOT
with respect to expected communication cost. Finally, we propose two
non-uniform server sampling based POT policies that achieve the best of both
the performance metrics. Experimental results validate the effctiveness of our
proposed policies.
