Access Restriction

Author Zbarsky, Samuel ♦ Harchol-Balter, Mor ♦ Gardner, Kristen ♦ Scheller-Wolf, Alan ♦ Velednitsky, Mark
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract An increasingly prevalent technique for improving response time in queueing systems is the use of redundancy. In a system with redundant requests, each job that arrives to the system is copied and dispatched to multiple servers. As soon as the first copy completes service, the job is considered complete, and all remaining copies are deleted. A great deal of empirical work has demonstrated that redundancy can significantly reduce response time in systems ranging from Google's BigTable service to kidney transplant waitlists. We propose a theoretical model of redundancy, the Redundancy- d system, in which each job sends redundant copies to d servers chosen uniformly at random. We derive the first exact expressions for mean response time in Redundancy-d systems with any finite number of servers. We also find asymptotically exact expressions for the distribution of response time as the number of servers approaches infinity.
Description Affiliation: Carnegie Mellon University (Gardner, Kristen; Zbarsky, Samuel; Harchol-Balter, Mor; Scheller-Wolf, Alan) || UC Berkeley (Velednitsky, Mark)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-01-10
Publisher Place New York
Journal ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number 44
Issue Number 2
Page Count 3
Starting Page 33
Ending Page 35

Open content in new tab

   Open content in new tab
Source: ACM Digital Library