On the maximum queue length in the supermarket model
<p style="text-align:justify;"> There are n queues, each with a single server. Customers arrive in a Poisson process at rate λn, where 0<λ<1. Upon arrival each customer selects d≥2 servers uniformly at random, and joins the queue at a least-loaded server among those ch...
Main Authors: | , |
---|---|
Format: | Journal article |
Published: |
Institute of Mathematical Statistics
2006
|
_version_ | 1797103629615759360 |
---|---|
author | Luczak, MJ McDiarmid, C |
author_facet | Luczak, MJ McDiarmid, C |
author_sort | Luczak, MJ |
collection | OXFORD |
description | <p style="text-align:justify;"> There are n queues, each with a single server. Customers arrive in a Poisson process at rate λn, where 0<λ<1. Upon arrival each customer selects d≥2 servers uniformly at random, and joins the queue at a least-loaded server among those chosen. Service times are independent exponentially distributed random variables with mean 1. We show that the system is rapidly mixing, and then investigate the maximum length of a queue in the equilibrium distribution. We prove that with probability tending to 1 as n→∞ the maximum queue length takes at most two values, which are lnlnn/lnd+O(1). </p> |
first_indexed | 2024-03-07T06:22:47Z |
format | Journal article |
id | oxford-uuid:f33d2d2c-a2c0-44e0-b229-7d9b9d3cf27a |
institution | University of Oxford |
last_indexed | 2024-03-07T06:22:47Z |
publishDate | 2006 |
publisher | Institute of Mathematical Statistics |
record_format | dspace |
spelling | oxford-uuid:f33d2d2c-a2c0-44e0-b229-7d9b9d3cf27a2022-03-27T12:10:37ZOn the maximum queue length in the supermarket modelJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f33d2d2c-a2c0-44e0-b229-7d9b9d3cf27aSymplectic Elements at OxfordInstitute of Mathematical Statistics2006Luczak, MJMcDiarmid, C <p style="text-align:justify;"> There are n queues, each with a single server. Customers arrive in a Poisson process at rate λn, where 0<λ<1. Upon arrival each customer selects d≥2 servers uniformly at random, and joins the queue at a least-loaded server among those chosen. Service times are independent exponentially distributed random variables with mean 1. We show that the system is rapidly mixing, and then investigate the maximum length of a queue in the equilibrium distribution. We prove that with probability tending to 1 as n→∞ the maximum queue length takes at most two values, which are lnlnn/lnd+O(1). </p> |
spellingShingle | Luczak, MJ McDiarmid, C On the maximum queue length in the supermarket model |
title | On the maximum queue length in the supermarket model |
title_full | On the maximum queue length in the supermarket model |
title_fullStr | On the maximum queue length in the supermarket model |
title_full_unstemmed | On the maximum queue length in the supermarket model |
title_short | On the maximum queue length in the supermarket model |
title_sort | on the maximum queue length in the supermarket model |
work_keys_str_mv | AT luczakmj onthemaximumqueuelengthinthesupermarketmodel AT mcdiarmidc onthemaximumqueuelengthinthesupermarketmodel |