Big jobs arrive early: From critical queues to random graphs

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.