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 |
| _version_ | 1826193641372123136 |
|---|---|
| author | Tsitsiklis, John N. Xu, Kuang |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. Xu, Kuang |
| author_sort | Tsitsiklis, John N. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:42:22Z |
| format | Article |
| id | mit-1721.1/81190 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:42:22Z |
| publishDate | 2013 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/811902022-09-26T13:16:11Z On the Power of (even a little) Centralization in Distributed Processing Tsitsiklis, John N. Xu, Kuang Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. Tsitsiklis, John N. Xu, Kuang 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. Irwin Mark Jacobs and Joan Klein Jacobs Presidential Fellowship Xerox Fellowship Program Thomas and Stacey Siebel Foundation (Scholarship) National Science Foundation (U.S.) (Grant CCF-0728554) 2013-09-26T14:17:12Z 2013-09-26T14:17:12Z 2011-06 Article http://purl.org/eprint/type/ConferencePaper 9781450308144 http://hdl.handle.net/1721.1/81190 John N. Tsitsiklis and Kuang Xu. 2011. On the power of (even a little) centralization in distributed processing. In Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems (SIGMETRICS '11). ACM, New York, NY, USA, 161-172. https://orcid.org/0000-0003-2658-8239 en_US http//dx.doi.org/10.1145/1993744.1993759 Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems (SIGMETRICS '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Tsitsiklis, John N. Xu, Kuang On the Power of (even a little) Centralization in Distributed Processing |
| title | On the Power of (even a little) Centralization in Distributed Processing |
| title_full | On the Power of (even a little) Centralization in Distributed Processing |
| title_fullStr | On the Power of (even a little) Centralization in Distributed Processing |
| title_full_unstemmed | On the Power of (even a little) Centralization in Distributed Processing |
| title_short | On the Power of (even a little) Centralization in Distributed Processing |
| title_sort | on the power of even a little centralization in distributed processing |
| url | http://hdl.handle.net/1721.1/81190 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT tsitsiklisjohnn onthepowerofevenalittlecentralizationindistributedprocessing AT xukuang onthepowerofevenalittlecentralizationindistributedprocessing |