2025/05/13 by Goldsztajn, Diego, Ferragut, Andres
#60K25 (Primary) 68M20 (Secondary) #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF) #Probability (math.PR)
paper · doi:10.48550/arxiv.2505.08974
We consider processing networks where multiple dispatchers are connected to single-server queues by a bipartite compatibility graph, modeling constraints that are common in data centers and cloud networks due to geographic reasons or data locality issues. We prove lower bounds for the steady-state occupancy, i.e., the complementary cumulative distribution function of the empirical queue length distribution. The lower bounds are geometric with ratios given 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 asymptotic performance of a growing processing network cannot match that of the classic Power-of-d or JSQ policies unless the flexibility metrics approach infinity in the large-scale limit.