Heavy tails in queueing systems: impact of parallelism on tail performance. (English) Zbl 1262.68024

Summary: We quantify the efficiency of parallelism in systems that are prone to failures and exhibit power law processing delays. We characterize the performance of two prototype schemes of parallelism, ‘redundant’ and ‘split’, in terms of both the power law exponent and exact asymptotics of the delay distribution tail. We also develop the optimal splitting scheme which ensures that split always outperforms redundant.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60G99 Stochastic processes
Full Text: DOI Euclid


[1] Andersen, L. N. and Asmussen, S. (2008). Parallel computing, failure recovery, and extreme values. J. Statist. Theory Appl. 2 , 279-292. · doi:10.1080/15598608.2008.10411875
[2] Asmussen, S. (2003). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 1029.60001
[3] Asmussen, S. et al. (2008). Asymptotic behavior of total times for jobs that must start over if a failure occurs. Math. Operat. Res. 33 , 932-944. · Zbl 1213.90096 · doi:10.1287/moor.1080.0329
[4] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation (Encyclopedia Math. Appl. 27 ). Cambridge University Press. · Zbl 0617.26001
[5] Cantor, D. G. and Gerla, M. (1974). Optimal routing in a packet-switched computer network. IEEE Trans. Comput. 23 , 1062-1069. · Zbl 0291.90031 · doi:10.1109/T-C.1974.223806
[6] Gallager, R. G. (1977). A minimum delay routing algorithm using distributed computation. IEEE Trans. Commun. 25 , 73-85. · Zbl 0361.68086 · doi:10.1109/TCOM.1977.1093711
[7] Hoekstra, G., Mei, R., Nazarathy, Y. and Zwart, B. (2009). Optimal file splitting for wireless networks with concurrent access. In NET-COOP ’09: Proc. 3rd Euro-NF Conf. on Network Control and Optimization (Lecture Notes Comput. Sci. 5894 ), Springer, Berlin, pp. 189-203. · Zbl 1266.68071
[8] Jelenković, P. and Momčilović, P. (2003). Large deviation analysis of subexponential waiting times in a processor-sharing queue. Math. Operat. Res. 28 , 587-608. · Zbl 1082.60083 · doi:10.1287/moor.28.3.587.16396
[9] Jelenković, P. R. and Tan, J. (2007). Is ALOHA causing power law delays? In Proc. 20th Internat. Teletraffic Congress (Lecture Notes Comput. Sci. 4516 ), Springer, Berlin, pp. 1149-1160.
[10] Jelenković, P. R. and Tan, J. (2007). Can retransmissions of superexponential documents cause subexponential delays? In Proc. IEEE INFOCOM ’07 , pp. 892-900.
[11] Jelenković, P. R. and Tan, J. (2007). Characterizing heavy-tailed distributions induced by retransmissions. Tech. Rep. EE2007-09-07, Department of Electrical Engineering, Columbia University. Available at http:// arxiv.org/abs/0709.1138v2. · Zbl 1287.60045 · doi:10.1239/aap/1363354105
[12] Kleinrock, L. (1964). Communication Nets: Stocastic Message Flow and Delay . McGraw-Hill, New York. · Zbl 0137.11906
[13] Nagaev, S. V. (1979). Large deviations of sums of independent random variables. Ann. Prob. 7 , 745-789. · Zbl 0418.60033 · doi:10.1214/aop/1176994938
[14] Sheahan, R., Lipsky, L., Fiorini, P. and Asmussen, S. (2006). On the completion time distribution for tasks that must restart from the beginning if a failure occurs. In ACM SIGMETRICS Performance Evaluation Review , Association for Computing Machinery, New York, pp. 24-26.
[15] Tan, J. and Shroff, N. (2010). Transition from heavy to light tails in retransmission durations. In Proc. INFOCOM ’10 (San Diego, California), IEEE Press, Piscataway, NJ, pp. 1334-1342.
[16] Tan, J., Yang, Y., Shroff, N. B. and Gamal, H. E. (2011). Delay asymptotics with retransmissions and fixed rate codes over erasure channels. In Proc. INFOCOM ’11 , IEEE Press, Piscataway, NJ, pp. 1260-1268.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.