  We consider a model inspired by compatibility constraints that arise between
tasks and servers in data centers, cloud computing systems and content delivery
networks. The constraints are represented by a bipartite graph or network that
interconnects dispatchers with compatible servers. Each dispatcher receives
tasks over time and sends every task to a compatible server with the least
number of tasks, or to a server with the least number of tasks among $d$
compatible servers selected uniformly at random. We focus on networks where the
neighborhood of at least one server is skewed in a limiting regime. This means
that a diverging number of dispatchers are in the neighborhood which are each
compatible with a uniformly bounded number of servers; thus, the degree of the
central server approaches infinity while the degrees of many neighboring
dispatchers remain bounded. We prove that each server with a skewed
neighborhood saturates, in the sense that the mean number of tasks queueing in
front of it in steady state approaches infinity. Paradoxically, this
pathological behavior can even arise in random networks where nearly all the
servers have at most one task in the limit.
