Help
Cart
Skip main navigation

Transform Method for Stochastic Processing and Matching Networks

Published Online:1 Nov 2026https://doi.org/10.1287/educ.2026.0305
Acknowledgments

The authors acknowledge that large language models, Claude and ChatGPT, were used for editorial refinement, including paraphrasing for clarity and identifying grammatical errors throughout the paper. The final content and interpretations remain the sole responsibility of the authors.

Endnotes

1 Boon et al. [6] also use the term “transform method.” The distinction is that they start from Pollaczek’s formula for the transform and then pass to heavy traffic, whereas the transform method in this tutorial works directly with the queue dynamics.

2 Jhunjhunwala et al. [51] used the ℓ∞ norm to get tight SSC bounds, crucial to obtain tail bounds. However, just to obtain (classic) heavy-traffic limit, it is sufficient to work with the ℓ2 norm, which is easier to work with but provides weaker SSC guarantees (Hurtado-Lange and Maguluri [45]).

References

  • [1] I. Adan and G. Weiss. Exact FCFS matching rates for two infinite multitype sequences. Operations Research 60(2):475–489, 2012.Link, Google Scholar
  • [2] M. Armony, S. Israelit, A. Mandelbaum, Y. N. Marmor, Y. Tseytlin, and S. Zeltyn. Patient flow in hospitals: A data-driven operationalized strategy. Production and Operations Management 24(12):1891–1913, 2015.Google Scholar
  • [3] S. Banerjee and D. Mukherjee. Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extrema. The Annals of Applied Probability 29(2):1262–1309, 2019.Crossref, Google Scholar
  • [4] S. Banerjee and D. Mukherjee. Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Sensitivity on the heavy-traffic parameter. The Annals of Applied Probability 30(1):80–144, 2020.Crossref, Google Scholar
  • [5] S. Bhambay, T. Vasantam, and N. Walton. Optimal scheduling in a quantum switch: Capacity and throughput optimality. Proceedings of the 2025 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems Association for Computing Machinery, New York, 139–141, 2025.Google Scholar
  • [6] M. Boon, A. Janssen, and J. van Leeuwaarden. Heavy-traffic single-server queues and the transform method. Indagationes Mathematicae 34(5):1014–1037, 2023.Crossref, Google Scholar
  • [7] A. Braverman. Steady-state analysis of the join-the-shortest-queue model in the Halfin–Whitt regime. Mathematics of Operations Research 45(3):1069–1103, 2020.Link, Google Scholar
  • [8] A. Braverman and J. Dai. Stein’s method for steady-state diffusion approximations of M/Ph/n+ M systems. The Annals of Applied Probability 27(1):550–581, 2017.Crossref, Google Scholar
  • [9] A. Braverman and J. Dai. Stein’s method for steady-state approximations: Error bounds and engineering solutions. ACM SIGMETRICS Performance Evaluation Review 45(3):250, 2018.Crossref, Google Scholar
  • [10] A. Braverman and Z. Scully. Diffusion approximation error for queueing systems with general primitives. Preprint, submitted July 17, https://arxiv.org/abs/2407.12716, 2024.Google Scholar
  • [11] A. Braverman, J. Dai, and J. Feng. Stein’s method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models. Stochastic Systems 6(2):301–366, 2017.Link, Google Scholar
  • [12] A. Braverman, J. G. Dai, and X. Fang. High-order steady-state diffusion approximations. Operations Research 72(2):604–616, 2024.Link, Google Scholar
  • [13] A. Braverman, J. Dai, and M. Miyazawa. Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach. Stochastic Systems 7(1):143–196, 2017.Link, Google Scholar
  • [14] A. Braverman, J. Dai, and M. Miyazawa. The bar approach for multiclass queueing networks with SBP service policies. Stochastic Systems 15(1):1–49, 2025.Link, Google Scholar
  • [15] A. Budhiraja and C. Lee. Stationary distribution convergence for generalized Jackson networks in heavy traffic. Mathematics of Operations Research 34(1):45–56, 2009.Link, Google Scholar
  • [16] R. Caldentey, E. H. Kaplan, and G. Weiss. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability 41(3):695–730, 2009.Crossref, Google Scholar
  • [17] E. Cardinaels, S. Borst, and J. S. Van Leeuwaarden. Multi-dimensional state space collapse in non-complete resource pooling scenarios. Proceedings of the ACM on Measurement and Analysis of Computing Systems 8(2):1–52, 2024.Crossref, Google Scholar
  • [18] B. Chatterjee, S. T. Maguluri, and D. Mukherjee. Higher-order approximations of sojourn times in M/G/1 queues via Stein’s method. Proceedings of the ACM on Measurement and Analysis of Computing Systems 10(1):1–36, 2026.Crossref, Google Scholar
  • [19] Z. Chen, S. Mou, and S. T. Maguluri. Stationary behavior of constant step size SGD type algorithms: An asymptotic characterization. Proceedings of the ACM on Measurement and Analysis of Computing Systems 6(1):1–24, 2022.Crossref, Google Scholar
  • [20] C. Comte, F. Mathieu, S. Mahavir Varma, and A. Bušić. Online stochastic matching: A polytope perspective. Preprint, submitted December 29, https://arxiv.org/abs/2112.14457, 2021.Google Scholar
  • [21] J. Dai and D. Huo. Asymptotic product-form steady-state for multiclass queueing networks with sbp service policies in multi-scale heavy traffic. Preprint, submitted March 6, https://arxiv.org/abs/2403.04090, 2024.Google Scholar
  • [22] J. Dai, P. W. Glynn, and Y. Xu. Asymptotic product-form steady state for generalized jackson networks in multiscale heavy traffic. Operations Research, ePub ahead of print May 4, https://doi.org/10.1287/opre.2023.0184, 2026.Link, Google Scholar
  • [23] A. Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3–4):311–359, 2012.Crossref, Google Scholar
  • [24] P. Eschenfeldt and D. Gamarnik. Join the shortest queue with many servers. the heavy-traffic asymptotics. Mathematics of Operations Research 43(3):867–886, 2018.Link, Google Scholar
  • [25] W. Fischer and K. Meier-Hellstern. The Markov-modulated Poisson process (MMPP) cookbook. Performance Evaluation 18(2):149–171, 1993.Crossref, Google Scholar
  • [26] G. J. Foschini and J. Salz. A basic dynamic routing problem and diffusion. IEEE Transactions on Communications 26(3):320–327, 1978.Google Scholar
  • [27] D. Gamarnik and A. Zeevi. Validity of heavy traffic steady-state approximations in generalized Jackson networks. The Annals of Applied Probability 16(1):56–90, 2006.Crossref, Google Scholar
  • [28] O. Garnett, A. Mandelbaum, and M. Reiman. Designing a call center with impatient customers. Manufacturing & Service Operations Management 4(3):208–227, 2002.Link, Google Scholar
  • [29] R. E. Gaunt and N. Walton. Stein’s method for the single server queue in heavy traffic. Statistics & Probability Letters 156:108566, 2020.Crossref, Google Scholar
  • [30] P. Glynn and A. Infanger. Solution representations for Poisson’s equation, martingale structure, and the Markov chain central limit theorem. Stochastic Systems 13(4):450–467, 2023.Google Scholar
  • [31] L. V. Green. Health care operations management: A 50-year review. Operations Research 54(6):1025–1037, 2006.Google Scholar
  • [32] I. Grosof, Y. Hong, and M. Harchol-Balter. Analysis of Markovian arrivals and service with applications to intermittent overload. Preprint, submitted May 7, https://arxiv.org/abs/2405.04102, 2024.Google Scholar
  • [33] J. Guang, X. Chen, and J. Dai. Uniform moment bounds for generalized Jackson networks in multiscale heavy traffic. Mathematics of Operations Research 51(1):668–685, 2026.Link, Google Scholar
  • [34] J. Guang, Y. Xu, and J. G. Dai. Steady-state convergence of the continuous-time routing system with general distributions in heavy traffic. Proceedings of the ACM on Measurement and Analysis of Computing Systems 9(1):1–29, 2025.Crossref, Google Scholar
  • [35] V. Gupta. Greedy algorithm for multiway matching with bounded regret. Operations Research 72(3):1139–1155, 2024.Link, Google Scholar
  • [36] V. Gupta and N. Walton. Load balancing in the nondegenerate slowdown regime. Operations Research 67(1):281–294, 2019.Link, Google Scholar
  • [37] I. Gurvich. Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. The Annals of Applied Probability 24:2527–2559, 2014.Google Scholar
  • [38] I. Gurvich and A. Ward. On the dynamic control of matching queues. Stochastic Systems 4(2):479–523, 2014.Link, Google Scholar
  • [39] A. Gut. Probability: A Graduate Course, vol. 75. Springer Science & Business Media, Boston, 2012.Google Scholar
  • [40] B. Hajek. Random Processes for Engineers. Cambridge University Press, Cambridge, UK, 2015.Crossref, Google Scholar
  • [41] J. M. Harrison. Brownian Motion and Stochastic Flow Systems. John Wiley & Sons, New York, 1985.Google Scholar
  • [42] D. Hurtado-Lange. Asymptotic analysis of single-hop stochastic processing networks using the drift method. PhD thesis, Georgia Institute of Technology, Atlanta, 2021.Google Scholar
  • [43] D. Hurtado-Lange and I. Grosof. Markov modulated JSQ in heavy traffic via the Poisson equation. Preprint, submitted February 28, https://arxiv.org/abs/2603.00387, 2026.Google Scholar
  • [44] D. Hurtado-Lange and S. T. Maguluri. A load balancing system in the many-server heavy-traffic asymptotics. Queueing Systems 101:353–391, 2022.Google Scholar
  • [45] D. Hurtado-Lange and S. T. Maguluri. Transform methods for heavy-traffic analysis. Stochastic Systems 10(4):275–309, 2020.Link, Google Scholar
  • [46] D. Hurtado-Lange and S. T. Maguluri. Heavy-traffic analysis of queueing systems with no complete resource pooling. Mathematics of Operations Research 47(4):3129–3155, 2022.Link, Google Scholar
  • [47] D. Hurtado-Lange, S. M. Varma, and S. T. Maguluri. Logarithmic heavy traffic error bounds in generalized switch and load balancing systems. Journal of Applied Probability 59(3):652–669, 2022.Crossref, Google Scholar
  • [48] P. Jhunjhunwala. Design and analysis of stochastic processing and matching networks. ACM SIGMETRICS Performance Evaluation Review 51(3):33–37, 2024.Crossref, Google Scholar
  • [49] P. Jhunjhunwala and S. T. Maguluri. Low-complexity switch scheduling algorithms: Delay optimality in heavy traffic. IEEE/ACM Transactions on Networking 30(1):464–473, 2021.Crossref, Google Scholar
  • [50] P. Jhunjhunwala and S. T. Maguluri. Heavy traffic distribution of queueing systems without resource pooling. Preprint, submitted June 13, https://arxiv.org/abs/2206.06504, 2022.Google Scholar
  • [51] P. Jhunjhunwala, D. Hurtado-Lange, and S. T. Maguluri. Exponential tail bounds on queues: A confluence of non-asymptotic heavy traffic and large deviations. ACM SIGMETRICS Performance Evaluation Review 51(4):18–19, 2024.Crossref, Google Scholar
  • [52] P. R. Jhunjhunwala, M. Zubeldia, and S. T. Maguluri. Join-the-shortest queue with abandonment: Critically loaded and heavily overloaded regimes. Mathematics of Operations Research 51(1):398–439, 2026.Link, Google Scholar
  • [53] S. Kerimov, I. Ashlagi, and I. Gurvich. On the optimality of greedy policies in dynamic matching. Operations Research 73(1):560–582, 2025.Link, Google Scholar
  • [54] J. Kingman. The single server queue in heavy traffic. Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 902–904, 1961.Google Scholar
  • [55] J. Kingman. Some inequalities for the queue GI/G/1. Biometrika 49(3–4):315–324, 1962.Crossref, Google Scholar
  • [56] F. Koehler and B. Wu. Constructive approximation under Carleman’s condition, with applications to smoothed analysis. Preprint, submitted December 4, https://arxiv.org/abs/2512.04371, 2025.Google Scholar
  • [57] X. Liu and L. Ying. A simple steady-state analysis of load balancing algorithms in the sub-Halfin-Whitt regime. ACM SIGMETRICS Performance Evaluation Review 46(2):15–17, 2019.Crossref, Google Scholar
  • [58] X. Liu and L. Ying. Universal scaling of distributed queues under load balancing in the super-Halfin-Whitt regime. IEEE/ACM Transactions on Networking 30(1):190–201, 2022.Crossref, Google Scholar
  • [59] S. T. Maguluri and R. Srikant. Heavy traffic queue length behavior in a switch under the MaxWeight algorithm. Stochastic Systems 6(1):211–250, 2016.Link, Google Scholar
  • [60] A. Makowski and A. Shwartz. The Poisson equation for countable Markov chains: Probabilistic methods and interpretations. Handbook of Markov Decision Processes, International Series in Operations Research and Management Science, vol. 40. Springer, Boston, 269–303, 2002.Crossref, Google Scholar
  • [61] R. Menich and R. F. Serfozo. Optimality of routing and servicing in dependent parallel processing systems. Queueing Systems 9(4):403–418, 1991.Crossref, Google Scholar
  • [62] S. Meyn and R. Tweedie. Markov Chains and Stochastic Stability, 2nd edition. Cambridge University Press, Cambridge, UK, 2009.Crossref, Google Scholar
  • [63] M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12(10):1094–1104, 2001.Crossref, Google Scholar
  • [64] J. Reed and T. Tezcan. Hazard rate scaling of the abandonment distribution for the GI/M/n + GI queue in heavy traffic. Operations Research 60(4):981–995, 2012.Link, Google Scholar
  • [65] M. I. Reiman. Open queueing networks in heavy traffic. Mathematics of Operations Research 9(3):441–458, 1984.Link, Google Scholar
  • [66] C. Shi, Y. Wei, and Y. Zhong. Process flexibility for multiperiod production systems. Operations Research 67(5):1300–1320, 2019.Link, Google Scholar
  • [67] M. van der Boor, S. Borst, J. van Leeuwaarden, and D. Mukherjee. Scalable load balancing in networked systems: A survey of recent advances. Preprint, submitted June 14, https://arxiv.org/abs/1806.05444, 2018.Google Scholar
  • [68] S. M. Varma. Stochastic matching networks: Theory and applications to matching platforms. ACM SIGMETRICS Performance Evaluation Review 52(3):3–6, 2025.Crossref, Google Scholar
  • [69] S. M. Varma and S. T. Maguluri. Throughput optimal routing in blockchain based payment systems. IEEE Transactions on Control of Network Systems 8(4):1859–1868, 2021.Crossref, Google Scholar
  • [70] S. M. Varma and S. T. Maguluri. Transportation polytope and its applications in parallel server systems. Preprint, submitted August 11, https://arxiv.org/abs/2108.13167, 2021.Google Scholar
  • [71] S. M. Varma and S. T. Maguluri. A heavy traffic theory of two-sided queues. ACM SIGMETRICS Performance Evaluation Review 49(3):43–44, 2022.Crossref, Google Scholar
  • [72] S. M. Varma, F. Castro, and S. T. Maguluri. Power-of-d choices load balancing in the sub-Halfin-Whitt regime. Stochastic Systems 15(4):291–336, 2025.Link, Google Scholar
  • [73] S. M. Varma, P. Bumpensanti, S. T. Maguluri, and H. Wang. Dynamic pricing and matching for two-sided queues. Operations Research 71(1):83–100, 2023.Link, Google Scholar
  • [74] S. M. Varma, P. Jhunjhunwala, D. Hurtado-Lange, and S. T. Maguluri. Heavy-traffic convergence simulation: Companion code for “Transform method for stochastic processing and matching networks.” Accessed June 21, 2026, https://github.com/smv30/survey_transform_method, 2026.Google Scholar
  • [75] N. Vvedenskaya, R. Dobrushin, and F. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems of Information Transmission 32(1):15–27, 1996.Google Scholar
  • [76] W. Wang, S. T. Maguluri, R. Srikant, and L. Ying. Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing. SIGMETRICS Performance Evaluation Review 45(3):232–245, 2018.Crossref, Google Scholar
  • [77] A. Ward. Asymptotic analysis of queueing systems with reneging: A survey of results for FIFO, single class models. Surveys in Operations Research and Management Science 17(1):1–14, 2012.Crossref, Google Scholar
  • [78] A. Ward and P. Glynn. A diffusion approximation for a Markovian queue with reneging. Queueing Systems 43(1–2):103–128, 2003.Crossref, Google Scholar
  • [79] A. Ward and P. Glynn. A diffusion approximation for a GI/GI/1 queue with balking or reneging. Queueing Systems 50(4):371–400, 2005.Crossref, Google Scholar
  • [80] W. Whitt. Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues, Springer Series in Operations Research and Financial Engineering. Springer, Berlin, 2002.Crossref, Google Scholar
  • [81] D. Williams. Probability with Martingales. Cambridge University Press, Cambridge, UK, 1991.Crossref, Google Scholar
  • [82] R. J. Williams. Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems 30(1–2):27–88, 1998.Crossref, Google Scholar
  • [83] R. J. Williams. Stochastic processing networks. Annual Review of Statistics and Its Application 3(1):323–345, 2016.Crossref, Google Scholar
  • [84] W. Winston. Optimality of the shortest line discipline. Journal of Applied Probability 14(1):181–189, 1977.Crossref, Google Scholar
  • [85] S. Zeltyn and A. Mandelbaum. Call centers with impatient customers: Many-server asymptotics of the M/M/n + G queue. Queueing Systems 51(3–4):361–402, 2005.Crossref, Google Scholar
  • [86] Z. Zhao, S. Banerjee, and D. Mukherjee. Many-server asymptotics for join-the-shortest-queue in the super-Halfin-Whitt scaling window. Mathematics of Operations Research, ePub ahead of print July 8, https://pubsonline.informs.org/doi/abs/10.1287/moor.2021.0133, 2025.Google Scholar
  • [87] M. Zubeldia, P. Jhunjhunwala, and S. T. Maguluri. Matching queues with abandonments in quantum switches: Stability and throughput analysis. Operations Research 74(1):339–355, 2026.Link, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree