Big jobs arrive early: From critical queues to random graphs

Gianmarco Bet, Remco Van Der Hofstad, Johan S.H. Van Leeuwaarden

Research output: Contribution to journalArticleScientificpeer-review


We consider a queue to which only afinite pool ofncustomers can arrive,at times depending on their service requirement. A customer with stochastic servicerequirementSarrives to the queue after an exponentially distributed time with meanS-αforsomeα∈[0,1]; therefore, larger service requirements trigger customers to join earlier. Thisfinite-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 sizengrows to infinity and establish that the scaled queue-length process converges to a dif-fusion process with a negative quadratic drift. We leverage this asymptotic result tocharacterize the head start that is needed to create a long period of activity. We alsodescribe how thisfirst busy period of the queue gives rise to a critically connected randomforest.
Original languageEnglish
Pages (from-to)310-334
JournalStochastic Systems
Issue number4
Publication statusPublished - 1 Dec 2020


Dive into the research topics of 'Big jobs arrive early: From critical queues to random graphs'. Together they form a unique fingerprint.

Cite this