2014/03/31 by José Blanchet, Jose Blanchet, Blanchet, Jose +2 · 1 citation
Business, Management and Accounting · Computer Science · Decision Sciences · Mathematics · #Advanced Queuing Theory Analysis #Distributed systems and fault tolerance #FOS: Mathematics #Probability (math.PR) #Simulation Techniques and Applications #math.PR
paper · pdf · doi:10.48550/arxiv.1403.8117
30 pages, 3 figures, Journal
openalex publication_date 2014/03/31 · arxiv created 2015/01/21 · arxiv updated 2015/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide the first algorithm that under minimal assumptions allows to simulate the stationary waiting-time sequence of a single-server queue backwards in time, jointly with the input processes of the queue (inter-arrival and service times). The single-server queue is useful in applications of DCFTP (Dominated Coupling From The Past), which is a well known protocol for simulation without bias from steady-state distributions. Our algorithm terminates in finite time assuming only finite mean of the inter-arrival and service times. In order to simulate the single-server queue in stationarity until the first idle period in finite expected termination time we require the existence of finite variance. This requirement is also necessary for such idle time (which is a natural coalescence time in DCFTP applications) to have finite mean. Thus, in this sense, our algorithm is applicable under minimal assumptions.