On the Power of (even a little) Centralization in Distributed Processing
We propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model, a fraction p of an available resource is deployed in a centralized manner (e.g., to serve a most loaded station) while the remaining fraction 1-p is allocat...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81190 https://orcid.org/0000-0003-2658-8239 |
| Summary: | We propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model, a fraction p of an available resource is deployed in a centralized manner (e.g., to serve a most loaded station) while the remaining fraction 1-p is allocated to local servers that can only serve requests addressed specifically to their respective stations.
Using a fluid model approach, we demonstrate a surprising phase transition in steady-state delay, as p changes: in the limit of a large number of stations, and when any amount of centralization is available (p>0), the average queue length in steady state scales as log [subscript 1/1-p] 1/1-λ when the traffic intensity λ goes to 1. This is exponentially smaller than the usual M/M/1-queue delay scaling of 1/1-λ, obtained when all resources are fully allocated to local stations (p=0). This indicates a strong qualitative impact of even a small degree of centralization.
We prove convergence to a fluid limit, and characterize both the transient and steady-state behavior of the finite system, in the limit as the number of stations N goes to infinity. We show that the queue-length process converges to a unique fluid trajectory (over any finite time interval, as N → ∞), and that this fluid trajectory converges to a unique invariant state v[superscript I], for which a simple closed-form expression is obtained. We also show that the steady-state distribution of the N-server system concentrates on v[superscript I] as N goes to infinity. |
|---|