On the maximum queue length in the supermarket model
There are $n$ queues, each with a single server. Customers arrive in a Poisson process at rate $\lambda n$, where $0<\lambda<1$. Upon arrival each customer selects $d\geq2$ servers uniformly at random, and joins the queue at a least-loaded server among those chosen. Service times are i...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
2006
|
| _version_ | 1797082093567606784 |
|---|---|
| author | Luczak, M McDiarmid, C |
| author_facet | Luczak, M McDiarmid, C |
| author_sort | Luczak, M |
| collection | OXFORD |
| description | There are $n$ queues, each with a single server. Customers arrive in a Poisson process at rate $\lambda n$, where $0<\lambda<1$. Upon arrival each customer selects $d\geq2$ 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\to\infty$ the maximum queue length takes at most two values, which are $\ln\ln n/\ln d+O(1)$. |
| first_indexed | 2024-03-07T01:23:20Z |
| format | Journal article |
| id | oxford-uuid:911b6a0e-7fe7-4292-bf33-6aca459f53ab |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:23:20Z |
| publishDate | 2006 |
| record_format | dspace |
| spelling | oxford-uuid:911b6a0e-7fe7-4292-bf33-6aca459f53ab2022-03-26T23:16:25ZOn the maximum queue length in the supermarket modelJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:911b6a0e-7fe7-4292-bf33-6aca459f53abSymplectic Elements at Oxford2006Luczak, MMcDiarmid, CThere are $n$ queues, each with a single server. Customers arrive in a Poisson process at rate $\lambda n$, where $0<\lambda<1$. Upon arrival each customer selects $d\geq2$ 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\to\infty$ the maximum queue length takes at most two values, which are $\ln\ln n/\ln d+O(1)$. |
| spellingShingle | Luczak, M 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 luczakm onthemaximumqueuelengthinthesupermarketmodel AT mcdiarmidc onthemaximumqueuelengthinthesupermarketmodel |