In queueing theory, a discipline within the mathematical theory of probability, quasireversibility (sometimes QR) is a property of some queues. The concept was first identified by Richard R. Muntz and further developed by Frank Kelly. Quasireversibility differs from reversibility in that a stronger condition is imposed on arrival rates and a weaker condition is applied on probability fluxes. For example, an M/M/1 queue with state-dependent arrival rates and state-dependent service times is reversible, but not quasireversible. A network of queues, such that each individual queue when considered in isolation is quasireversible, always has a product form stationary distribution. Quasireversibility had been conjectured to be a necessary condition for a product form solution in a queueing network, but this was shown not to be the case. Chao et al. exhibited a product form network where quasireversibility was not satisfied.
Definition A queue with stationary distribution π {\displaystyle \pi } is quasireversible if its state at time t, x(t) is independent of
the arrival times for each class of customer subsequent to time t, the departure times for each class of customer prior to time t for all classes of customer.
Partial balance formulation Quasireversibility is equivalent to a particular form of partial balance. First, define the reversed rates q'(x,x') by
π ( x ) q ′ ( x , x ′ ) = π ( x ′ ) q ( x ′ , x ) {\displaystyle \pi (\mathbf {x} )q'(\mathbf {x} ,\mathbf {x'} )=\pi (\mathbf {x'} )q(\mathbf {x'} ,\mathbf {x} )}
then considering just customers of a particular class, the arrival and departure processes are the same Poisson process (with parameter α {\displaystyle \alpha } ), so
α = ∑ x ′ ∈ M x q ( x , x ′ ) = ∑ x ′ ∈ M x q ′ ( x , x ′ ) {\displaystyle \alpha =\sum _{\mathbf {x'} \in M_{\mathbf {x} }}q(\mathbf {x} ,\mathbf {x'} )=\sum _{\mathbf {x'} \in M_{\mathbf {x} }}q'(\mathbf {x} ,\mathbf {x'} )}
where Mx is a set such that x ′ ∈ M x {\displaystyle \scriptstyle {\mathbf {x'} \in M_{\mathbf {x} }}} means the state x' represents a single arrival of the particular class of customer to state x.
Examples Burke's theorem shows that an M/M/m queueing system is quasireversible. Kelly showed that each station of a BCMP network is quasireversible when viewed in isolation. G-queues in G-networks are quasireversible.
See also Time reversibility
References
