pith. sign in

arxiv: 2505.07648 · v2 · submitted 2025-05-12 · 🧮 math.PR

Markov Modelling Approach for Queues with Correlated Service Times -- the M/M_D/2 Model

Suman Thapa , Yiqiang Q. Zhao This is my paper

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

classification 🧮 math.PR
keywords queueing theoryMarkov chainscorrelated service timesstationary distributionM/M/2 queueperformance analysisdependence in queues
0
0 comments X

The pith

The number of customers in a two-server queue with correlated exponential service times forms a Markov chain whose stationary distribution can be found exactly.

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

The paper shows that a queueing system with Poisson arrivals and two servers whose exponential service times are positively correlated can still be modeled so that the total number of customers in the system evolves as a Markov chain. It then derives a closed-form solution for the long-run probabilities of each possible number of customers. A reader cares because this removes the usual need for simulation or approximation when dependence is present, making the effect of correlation on congestion, waiting time, and server utilization directly visible by comparing to the classic independent case.

Core claim

In the M/M_D/2 model the queue-length process is a Markov chain even though the two service times are correlated. The stationary distribution is obtained by solving the global balance equations for the chain, and the resulting probabilities are expressed in terms of the arrival rate, the two service rates, and the correlation parameter between the servers.

What carries the argument

The M/M_D/2 model, in which the correlation between the two exponential service times is embedded directly in the transition rates of a one-dimensional Markov chain on the total number of customers.

If this is right

  • Steady-state probabilities for every number of customers become available in closed form.
  • Mean queue length, probability that both servers are busy, and other performance measures can be written explicitly as functions of the correlation parameter.
  • Direct numerical comparison with the independent M/M/2 queue shows the precise change in congestion caused by positive dependence.

Where Pith is reading between the lines

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

  • The same embedding technique may let analysts treat other forms of dependence, such as between arrival and service processes, while retaining a Markov description on queue length alone.
  • Service correlations could be treated as a design variable whose value is chosen to minimize a performance cost.
  • The approach supplies a benchmark against which approximate methods for larger numbers of correlated servers can be tested.

Load-bearing premise

The correlation between the two servers' service times can be built into the transition rates of the queue-length process without destroying its Markov property.

What would settle it

Long-run simulation of the two-server queue with a chosen positive correlation between service times produces empirical frequencies for each customer count that match the analytic stationary probabilities derived from the balance equations.

Figures

Figures reproduced from arXiv: 2505.07648 by Suman Thapa, Yiqiang Q. Zhao.

Figure 1
Figure 1. Figure 1: Failure patterns (×) under different orderings of T1, T2, T12 in the Marshall–Olkin shock model. Solid segments show original lifetimes; dashed segments show lifetimes after replacement. Common-shock times are regeneration epochs. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: ρ = 0.1 for impact on the system performance by µ12 when µ1 = µ2 = µ It is evident that the dependence between service times has a significant impact on system performance. This impact becomes increasingly pronounced as µ goes to 0. For a small value of ρ (say ρ = 0.1), the increase in E[QD,h] is initially slower than linear, specifically, it grows more slowly than the slope of the straight line connecting… view at source ↗
Figure 3
Figure 3. Figure 3: ρ = 0.5 for impact on the system performance by µ12 when µ1 = µ2 = µ [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: ρ = 0.9 for impact on the system performance by µ12 when µ1 = µ2 = µ 27 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: ρ = 0.1 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 1.5 However, It is interesting to observe that, when the dependence parameter θ is large (for ex￾ample, θ = 15 in Figures 14 and 15) while the joint service rate µ12 remains relatively small, the expected queue length in the dependent system can be smaller than that in the independent system, which is not intuitively obvious. This p… view at source ↗
Figure 6
Figure 6. Figure 6: ρ = 0.5 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 1.5 [PITH_FULL_IMAGE:figures/full_fig_p029_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: ρ = 0.9 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 1.5 29 [PITH_FULL_IMAGE:figures/full_fig_p029_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: ρ = 0.1 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 2 [PITH_FULL_IMAGE:figures/full_fig_p030_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: ρ = 0.5 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 2 30 [PITH_FULL_IMAGE:figures/full_fig_p030_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: ρ = 0.9 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 2 [PITH_FULL_IMAGE:figures/full_fig_p031_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: ρ = 0.1 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 3 31 [PITH_FULL_IMAGE:figures/full_fig_p031_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: ρ = 0.5 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 3 [PITH_FULL_IMAGE:figures/full_fig_p032_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: ρ = 0.9 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 3 32 [PITH_FULL_IMAGE:figures/full_fig_p032_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: ρ = 0.1 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 15 6 Concluding remarks In this paper, we proposed a new approach that leads to a Markovian queueing model for systems with positively correlated servers. This approach successfully addresses the concerns raised by Mitchell et al. [20], who wrote: “It is not clear that the birth–death equation approach can be modified to incorpo￾ra… view at source ↗
Figure 15
Figure 15. Figure 15: ρ = 0.5 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 15 [PITH_FULL_IMAGE:figures/full_fig_p034_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: ρ = 0.9 for impact on the system performance by µ12 when µ1 ̸= µ2 with θ = 15 34 [PITH_FULL_IMAGE:figures/full_fig_p034_16.png] view at source ↗
read the original abstract

Demand for studying queueing systems with multiple servers providing correlated services was created about 60 years ago, motivated by various applications. In recent years, the importance of such studies has been significantly increased, supported by new applications of greater significance to much larger scaled industry, and the whole society. Such studies have been considered very challenging. In this paper, a new Markov modelling approach for queueing systems with servers providing correlated services is proposed. We apply this new proposed approach to a queueing system with arrivals according to a Poisson process and two positive correlated exponential servers, referred to as the $M/M_D/2$ queue. We first prove that the queueing process (the number of customers in the system) is a Markov chain, and then provide an analytic solution for the stationary distribution of the process, based on which it becomes much easier to see the impact of the dependence on system performance compared to the performance with independent services.

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 / 2 minor

Summary. The paper proposes a new Markov modelling approach for queueing systems with correlated service times. It applies this to the M/M_D/2 model with Poisson arrivals and two positively correlated exponential servers, claiming to prove that the queue-length process N(t) is a Markov chain and to derive an analytic solution for its stationary distribution, which is then used to assess the impact of service dependence on performance relative to the independent case.

Significance. If the Markov property holds and the stationary distribution is correctly obtained, the work would provide a useful analytic framework for a class of dependent-service multi-server queues that has been studied for decades but remains challenging. The explicit closed-form stationary distribution would be a strength, enabling direct performance comparisons and clearer visibility of correlation effects without simulation.

major comments (2)
  1. [Model description and Markov property proof] § describing the M/M_D/2 model and the Markov-property proof: the claim that correlation between the two exponential service times can be incorporated so that N(t) alone is Markovian is load-bearing. Standard constructions (Marshall-Olkin shocks, copulas on service times) generally make the joint law of residual service times history-dependent, so the instantaneous departure rate when both servers are busy is not necessarily a fixed function of N alone. The paper must exhibit the explicit state space, the generator, and the derivation showing time-homogeneous rates that depend on N only.
  2. [Stationary distribution derivation] Stationary-distribution section (balance equations and solution): the analytic solution is derived under the assumed Markov property. If the transition rates are not rigorously shown to be state-dependent solely through N and independent of history, the global balance equations and their closed-form solution do not follow. Please display the rate matrix or the system of equations and verify they incorporate the correlation parameter without hidden auxiliary variables.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'positive correlated' should be replaced by a precise statement of the correlation parameter range or distribution used.
  2. [Notation and model definition] Notation: define the subscript D in M/M_D/2 at first use and ensure consistent spelling of 'correlated' throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments. We address the two major comments below, clarifying our construction of the correlated service times and indicating where we will strengthen the exposition in revision.

read point-by-point responses

  1. Referee: [Model description and Markov property proof] § describing the M/M_D/2 model and the Markov-property proof: the claim that correlation between the two exponential service times can be incorporated so that N(t) alone is Markovian is load-bearing. Standard constructions (Marshall-Olkin shocks, copulas on service times) generally make the joint law of residual service times history-dependent, so the instantaneous departure rate when both servers are busy is not necessarily a fixed function of N alone. The paper must exhibit the explicit state space, the generator, and the derivation showing time-homogeneous rates that depend on N only.

    Authors: We agree that an explicit display of the generator is necessary for full rigor. In the M/M_D/2 construction the positive correlation is introduced by defining a joint service mechanism whose instantaneous completion rate, when both servers are busy, equals 2μ(1+ρ) where ρ ∈ (0,1] is the dependence parameter; because the marginals remain exponential, the memoryless property is preserved and the future evolution depends only on the current value of N(t). The state space is the non-negative integers, the generator is a birth-death matrix with birth rate λ everywhere and state-dependent death rates μ (for N=1) and 2μ(1+ρ) (for N≥2). We will add the full infinitesimal generator and the short derivation establishing time-homogeneity in the revised manuscript. revision: yes

  2. Referee: [Stationary distribution derivation] Stationary-distribution section (balance equations and solution): the analytic solution is derived under the assumed Markov property. If the transition rates are not rigorously shown to be state-dependent solely through N and independent of history, the global balance equations and their closed-form solution do not follow. Please display the rate matrix or the system of equations and verify they incorporate the correlation parameter without hidden auxiliary variables.

    Authors: We accept the request for explicit equations. The global balance equations are written directly from the generator above: λπ_0 = μπ_1, (λ+μ)π_1 = λπ_0 + 2μ(1+ρ)π_2, and for n≥2 the usual birth-death relation with the correlated death rate 2μ(1+ρ). The correlation parameter ρ appears only in the death rates for n≥2; no auxiliary variables are required. The resulting linear system admits the closed-form solution given in the paper. In revision we will display the complete set of balance equations together with the generator to make this transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity: proof of Markov property and analytic stationary distribution is self-contained.

full rationale

The paper proposes a new Markov modelling approach, proves that the queue-length process N(t) is a Markov chain for the M/M_D/2 model, and derives an analytic solution for its stationary distribution. No quoted step reduces a claimed result to its inputs by construction (e.g., no fitted parameter renamed as prediction, no self-definitional loop where the Markov property is assumed to prove itself, and no load-bearing self-citation chain). The derivation relies on an explicit proof of the Markov property and standard balance equations for the stationary distribution, which are externally verifiable against Markov chain theory and do not presuppose the final performance measures. This is the normal case of a self-contained mathematical argument.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

Review performed from abstract only; ledger entries are inferred from stated model components and standard queueing assumptions.

free parameters (1)
  • correlation parameter
    A parameter quantifying positive dependence between the two exponential service times must be introduced to define the M/M_D/2 model.
axioms (2)
  • domain assumption Customer arrivals follow a Poisson process
    Explicitly stated in the abstract for the M/M_D/2 queue.
  • domain assumption Service times are exponentially distributed and positively correlated
    Core modeling choice defining the M/M_D/2 system in the abstract.

pith-pipeline@v0.9.0 · 5696 in / 1268 out tokens · 59678 ms · 2026-05-22T16:14:08.099622+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

30 extracted references · 30 canonical work pages

  1. [1]

    and Levy, H

    Avi-Itzhak, B. and Levy, H. (2001) Bufferr equirement and server ordering in a tandem queue with correlated service times,Mathematics of Operations Research,26(2), 358–74

    work page 2001

  2. [2]

    (1979) On a tandem queueing model with identical service times at both counters, IAdvances in applied probability,11(3), 616–643

    Boxma, O.J. (1979) On a tandem queueing model with identical service times at both counters, IAdvances in applied probability,11(3), 616–643

    work page 1979

  3. [3]

    (1979) On a tandem queueing model with identical service times at both counters, IIAdvances in applied probability,11(3), 644–659

    Boxma, O.J. (1979) On a tandem queueing model with identical service times at both counters, IIAdvances in applied probability,11(3), 644–659

    work page 1979

  4. [4]

    and Deng, Q

    Boxma, O.J. and Deng, Q. (2000) Asymptotic behavior of the tandem queueing system with identical service times at both queues,Mathematical Methods of Operations Research,52, 307–23

    work page 2000

  5. [5]

    (1998) Tandem queues with blocking: A comparison between dependent and independent service,Operations Research,46(3), 424–429

    Browning, S.G. (1998) Tandem queues with blocking: A comparison between dependent and independent service,Operations Research,46(3), 424–429

    work page 1998

  6. [6]

    (1979) The message channel, a tandem interconnection of queues, Part I,IBM Report RC 6868

    Calo, S.B. (1979) The message channel, a tandem interconnection of queues, Part I,IBM Report RC 6868

    work page 1979

  7. [7]

    (1980) The message channel, a tandem interconnection of queues, Part II,IBM Report RC 7170

    Calo, S.B. (1980) The message channel, a tandem interconnection of queues, Part II,IBM Report RC 7170

    work page 1980

  8. [8]

    (1909) The theory of probabilities and telephone conversations,Ny Tidsskrift for Matematik, B,20, 33–39

    Erlang, A.K. (1909) The theory of probabilities and telephone conversations,Ny Tidsskrift for Matematik, B,20, 33–39

    work page 1909

  9. [9]

    and Conolly, B

    Hoon Choo, Q. and Conolly, B. (1980) Waiting time analysis for a tandem queue with corre- lated service,European journal of operational research,4(5), 337–345

    work page 1980

  10. [10]

    (1989) Random neural networks with negative and positive signals and product form solution,Neural Computation,1, 502–510

    Gelenbe, E. (1989) Random neural networks with negative and positive signals and product form solution,Neural Computation,1, 502–510

    work page 1989

  11. [11]

    (1991) Product-form queueing networks with negative and positive customers, Journal of Applied Probability,28, 656–663

    Gelenbe, E. (1991) Product-form queueing networks with negative and positive customers, Journal of Applied Probability,28, 656–663

    work page 1991

  12. [12]

    (1960) Waiting lines with heterogeneous servers,Operations Research,8, 504–511

    Gumbel, H. (1960) Waiting lines with heterogeneous servers,Operations Research,8, 504–511

    work page 1960

  13. [13]

    (1976) Networks of queues,Adv

    Kelly, F.P. (1976) Networks of queues,Adv. Appl. Prob.,8, 416–432

    work page 1976

  14. [14]

    (1979)Reversibility and Stochastic Networks, Wiley, Chichester

    Kelly, F.P. (1979)Reversibility and Stochastic Networks, Wiley, Chichester

    work page 1979

  15. [15]

    Kelly, F.P (1982) The throughput of a series of buffers,Adv. in Appl. Probab.,14, 633–653. 35

    work page 1982

  16. [16]

    (1964)Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, New York

    Kleinrock, L. (1964)Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, New York

    work page 1964

  17. [17]

    (2000)Continuous Multivariate Distributions: Models and Applications, John Wiley & Sons

    Kotz, S., Balakrishnan, N., and Johnson, N.L. (2000)Continuous Multivariate Distributions: Models and Applications, John Wiley & Sons

    work page 2000

  18. [18]

    (2019) The bivariate lack-of-memory distributions,Sankhy¯ a: The Indian Journal of Statistics,81, 273–297

    Lin, G.D., Dou, X., and Kuriki, S. (2019) The bivariate lack-of-memory distributions,Sankhy¯ a: The Indian Journal of Statistics,81, 273–297

    work page 2019

  19. [19]

    and Olkin, I

    Marshall, A.W. and Olkin, I. (1967) A multivariate exponential distribution,Journal of the American Statistical Association.62, 30–44

    work page 1967

  20. [20]

    and Beswick, C.A

    Mitchell, C.R., Paulson, A.S. and Beswick, C.A. (1977) The effect of correlated exponential service times on single server tandem queues,Naval Research Logistics Quarterly,24(1), 95– 112

    work page 1977

  21. [21]

    and Whitt, W

    Pang, G. and Whitt, W. (2012) Infinite-server queues with batch arrivals and dependent service times,Probability in the Engineering and Informational Sciences,26, 197–220

    work page 2012

  22. [22]

    and Whitt, W

    Pang, G. and Whitt, W. (2012) The impact of dependent service times on large-scale service systems,Manufacturing and Service Operations Management,14(2), 226–278

    work page 2012

  23. [23]

    and Whitt, W

    Pang, G. and Whitt, W. (2013) Two-parameter heavy-traffic limits for infinite-server queues with dependent service times,Queueing Systems,73(2), 119–146

    work page 2013

  24. [24]

    and Wolff, R.W

    Pinedo, M. and Wolff, R.W. (1982) A comparison between tandem queues with dependent and independent service times,Operations Research,30(3), 464–479

    work page 1982

  25. [25]

    (2007) Performance evaluation of dependent two-stage services,Proceedings of the 21st European Conference on Modelling and Simulation (ECMS), 74–9

    Sandmann, W. (2007) Performance evaluation of dependent two-stage services,Proceedings of the 21st European Conference on Modelling and Simulation (ECMS), 74–9

    work page 2007

  26. [26]

    (2010) Delays in a series of queues: Independent versus identical service times, The IEEE symposium on Computers and Communications, 32–37

    Sandmann, W. (2010) Delays in a series of queues: Independent versus identical service times, The IEEE symposium on Computers and Communications, 32–37

    work page 2010

  27. [27]

    (2012) Delays in a series of queues with correlated service times,Journal of Network and Computer Applications,35(5), 1415–1423

    Sandmann, W. (2012) Delays in a series of queues with correlated service times,Journal of Network and Computer Applications,35(5), 1415–1423

    work page 2012

  28. [28]

    (1970) Two-server Markovian queues with balking: heterogeneous vs

    Singh, V.P. (1970) Two-server Markovian queues with balking: heterogeneous vs. homogeneous servers,Operations Research,18, 145–159

    work page 1970

  29. [29]

    (1982) Tandem queues with dependant service times in light traffic,Operations research,30, 619–635

    Wolff, R.W. (1982) Tandem queues with dependant service times in light traffic,Operations research,30, 619–635

    work page 1982

  30. [30]

    (1993) Tandem queues with correlate service times and finite capacity,Math

    Ziedins, I. (1993) Tandem queues with correlate service times and finite capacity,Math. O.R., 18, 901–915. 36

    work page 1993