pith. sign in

arxiv: 2606.18218 · v2 · pith:IZ2H3TLInew · submitted 2026-06-16 · 🧮 math.PR · cs.LG· cs.SY· eess.SY· math.OC· stat.ML

Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

Hao Liang , Cheng Tang , Yunzong Xu This is my paper

Pith reviewed 2026-07-02 22:26 UTC · model grok-4.3

classification 🧮 math.PR cs.LGcs.SYeess.SYmath.OCstat.ML
keywords finite-time queue peaksstochastic networksgeneralized switchesMaxWeight schedulinglogarithmic scalingsquare-root envelopeinterior slackstate-space collapse
0
0 comments X

The pith

With interior slack, queue peaks in stochastic networks follow square-root growth only up to a geometry threshold then switch to logarithmic scaling.

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

The paper studies finite-horizon peaks of queue lengths in generalized switches where many queues share service resources under policies like MaxWeight. Arrivals can be dependent and history-responsive, but the only requirement is that their conditional means lie inside a fixed contraction of the capacity region. This interior slack changes the peak law: the square-root envelope holds only up to a threshold that depends on network geometry; past that point the running maximum grows logarithmically in the horizon, both with high probability and in expectation. The mechanism is self-normalization of fluctuations by the stabilizing drift in the current queue direction. Matching lower bounds confirm that the logarithmic term and the geometric threshold cannot be removed.

Core claim

Under uniform interior slack the square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold the running maximum grows only logarithmically with the horizon, both with high probability and in expectation, because the projected fluctuation scale is normalized by the stabilizing drift scale.

What carries the argument

Self-normalization, in which the projected fluctuation scale in the current queue direction is normalized by the stabilizing drift scale.

If this is right

  • Capacity geometry stays in the threshold but drops out of the logarithmic coefficient.
  • When finite-time state-space collapse is available the threshold can be sharpened by local bottleneck geometry.
  • For generalized input-queued switches the bounds achieve tight logarithmic coefficients.
  • Matching lower bounds show both the logarithmic term and the geometric threshold are necessary.

Where Pith is reading between the lines

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

  • Buffer-dimensioning rules could be tightened by switching from square-root to log scaling once the horizon exceeds the threshold.
  • The same self-normalization idea may apply to other drift-minimizing policies beyond MaxWeight.
  • In networks with stronger slack the logarithmic regime could dominate even moderate horizons.

Load-bearing premise

The conditional mean arrival vector stays inside a fixed contraction of the capacity region.

What would settle it

Finding a sequence of horizons where the maximum queue length grows faster than logarithmically with high probability under uniform interior slack would disprove the claimed switch in scaling.

Figures

Figures reproduced from arXiv: 2606.18218 by Cheng Tang, Hao Liang, Yunzong Xu.

Figure 1
Figure 1. Figure 1: An illustration of the two-phase upper envelope given by [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The local geometry behind the two-queue bound. The green triangle is the capacity region, [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Nonstationary CRP geometry. The nominal point [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Two-phase behavior of the mean running peak. Top: mean peak with [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Two-queue example. Global prediction uses Theorem [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Geometry and variance effects in generalized IQS. [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustrative compatibility graph for the parallel-server model with [PITH_FULL_IMAGE:figures/full_fig_p030_7.png] view at source ↗
read the original abstract

We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, nonstationary, and responsive to the system history; the only load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.

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

0 major / 3 minor

Summary. The manuscript establishes finite-time laws for the running maximum of queue lengths in generalized switch models under the sole assumption of uniform interior slack. It shows that the peak grows as the square root of time up to a geometry-dependent threshold, after which it transitions to logarithmic growth with the horizon, both with high probability and in expectation, for drift-minimizing policies such as MaxWeight. The mechanism is self-normalization of projected fluctuations by the stabilizing drift. Matching lower bounds are provided, and the threshold can be sharpened using finite-time state-space collapse when available. Specific bounds with tight logarithmic coefficients are obtained for generalized input-queued switches, with simulations illustrating the two-phase envelope and refinements.

Significance. If the derivations hold, the result provides a sharp refinement of transient peak laws in stochastic networks by identifying the transition from square-root to logarithmic scaling induced by uniform interior slack. The self-normalization argument, which removes capacity geometry from the logarithmic coefficient while retaining it in the threshold, is a notable technical contribution. Matching lower bounds and applicability to input-queued switches strengthen the work, as do the simulations validating the predicted envelope and variance-sensitive improvements. This advances performance analysis for finite-horizon behavior under minimal load conditions.

minor comments (3)
  1. The abstract refers to 'generalized input-queued switches' obtaining finite-time peak bounds; the main text should explicitly state in which section or theorem this specialization is derived from the general case.
  2. Simulations are said to illustrate 'local geometric refinements'; a minor clarification on how the plotted thresholds align with the geometry-dependent threshold in the main theorems would improve readability.
  3. The claim of 'tight logarithmic coefficients' for input-queued switches would benefit from a brief comparison in the text to the general logarithmic term derived earlier.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results on finite-time queue peaks under uniform interior slack, as well as the recommendation for minor revision. The assessment correctly identifies the self-normalization mechanism, the square-root to logarithmic transition, matching lower bounds, and applicability to input-queued switches.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives finite-time peak laws for queue maxima under uniform interior slack via self-normalization of projected fluctuations by stabilizing drift, yielding a two-phase envelope with matching lower bounds. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; results are framed as external mathematical bounds plus simulations, with no renaming of known patterns or ansatz smuggling. The argument remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the uniform interior slack load condition and standard properties of drift-minimizing policies; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • standard math Standard assumptions from probability theory and stochastic processes for modeling arrivals, services, and stability in queueing networks.
    Invoked implicitly to support finite-time analysis and high-probability bounds.

pith-pipeline@v0.9.1-grok · 5770 in / 1178 out tokens · 31334 ms · 2026-07-02T22:26:52.044133+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Bellman-sufficient Information Complexity

    cs.LG 2026-06 unverdicted novelty 7.0

    Introduces Bellman-sufficient information complexity as a representation-level framework for sequential decision making that unifies upper and lower bounds through a conditional Bellman information-risk sandwich.

  2. Bellman-sufficient Information Complexity

    cs.LG 2026-06 unverdicted novelty 6.0

    Proposes Bellman-sufficient state representations and information indices Y=χ(Ω) to organize sequential decision making with a conditional Bellman information-risk sandwich providing matching upper and lower complexit...

Reference graph

Works this paper leans on

28 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    Williamson

    Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P. Williamson. Adversarial queueing theory.Journal of the ACM, 48(1):13–38, 2001

    2001

  2. [2]

    Cambridge university press, 2006

    Nicolo Cesa-Bianchi and G´ abor Lugosi.Prediction, learning, and games. Cambridge university press, 2006

    2006

  3. [3]

    J. G. Dai. Stability of fluid and stochastic processing networks. MaPhySto Miscellanea Publication 9, MaPhySto, Centre for Mathematical Physics and Stochastics, 1999

    1999

  4. [4]

    J. G. Dai and J. Michael Harrison.Processing Networks: Fluid Models and Stability. Cambridge University Press, 2020. ISBN 9781108488891

    2020

  5. [5]

    Atilla Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions.Queueing Systems, 72(3–4):311–359, 2012

    2012

  6. [6]

    Hitting-time and occupation-time bounds implied by drift analysis with applica- tions.Advances in Applied Probability, 14(3):502–525, 1982

    Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applica- tions.Advances in Applied Probability, 14(3):502–525, 1982

    1982

  7. [7]

    Introduction to online convex optimization.Foundations and Trends in Optimiza- tion, 2(3–4):157–325, 2016

    Elad Hazan. Introduction to online convex optimization.Foundations and Trends in Optimiza- tion, 2(3–4):157–325, 2016

    2016

  8. [8]

    Varma, and Siva Theja Maguluri

    Daniela Hurtado-Lange, Sushil M. Varma, and Siva Theja Maguluri. Logarithmic heavy traffic error bounds in generalized switch and load balancing systems.Journal of Applied Probability, 59(3):652–669, 2022

    2022

  9. [9]

    Frank P. Kelly. Stochastic networks. Part III lecture notes, Lent Term, Statistical Laboratory, University of Cambridge, 2011

    2011

  10. [10]

    J. F. C. Kingman. The single server queue in heavy traffic.Proceedings of the Cambridge Philosophical Society, 57(4):902–904, 1961

    1961

  11. [11]

    Springer, 2001

    Jean-Yves Le Boudec and Patrick Thiran.Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer, 2001

    2001

  12. [12]

    Yujie Liu, Vincent Y. F. Tan, and Yunbei Xu. Finite-time minimax bounds and an optimal lyapunov policy in queueing control, 2025. arXiv:2506.18278

    work page arXiv 2025

  13. [13]

    Siva Theja Maguluri and R. Srikant. Heavy traffic queue length behavior in a switch under the MaxWeight algorithm.Stochastic Systems, 6(1):211–250, 2016

    2016

  14. [14]

    Siva Theja Maguluri, Sai Kiran Burle, and R. Srikant. Optimal heavy-traffic queue length scaling in an incompletely saturated switch.Queueing Systems, 88(3–4):279–309, 2018

    2018

  15. [15]

    Neely.Stochastic Network Optimization with Application to Communication and Queueing Systems

    Michael J. Neely.Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool, 2010. 26

    2010

  16. [16]

    Finite-time behavior of erlang-c model: Mixing time, mean queue length and tail bounds.ACM SIGMETRICS Performance Evaluation Review, 53(1):4–6, 2025

    Hoang Huy Nguyen, Sushil Mahavir Varma, and Siva Theja Maguluri. Finite-time behavior of erlang-c model: Mixing time, mean queue length and tail bounds.ACM SIGMETRICS Performance Evaluation Review, 53(1):4–6, 2025

    2025

  17. [17]

    Martin I. Reiman. Some diffusion approximations with state space collapse. In Fran¸ cois Baccelli and Guy Fayolle, editors,Modelling and Performance Evaluation Methodology, volume 60 of Lecture Notes in Control and Information Sciences, pages 207–240. Springer, Berlin, Heidelberg, 1984

    1984

  18. [18]

    Tsitsiklis, and Yuan Zhong

    Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Qualitative properties of α-weighted scheduling policies.ACM SIGMETRICS Performance Evaluation Review, 38(1):239–250, 2010

    2010

  19. [19]

    Tsitsiklis, and Yuan Zhong

    Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Optimal scaling of average queue sizes in an input-queued switch: an open problem.Queueing Systems, 68(3–4):375–384, 2011

    2011

  20. [20]

    Tsitsiklis, and Yuan Zhong

    Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Qualitative properties of α-fair policies in bandwidth-sharing networks.Annals of Applied Probability, 24(1):76–113, 2014

    2014

  21. [21]

    Optimal queue-size scaling in switched networks

    Devavrat Shah, Neil Walton, and Yuan Zhong. Optimal queue-size scaling in switched networks. Annals of Applied Probability, 24(6):2207–2245, 2014

    2014

  22. [22]

    Tsitsiklis, and Yuan Zhong

    Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. On queue-size scaling for input-queued switches.Stochastic Systems, 6(1):1–25, 2016

    2016

  23. [23]

    Alexander L. Stolyar. MaxWeight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic.Annals of Applied Probability, 14(1):1–53, 2004

    2004

  24. [24]

    Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.IEEE Transactions on Automatic Control, 37(12):1936–1948, 1992

    1936

  25. [25]

    Learning and information in stochastic networks and queues

    Neil Walton and Kuang Xu. Learning and information in stochastic networks and queues. In Tutorials in operations research: Emerging optimization methods and modeling techniques with applications, pages 161–198. INFORMS, 2021

    2021

  26. [26]

    Williams

    Ruth J. Williams. Stochastic processing networks.Annual Review of Statistics and Its Application, 3:323–345, 2016

    2016

  27. [27]

    ring zigzag

    Jiaming Xu and Yuan Zhong. Improved queue-size scaling for input-queued switches via graph factorization.Advances in Applied Probability, 52(3):798–824, 2020. 27 Appendix Contents A Experimental details 29 A.1 Experiment 1: two-phase behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 A.2 Experiment 2: local versus global geometry . . . . ...

    2020

  28. [28]

    40 Proof.For everys∈ Sand every coordinatei, qi −s i 2 + ≥q 2 i −2q isi

    Then ⟨u, sLO⟩ ≥H(u)− S2 max 2∥q∥ 2 . 40 Proof.For everys∈ Sand every coordinatei, qi −s i 2 + ≥q 2 i −2q isi. Hence (q−s) + 2 2 ≥ ∥q∥ 2 2 −2⟨q, s⟩. Let ¯s∈arg maxs∈S ⟨u, s⟩, so⟨u,¯s⟩=H(u). By optimality ofs LO and by∥¯s∥2 ≤S max, ∥q∥2 2 −2⟨q, s LO⟩ ≤ (q−s LO)+ 2 2 ≤ (q−¯s)+ 2 2 ≤ ∥q−¯s∥2 2 ≤ ∥q∥ 2 2 −2∥q∥ 2 H(u) +S 2 max. Dividing by 2∥q∥ 2 proves the cla...