On the Stability of Redundancy Models

References

• Adan I , Kleiner I , Righter R , Weiss G (2017) FCFS parallel service systems and matchings models. Proc. 11th EAI Internat. Con. Performance Evaluation Methodologies Tools 2017 VALUETOOLS (ACM, New York), 106–112.Google Scholar
• Ananthanarayanan G , Ghodsi A , Shenker S , Stoica I (2013) Effective straggler mitigation: Attack of the clones. Proc. 10th USENIX Conf. Networked Systems Design Implementation NSDI 2013 (USENIX Association, Berkeley, CA), 185–198.Google Scholar
• Ananthanarayanan G , Kandula S , Greenberg AG , Stoica I , Lu Y , Saha B , Harris E (2010) Reining in the outliers in map-reduce clusters using mantri. Proc. 9th USENIX Conf. Operating Systems Design Implementation OSDI 2010 (Vancouver, BC, Canada), 265–278.Google Scholar
• Ayesta U , Bodas T , Verloop IM (2018) On a unifying product form framework for redundancy models. Performance Evaluation 127–128(2018):93–119.Crossref, Google Scholar
• Ayesta U , Bodas T , Dorsman J , Verloop IM (2019) A token-based central queue with order-independent service rates. Preprint, submitted February 6, https://arxiv.org/abs/1401.02121902.02137.Google Scholar
• Baccelli F , Foss S (1995) On the saturation rule for the stability of queues. J. Appl. Probability 32(2):494–507.Google Scholar
• Bonald T , Comte C (2017) Balanced fair resource sharing in computer clusters. Performance Evaluation 116(2017):70–83.Crossref, Google Scholar
• Bonald T , Massoulié L (2001) Impact of fairness on Internet performance. Proc. 2001 ACM SIGMETRICS Internat. Conf. Measurement Modeling Computer Systems (ACM, New York), 82–91.Google Scholar
• Bramson M (2008) Stability of Queueing Networks (Springer, New York). Google Scholar
• Dean J , Barroso LA (2013) The tail at scale. Comm. ACM 56(2013):74–80.Crossref, Google Scholar
• Gardner K , Hyytia E , Righter R (2019) A little redundancy goes a long way: Convexity in redundancy systems. Performance Evaluation 131(2019):22–42.Google Scholar
• Gardner K , Harchol-Balter M , Scheller-Wolf A , van Houdt B (2017a) A better model for job redundancy: Decoupling server slowdown and job size. IEEE/ACM Trans. Networking 25(6):3353–3367.Crossref, Google Scholar
• Gardner K , Harchol-Balter M , Scheller-Wolf A , Velednitsky M , Zbarsky S (2017b) Redundancy-d: The power of d choices for redundancy. Oper. Res. 65(4):1078–1094.Link, Google Scholar
• Gardner K , Zbarsky S , Doroudi S , Harchol-Balter M , Hyytiä E , Scheller-Wolf A (2016) Queueing with redundant requests: Exact analysis. Queueing Systems 83(3–4):227–259.Crossref, Google Scholar
• Gast N , Gaujal B (2012) Markov chains with discontinuous drifts have differential inclusions limits. Performance Evaluation 69:623–642.Crossref, Google Scholar
• Hellemans T , van Houdt B (2018a) Analysis of redundancy(d) with identical replicas. ACM SIGMETRICS Performance Evaluation Rev. 46(3):1–6.Google Scholar
• Hellemans T , van Houdt B (2018b) On the power-of-d-choices with least loaded server selection. Proc. ACM Measurement Anal. Comput. Systems June 2018 (ACM, New York), 27:1–22.Google Scholar
• Joshi G , Soljanin E , Wornell G (2015) Queues with redundancy: Latency-cost analysis. Performance Evaluation Rev. 43(2):54–56.Crossref, Google Scholar
• Koole G , Righter R (2007) Resource allocation in grid computing. J. Scheduling 11:163–173.Google Scholar
• Lee K , Pedarsani R , Ramchandran K (2017a) On scheduling redundant requests with cancellation overheads. IEEE/ACM Trans. Networking 25(2):1279–1290. https://doi: 10.1109/TNET.2016.2622248.Crossref, Google Scholar
• Lee K , Shah NB , Huang L , Ramchandran K (2017b) The mds queue: Analysing the latency performance of erasure codes. IEEE Trans. Inform. Theory 63(5):2822–2842. https://doi: 10.1109/TIT.2017.2674671.Google Scholar
• Paganini F , Tang A , Ferragut A , Andrew L (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Automatic Control 57(3):579–591. https://doi: 10.1109/TAC.2011.2160013.Crossref, Google Scholar
• Raaijmakers Y , Borst S , Boxma O (2018) Redundancy scheduling with scaled Bernoulli service requirements. Preprint, submitted November 15, https://arxiv.org/abs/1811.06309.Google Scholar
• Reiman MI , Simon B (1988) An interpolation approximation for queueing systems with poisson input. Oper. Res. 36(3):454–469.Link, Google Scholar
• Robert P (2003) Stochastic Networks and Queues (Springer-Verlag, New York). Crossref, Google Scholar
• Shah NB , Lee K , Ramchandran K (2016) When do redundant requests reduce latency? IEEE Trans. Comm. 64(2):715–722. https://doi: 10.1109/TCOMM.2015.2506161.Crossref, Google Scholar
• Vulimiri A , Brighten Godfrey P , Mittal R , Sherry J , Ratnasamy S , Shenker S (2013) Low latency via redundancy. CoNEXT 13: Proc. 9th ACM Conf. Emerging Networking Experiments Tech. 2013 (ACM, New York), 283–294.Google Scholar
• Walrand J (1990) Queueing networks. Heyman D, Sobel M, eds. Stochastic Models, vol. 2 of Handbooks in Operations Research and Management Science (Elsevier, New York), 519–603).Google Scholar