short-paper

Queues with Redundancy: Latency-Cost Analysis

Authors:

Gauri Joshi,

Emina Soljanin,

Gregory WornellAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 43, Issue 2

Pages 54 - 56

https://doi.org/10.1145/2825236.2825258

Published: 16 September 2015 Publication History

Get Access

References

[1]

Flatto, L., and Hahn, S. Two parallel queues created by arrivals with two demands I. SIAM Journal on Applied Mathematics 44, 5 (1984), 1041--1053.

Crossref

Google Scholar

[2]

Joshi, G., Liu, Y., and Soljanin, E. Coding for fast content download. Allerton Conference on Communication, Control and Computing (Oct. 2012), 326--333.

Crossref

Google Scholar

[3]

Joshi, G., Liu, Y., and Soljanin, E. On the Delay-storage Trade-off in Content Download from Coded Distributed Storage. IEEE Journal on Selected Areas on Communications (May 2014).

Crossref

Google Scholar

[4]

Joshi, G., Soljanin, E., and Wornell, G. Efficient redundancy techniques for latency reduction in cloud systems. arXiv {cs.dc} (Aug. 2015).

Google Scholar

[5]

Nelson, R., and Tantawi, A. Approximate analysis of fork/join synchronization in parallel queues. 739--743.

Digital Library

Google Scholar

[6]

Shah, N., Lee, K., and Ramachandran, K. The mds queue: Analyzing the latency performance of erasure codes. IEEE International Symposium on Information Theory (July 2014).

Crossref

Google Scholar

[7]

Shah, N., Lee, K., and Ramchandran, K. When do redundant requests reduce latency? In Allerton Conference on Communication, Control and Computing (Oct. 2013), pp. 731--738.

Crossref

Google Scholar

[8]

Wang, D., Joshi, G., and Wornell, G. Using straggler replication to reduce latency in large-scale parallel computing (extended version). arXiv:1503.03128 {cs.dc} (Mar. 2015).

Google Scholar

Cited By

View all

Anton ERighter RVerloop I(2024)Efficient scheduling in redundancy systems with general service timesQueueing Systems: Theory and Applications10.1007/s11134-024-09904-3106:3-4(333-372)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s11134-024-09904-3
Rumyantsev ADolgaleva DGolovin A(2023)Steady-state performance analysis of multiserver queueing models with redundancyProgram Systems: Theory and ApplicationsПрограммные системы: теория и приложения10.25209/2079-3316-2023-14-1-55-9414:1(55-94)Online publication date: 2023
https://doi.org/10.25209/2079-3316-2023-14-1-55-94
Jinan RBadita ASarvepalli PParag P(2022)Latency Optimal Storage and Scheduling of Replicated Fragments for Memory Constrained ServersIEEE Transactions on Information Theory10.1109/TIT.2022.315218268:6(4135-4155)Online publication date: Jun-2022
https://doi.org/10.1109/TIT.2022.3152182
Show More Cited By

Queues with Redundancy: Latency-Cost Analysis
1. General and reference
  1. Cross-computing tools and techniques
2. Social and professional topics
  1. Professional topics
    1. Computing profession

Recommendations

Queues with Redundancy: Is Waiting in Multiple Lines Fair?
Problem definition: We study service systems where some (so-called “redundant”) customers join multiple queues simultaneously, enabling them to receive service in any one of the queues, while other customers join a single queue. Academic/practical ...
(N,n)-preemptive priority queues

In this paper, we propose a new priority discipline, called the (N,n)-preemptive priority discipline. Under this discipline, the preemption of the service of a low-class customer is determined by two thresholds N and n of the queue length of high-class ...
Preemptive Priority Queues

Customers of different priorities arrive at a counter in accordance with a Poisson process. The customers are served by a single server in order of priority and for each priority in order of arrival. Preemptive discipline is assumed. Three service ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 2

September 2015

79 pages

ISSN:0163-5999

DOI:10.1145/2825236

Editor:
Giuliano Casale
Imperial College London, London

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2015

Published in SIGMETRICS Volume 43, Issue 2

Check for updates

Qualifiers

Short-paper

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
227
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Anton ERighter RVerloop I(2024)Efficient scheduling in redundancy systems with general service timesQueueing Systems: Theory and Applications10.1007/s11134-024-09904-3106:3-4(333-372)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s11134-024-09904-3
Rumyantsev ADolgaleva DGolovin A(2023)Steady-state performance analysis of multiserver queueing models with redundancyProgram Systems: Theory and ApplicationsПрограммные системы: теория и приложения10.25209/2079-3316-2023-14-1-55-9414:1(55-94)Online publication date: 2023
https://doi.org/10.25209/2079-3316-2023-14-1-55-94
Jinan RBadita ASarvepalli PParag P(2022)Latency Optimal Storage and Scheduling of Replicated Fragments for Memory Constrained ServersIEEE Transactions on Information Theory10.1109/TIT.2022.315218268:6(4135-4155)Online publication date: Jun-2022
https://doi.org/10.1109/TIT.2022.3152182
Bedin AChiariotti FKucera SZanella A(2022)Optimal Latency-Oriented Coding and Scheduling in Parallel Queuing SystemsIEEE Transactions on Communications10.1109/TCOMM.2022.320010570:10(6471-6488)Online publication date: Oct-2022
https://doi.org/10.1109/TCOMM.2022.3200105
Mehmood FBaloch NHussain FAmin WHossain MZikria YYu H(2022)An efficient and cost effective application mapping for network-on-chip using Andean condor algorithmJournal of Network and Computer Applications10.1016/j.jnca.2021.103319200:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.jnca.2021.103319
Gardner KRighter R(2022)The cost of collaborationQueueing Systems: Theory and Applications10.1007/s11134-021-09721-y100:1-2(7-40)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11134-021-09721-y
Anton EAyesta UJonckheere MVerloop I(2021)On the Stability of Redundancy ModelsOperations Research10.1287/opre.2020.203069:5(1540-1565)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1287/opre.2020.2030
Anton EAyesta UJonckheere MVerloop I(2021)Improving the Performance of Heterogeneous Data Centers through RedundancyProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283334:3(1-29)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428333
Birke RPerez JQiu ZBorkqvist MChen L(2021)sPARE: Partial Replication for Multi-Tier Applications in the CloudIEEE Transactions on Services Computing10.1109/TSC.2017.278084514:2(574-588)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TSC.2017.2780845
Joshi GKaushal D(2021)Synergy via Redundancy: Adaptive Replication Strategies and Fundamental LimitsIEEE/ACM Transactions on Networking10.1109/TNET.2020.304751329:2(737-749)Online publication date: Apr-2021
https://doi.org/10.1109/TNET.2020.3047513
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Queues with Redundancy: Is Waiting in Multiple Lines Fair?

(N,n)-preemptive priority queues

Preemptive Priority Queues