John N. Tsitsiklis
ABSTRACT
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 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 vI, for which a simple closed-form expression is obtained. We also show that the steady-state distribution of the N-server system concentrates on vI as N goes to infinity.
Supplemental Material
- M. Bramson. State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems: Theory and Applications, 30: pp. 89--148, 1998. Google Scholar
Digital Library
- S.N. Ethier and T.G. Kurtz. Markov Processes: Characterization and Convergence (2nd edition). Wiley-Interscience, 2005.Google Scholar
- N.D. Vvedenskaya, R.L. Dobrushin, and F.I. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Probl. Inf. Transm, 32(1): pp. 20--34, 1996.Google Scholar
- M. Mitzenmacher. The power of two choices in randomized load balancing. Ph.D. thesis, U.C. Berkeley, 1996. Google ScholarDigital Library
- M. Alanyali and M. Dashouk. On power-of-choice in downlink transmission scheduling. Inform. Theory and Applicat. Workshop, U.C. San Diego, 2008.Google ScholarCross Ref
- N. Gast and B. Gaujal. Mean field limit of non-smooth systems and differential inclusions. INRIA Research Report, 2010.Google ScholarDigital Library
- M. Bramson, Y. Lu, and B. Prabhakar. Randomized load balancing with general service time distributions. ACM Sigmetrics, New York, 2010. Google ScholarDigital Library
- M. Mitzenmacher, A. Richa, and R. Sitaraman. The power of two random choices: A survey of techniques and results. Handbook of Randomized Computing: Volume 1, pp. 255--312, 2001.Google ScholarCross Ref
- G.J. Foschini and J. Salz. A basic dynamic routing problem and diffusion. IEEE Trans. on Comm. 26: pp. 320--327, 1978.Google ScholarCross Ref
- Y.T. He and D.G. Down, On accommodating customer flexibility in service systems. INFOR, 47(4): pp. 289--295, 2009.Google Scholar
- J.N. Tsitsiklis and K. Xu, On the power of (even a little) centralization in distributed processing (Technical Report). http://web.mit.edu/jnt/www/Papers/TXSIG11.pdf.Google Scholar
Index Terms
- On the power of (even a little) centralization in distributed processing
Recommendations
On the power of (even a little) centralization in distributed processing
Performance evaluation reviewWe 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 ...
Transform-free analysis of the GI/G/1/K queue through the decomposed Little's formula
In this paper, we consider the steady-state queue length distribution of the GI/G/1/K queue. As a result, we obtain transform-free expressions for the steady-state queue length distributions at an arrival, at a departure and at an arbitrary time, all in ...
Optimal Control of a Multiclass, Flexible Queueing System
<P>We consider a general class of queueing systems with multiple job types and a flexible service facility. The arrival times and sizes of incoming jobs are random, and correlations among the sizes of arriving job types are allowed. By choosing among a ...
Comments