pith. sign in

arxiv: 2505.08974 · v3 · submitted 2025-05-13 · 🧮 math.PR · cs.PF

Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity

Diego Goldsztajn , Andres Ferragut This is my paper

Pith reviewed 2026-05-22 14:53 UTC · model grok-4.3

classification 🧮 math.PR cs.PF
keywords processing networkssteady-state occupancygeometric lower boundsflexibility metricsbipartite compatibility graphload balancingqueue length tailasymptotic performance
0
0 comments X

The pith

Steady-state queue lengths in limited-connectivity processing networks decay geometrically at rates set by two flexibility metrics from the compatibility graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves lower bounds on the complementary cumulative distribution function of the empirical queue length in processing networks where dispatchers connect to single-server queues through a fixed bipartite compatibility graph. These bounds take a geometric form whose decay ratio is controlled by the average dispatcher degree and a second metric that averages the minimum degree of compatible dispatchers for each server. If the bounds hold, then any growing network whose flexibility metrics stay bounded cannot match the asymptotic tail behavior of fully flexible policies such as Power-of-d or Join-the-Shortest-Queue. Readers care because data centers and cloud systems routinely impose geographic or locality constraints that produce exactly such limited graphs.

Core claim

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.

What carries the argument

The two flexibility metrics derived from the static bipartite compatibility graph, which set the common ratio of the geometric lower bound on the occupancy tail.

If this is right

  • The occupancy tail is bounded below by a geometric distribution whose ratio equals the larger of the two flexibility metrics.
  • If both metrics remain finite as the network grows, the probability of large queues cannot vanish at the rate achieved by Power-of-d or JSQ.
  • Any asymptotic optimality claim for a growing network must be accompanied by a proof that at least one flexibility metric diverges with system size.
  • The lower bounds apply directly to the empirical distribution seen by an external observer sampling the entire system.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Network designers could treat the two metrics as explicit design targets when adding links to a compatibility graph.
  • The same geometric technique might be adapted to time-varying or randomly rewired graphs to quantify how much dynamism improves the tail.
  • In mean-field limits of these networks the metrics would appear as parameters that control whether the fluid equilibrium has positive mass at large queue lengths.
  • Empirical validation could begin with small-scale testbeds that fix the graph and measure the observed occupancy tail against the predicted geometric ratio.

Load-bearing premise

The compatibility graph is static and the system reaches a unique steady-state distribution whose occupancy tail can be bounded using only the two flexibility metrics derived from the graph degrees.

What would settle it

A simulation or measurement, in a large but finite network whose flexibility metrics remain bounded, that exhibits a queue-length tail decaying strictly faster than the geometric rate given by those metrics.

Figures

Figures reproduced from arXiv: 2505.08974 by Andres Ferragut, Diego Goldsztajn.

Figure 1
Figure 1. Figure 1: Dispatchers and servers are represented by crossed white circles and black circles, respectively. Each server in G1 n is connected to all the dispatchers at its left and only one dispatcher at its right. The connected component on the right of G2 n consists of one dispatcher connected to n servers, whereas each of the other n connected components consists of one dispatcher and one server. Theorem 3. Consid… view at source ↗
Figure 2
Figure 2. Figure 2: Edge simplification that removes the compatibility relation (d, u) and incorporates server v and the compatibility relation (d, v). The servers u and v have the same potential departure process. Further, λ2(e) := λ1(e) for all e ∈ D2 and µ2(w) := µ1(w) for all w ∈ S1. Remark 1. Suppose that u ∈ S1 is only compatible with d ∈ D1 and consider the edge simplification that removes (d, u) and adds the server v.… view at source ↗
Figure 3
Figure 3. Figure 3: Bipartite graph G0 obtained after performing an edge simplification at each edge of G. Each of the sets of servers {ud, ue} and {vd, ve} has a common potential departure process. case. Furthermore, then (3) and (4) hold for the stationary distributions. 5 Proof of Theorem 1 In this section we establish Theorem 1. For this purpose, we consider the load balancing process X of Section 3 and assume that it is … view at source ↗
Figure 4
Figure 4. Figure 4: Schematic view of the bipartite graphs G, G0 and Gγ. The circles represent sets of nodes and a thick line between two sets of nodes indicates that there may exist edges between the two sets. The set S˜ γ is the set of servers incorporated through the edge simplifications. The potential departure processes of servers in Sγ are coupled with those of servers in S˜ γ but are mutually independent over Sγ. for a… view at source ↗
read the original 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript considers processing networks in which dispatchers route jobs to single-server queues subject to a static bipartite compatibility graph. It derives geometric lower bounds on the complementary cumulative distribution function of the steady-state empirical queue-length distribution; the decay ratio is expressed in terms of two flexibility metrics extracted from the graph (average dispatcher degree and a novel server-side average of minimum compatible dispatcher degrees). These bounds are then applied to show that, in a sequence of growing networks, the asymptotic tail performance cannot match that of the fully flexible Power-of-d or JSQ policies unless both flexibility metrics diverge to infinity.

Significance. If the claimed geometric bounds hold and depend only on the two degree-derived metrics, the work supplies a graph-theoretic necessary condition for good large-scale performance in constrained processing networks. This is relevant to data-center and cloud scheduling design. The introduction of the novel flexibility metric and the direct derivation from the compatibility graph (without fitted parameters) are positive features.

major comments (2)
  1. [§4] §4, proof of the main lower-bound theorem: the argument proceeds via a global balance equation or Lyapunov drift that averages over the bipartite graph using only the two flexibility metrics. It is not shown that the resulting ratio remains valid for bipartite graphs that share the same degree sequence but differ in vertex expansion or min-cut structure; a low-expansion cut could induce localized overload that inflates the occupancy tail beyond the claimed geometric rate.
  2. [§5] §5, asymptotic comparison with Power-of-d/JSQ: the claim that the network cannot match the classic policies unless the flexibility metrics tend to infinity rests on the lower bound being determined solely by the two scalars. If expansion properties affect the tail independently of degrees, the necessary condition for asymptotic equivalence would involve additional graph invariants not captured by the current metrics.
minor comments (3)
  1. [§2] The definition of the novel server-side flexibility metric (averaging minimum compatible dispatcher degrees) would benefit from an explicit formula and a small illustrative graph computation in §2.
  2. [§3] Notation for the empirical queue-length distribution and its complementary CDF should be introduced with a short probability-space clarification to aid readers unfamiliar with mean-field or fluid limits.
  3. [Abstract and §3] A few typographical inconsistencies appear in the statement of the two flexibility metrics between the abstract and the main theorem; align the wording.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments. We address each major comment below, clarifying that our derivations rely solely on the flexibility metrics and hold for arbitrary bipartite graphs.

read point-by-point responses

  1. Referee: [§4] §4, proof of the main lower-bound theorem: the argument proceeds via a global balance equation or Lyapunov drift that averages over the bipartite graph using only the two flexibility metrics. It is not shown that the resulting ratio remains valid for bipartite graphs that share the same degree sequence but differ in vertex expansion or min-cut structure; a low-expansion cut could induce localized overload that inflates the occupancy tail beyond the claimed geometric rate.

    Authors: We appreciate this observation. The proof in §4 is obtained by summing the global balance equations of the stationary distribution for the underlying continuous-time Markov chain. The averaging step uses only the average dispatcher degree and the server-side flexibility metric (the average, over servers, of the minimum degree among compatible dispatchers). No assumptions are made on vertex expansion, conductance, or min-cut properties. Consequently the resulting geometric lower bound on the complementary cumulative distribution function holds for every static bipartite compatibility graph possessing the given degree-derived metrics. A low-expansion cut that produces localized overload can only increase certain regional occupancies and thereby enlarge the empirical tail; this is consistent with, and does not violate, a lower bound. We therefore maintain that the claimed ratio is valid uniformly and does not require additional expansion hypotheses. revision: no

  2. Referee: [§5] §5, asymptotic comparison with Power-of-d/JSQ: the claim that the network cannot match the classic policies unless the flexibility metrics tend to infinity rests on the lower bound being determined solely by the two scalars. If expansion properties affect the tail independently of degrees, the necessary condition for asymptotic equivalence would involve additional graph invariants not captured by the current metrics.

    Authors: We thank the referee for this remark. The asymptotic statement in §5 is an immediate corollary of the lower bound proved in §4. Because that lower bound depends only on the two flexibility metrics and applies to every bipartite graph, any sequence of networks whose metrics remain bounded necessarily exhibits a tail that decays no faster than the corresponding geometric rate. This rate is strictly inferior to the decay attained by Power-of-d or JSQ under full flexibility. While expansion may modulate the precise constant or the location of overload, it cannot improve the tail beyond the lower bound we have established; poorer expansion can only degrade performance further. Hence the necessary condition that the flexibility metrics diverge to infinity remains valid irrespective of other graph-theoretic invariants. revision: no

Circularity Check

0 steps flagged

Derivation self-contained from compatibility graph metrics

full rationale

The paper derives geometric lower bounds on the complementary CDF of empirical queue lengths directly from two flexibility metrics computed as averages over the degrees in the static bipartite compatibility graph. These metrics are explicit functions of the input graph and serve as parameters in the bound expressions rather than being fitted to the occupancy tail or redefined in terms of the claimed result. The proof relies on standard balance equations or Lyapunov arguments applied to the queueing process under the given compatibility constraints, without load-bearing self-citations, ansatzes smuggled from prior work, or reductions that make the output equivalent to the inputs by construction. The asymptotic comparison to Power-of-d and JSQ follows from the same graph-derived scalars and does not require external uniqueness theorems or fitted parameters.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on standard queueing-theory assumptions and the definition of the novel flexibility metric; no free parameters are fitted and no new physical entities are postulated.

axioms (2)
  • domain assumption The processing network reaches a unique steady-state distribution whose occupancy can be characterized via the bipartite compatibility graph.
    Invoked to justify the existence of the steady-state occupancy that the lower bounds target.
  • domain assumption Standard Markovian assumptions (Poisson arrivals, exponential service) hold for the underlying queues.
    Typical background for steady-state analysis in processing networks.
invented entities (1)
  • Novel flexibility metric that averages the minimum degree over the compatible dispatchers across the servers no independent evidence
    purpose: To quantify server-side flexibility in the bipartite graph for the geometric bound
    Defined within the paper and used to express the decay ratio of the occupancy tail.

pith-pipeline@v0.9.0 · 5650 in / 1421 out tokens · 49318 ms · 2026-05-22T14:53:01.388906+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Scalable load balancing in networked systems: A survey of recent advances,

    M. van der Boor, S. C. Borst, J. S. H. van Leeuwaarden, and D. Mukherjee, “Scalable load balancing in networked systems: A survey of recent advances,”SIAM Review, vol. 64, no. 3, pp. 554–622, 2022

    work page 2022

  2. [2]

    Supermarket model on graphs,

    A. Budhiraja, D. Mukherjee, and R. Wu, “Supermarket model on graphs,”The Annals of Applied Probability, vol. 29, no. 3, pp. 1740–1777, 2019

    work page 2019

  3. [3]

    On the stability of a partially accessible multi-station queue with state-dependent routing,

    S. G. Foss and N. I. Chernova, “On the stability of a partially accessible multi-station queue with state-dependent routing,”Queueing Systems, vol. 29, pp. 55–73, 1998

    work page 1998

  4. [4]

    The power of two choices on graphs: the pair-approximation is accurate?

    N. Gast, “The power of two choices on graphs: the pair-approximation is accurate?” ACM SIGMETRICS Performance Evaluation Review, vol. 43, no. 2, pp. 69–71, 2015

    work page 2015

  5. [5]

    Server saturation in skewed networks,

    D. Goldsztajn, S. C. Borst, and J. S. Van Leeuwaarden, “Server saturation in skewed networks,”Proceedings of the ACM on Measurement and Analysis of Computing Sys- tems, vol. 8, no. 2, pp. 1–37, 2024

    work page 2024

  6. [6]

    Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services,

    Y. Lu, Q. Xie, G. Kliot, A. Geller, J. R. Larus, and A. Greenberg, “Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services,”Performance Evaluation, vol. 68, no. 11, pp. 1056–1071, 2011. 16 Geometric lower bounds for processing networks Goldsztajn and Ferragut

    work page 2011

  7. [7]

    Optimality of routing and servicing in dependent parallel processing systems,

    R. Menich and R. F. Serfozo, “Optimality of routing and servicing in dependent parallel processing systems,”Queueing Systems, vol. 9, pp. 403–418, 1991

    work page 1991

  8. [8]

    The power of two choices in randomized load balancing,

    M. Mitzenmacher, “The power of two choices in randomized load balancing,”IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 10, pp. 1094–1104, 2001

    work page 2001

  9. [9]

    Asymptotically optimal load balancing topologies,

    D. Mukherjee, S. C. Borst, and J. S. H. van Leeuwaarden, “Asymptotically optimal load balancing topologies,”Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 2, no. 1, pp. 1–29, 2018

    work page 2018

  10. [10]

    Universality of power-of-dload balancing in many-server systems,

    D. Mukherjee, S. C. Borst, J. S. H. van Leeuwaarden, and P. A. Whiting, “Universality of power-of-dload balancing in many-server systems,”Stochastic Systems, vol. 8, no. 4, pp. 265–292, 2018

    work page 2018

  11. [11]

    Load balancing under strict compatibility constraints,

    D. Rutten and D. Mukherjee, “Load balancing under strict compatibility constraints,” Mathematics of Operations Research, vol. 48, no. 1, pp. 227–256, 2023

    work page 2023

  12. [12]

    Mean-field analysis for load balancing on spatial graphs,

    ——, “Mean-field analysis for load balancing on spatial graphs,”The Annals of Applied Probability, vol. 34, no. 6, pp. 5228–5257, 2024

    work page 2024

  13. [13]

    Extremal properties of the short- est/longest non-full queue policies in finite-capacity systems with state-dependent ser- vice rates,

    P. D. Sparaggis, D. Towsley, and C. Cassandras, “Extremal properties of the short- est/longest non-full queue policies in finite-capacity systems with state-dependent ser- vice rates,”Journal of Applied Probability, vol. 30, pp. 223–236, 1993

    work page 1993

  14. [14]

    Pull-based load distribution in large-scale heterogeneous service sys- tems,

    A. L. Stolyar, “Pull-based load distribution in large-scale heterogeneous service sys- tems,”Queueing Systems, vol. 80, pp. 341–361, 2015

    work page 2015

  15. [15]

    Queueing system with selection of the shortest of two queues: An asymptotic approach,

    N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich, “Queueing system with selection of the shortest of two queues: An asymptotic approach,”Problemy Peredachi Informatsii, vol. 32, no. 1, pp. 20–34, 1996

    work page 1996

  16. [16]

    Optimal load balancing with locality constraints,

    W. Weng, X. Zhou, and R. Srikant, “Optimal load balancing with locality constraints,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 4, no. 3, pp. 1–37, 2020

    work page 2020

  17. [17]

    Optimal rate-matrix pruning for large-scale heterogeneous systems,

    Z. Zhao and D. Mukherjee, “Optimal rate-matrix pruning for large-scale heterogeneous systems,”Queueing Systems, vol. 110, no. 1, p. 16, 2026

    work page 2026

  18. [18]

    Exploiting data locality to improve performance of heterogeneous server clusters,

    Z. Zhao, D. Mukherjee, and R. Wu, “Exploiting data locality to improve performance of heterogeneous server clusters,”Stochastic Systems, vol. 14, no. 3, pp. 229–272, 2024. 17

    work page 2024