Abstract:
We consider processing networks where multiple dispatchers are connected to single-server queues by a bipartite compatibility graph, modeling constraints that are common in distributed data center networks, typical in cloud systems, due to geographic reasons or data locality issues. We prove lower bounds for the steady-state occupancy, i.e., the complementary cumulative distribution of the empirical queue length measure. Our lower bounds are geometric, with ratios determined by two flexibility metrics: the average degree of the dispatchers and a novel metric that averages the minimum degree over the compatible dispatchers across the servers. Using these lower bounds, we establish that the large scale asymptotic performance of a processing network cannot match that of the classic Power-of-d or JSQ policies unless these flexibility metrics approach infinity in this large scale limit.
Preprint: https://arxiv.org/abs/2505.08974
Speaker: Andres Ferragut, https://aferragu.github.io