Big jobs arrive early: From critical queues to random graphs

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review


We consider a queue to which only a finite pool of n customers can arrive, at times depending on their service requirement. A customer with stochastic service requirement S arrives to the queue after an exponentially distributed time with mean S for some α ∈ [0,1]; therefore, larger service requirements trigger customers to join earlier. This finite-pool queue interpolates between two previously studied cases: α = 0 gives the so-called Δ(i) /G/1 queue and α = 1 is closely related to the exploration process for inho-mogeneous random graphs. We consider the asymptotic regime in which the pool size n grows to infinity and establish that the scaled queue-length process converges to a diffusion process with a negative quadratic drift. We leverage this asymptotic result to characterize the head start that is needed to create a long period of activity. We also describe how this first busy period of the queue gives rise to a critically connected random forest.

Originele taal-2Engels
Pagina's (van-tot)310-334
Aantal pagina's25
TijdschriftStochastic Systems
Nummer van het tijdschrift4
StatusGepubliceerd - dec 2020

Vingerafdruk Duik in de onderzoeksthema's van 'Big jobs arrive early: From critical queues to random graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit