Multi-Class Processes, Dual Points and M/M/1 Queues
2006, v.12, Issue 2, 175-201
We consider the discrete Hammersley - Aldous - Diaconis process (HAD) and the totally asymmetric simple exclusion process (TASEP) in Z. The basic coupling induces a multi-class process which is useful in discussing shock measures and other important properties of the processes. The invariant measures of the multi-class systems are the same for both processes, and can be constructed as the law of the output process of a system of multi-class queues in tandem; the arrival and service processes of the queueing system are a collection of independent Bernoulli product measures. The proof of invariance involves a new coupling between stationary versions of the processes called a multi-line process; this process has a collection of independent Bernoulli product measures as an invariant measure. Some of these results have appeared elsewhere and this paper is partly a review, with some proofs given only in outline. However we emphasize a new approach via dual points: when the graphical construction is used to construct a trajectory of the TASEP or HAD process as a function of a Poisson process in Z x R, the dual points are those which govern the time-reversal of the trajectory. Each line of the multi-line process is governed by the dual points of the line below. We also mention some other processes whose multi-class versions have the same invariant measures, and we note an extension of Burke's theorem to multi-class queues which follows from the results.
Keywords: totally asymmetric simple exclusion process,multi-type processes,Hammerley - Aldous - Diaconis process,multi-class queueing system