The DOI matches its Crossref record.
Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure Occurs
Open accessAbstract
Many processes must complete in the presence of failures. Different systems respond to task failure in different ways. The system may resume a failed task from the failure point (or a saved checkpoint shortly before the failure point), it may give up on the task and select a replacement task from the ready queue, or it may restart the task. The behavior of systems under the first two scenarios is well documented, but the third (RESTART) has resisted detailed analysis. In this paper we derive tight asymptotic relations between the distribution of task times without failures and the total time when including failures, for any failure distribution. In particular, we show that if the task-time distribution has an unbounded support, then the total-time distribution H is always heavy tailed. Asymptotic expressions are given for the tail of H in various scenarios. The key ingredients of the analysis are the Cramér–Lundberg asymptotics for geometric sums and integral asymptotics, which in some cases are obtained via Tauberian theorems and in some cases by barehand calculations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The generic channel with failures model results in power law distributions when the distributions of L and A have a matrix exponential representation.
“It was first recognized in [6] that this model results in power law distributions when the distributions of L ≡ L ∞ and A have a matrix exponential representation, and this result was rigorously proved and further generalized in [3], [11], and [16].”
From Distribution of the Number of Retransmissions of Bounded Documents (2015) · cites this paper as [3]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 23
- Andersen L. N., 2008, J. Statist. Theory Appl.
- 10.1142/2779 · DOI
- Asmussen S., 2003, Applied Probability and Queues
- 10.1017/CBO9780511721434 · DOI
- 10.1080/15326349908807140 · DOI
- Castillo X., 1980, Proc. FTCS-10, 187
- Chimento P. F., 1993, IEEE Trans. Comput., 42
- 10.1007/PL00008926 · DOI
- DePrisco R., 1994, Proc. 13th ACM PODC, 161
- 10.1239/aap/1143936149 · DOI
- 10.1002/j.1538-7305.1982.tb03096.x · DOI
- 10.1109/INFCOM.2007.109 · DOI
- Jelenković P., 2007, Workshop of Transient and Asymptotic Analysis of Queues
- 10.1007/978-94-017-1693-2 · DOI
- 10.1137/1125070 · DOI
- Kartashov N. V., 1982, Teor. Veoryuatnost. i Mat. Statist., 27, 51
- 10.1016/0164-1212(86)90038-5 · DOI
- 10.2307/1427109 · DOI
- Lipsky L., 2007, Queueing Theory. A Linear Algebraic Approach
- Müller A., 2002, Comparison Methods for Stochastic Models and Risks
- 10.1145/1215956.1215967 · DOI · Paper page
- 10.1080/07474949608836348 · DOI
- Willmot G. E., 2001, Lecture Notes in Statistics, 156
Cited by
Sorted by citations
Distribution of the Number of Retransmissions of Bounded Documents
Jelenković, P. R., & Skiani, E. D. (2015) · Advances in Applied Probability · doi:10.1239/aap/1435236982 · Cited by 7
“It was first recognized in [6] that this model results in power law distributions when the distributions of L ≡ L∞ and A have a matrix exponential representation, and this result was rigorously proved and further generalized in [3], [11], and [16].”
Result
Metadata
- Authors
- Asmussen, S., Fiorini, P., Lipsky, L., Rolski, T., & Sheahan, R.
- Affiliations
- Aarhus University (DK)
- University of Southern Maine (US)
- University of Connecticut (US)
- University of Wrocław (PL)
- Venue
- Mathematics of Operations Research
- Published
- 2008-11
- Volume
- 33
- Issue
- 4
- Pages
- 932-944
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2128919822
- Cited by
- 60
- References
- 0
- Citations by year
- 2024: 5 · 2022: 1 · 2020: 2 · 2019: 1 · 2018: 2 · 2017: 2 · 2016: 4 · 2015: 8 · 2014: 3 · 2013: 6 · 2012: 6
- FWCI
- 12.91
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Mathematics of Operations Research (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Queuing Theory Analysis
- Social Sciences › Decision Sciences › Management Science and Operations Research › Probability and Risk Models
- Physical Sciences › Engineering › Safety, Risk, Reliability and Quality › Reliability and Maintenance Optimization
- Keywords
- task failure, heavy-tailed distributions, asymptotic analysis, integral asymptotics, Tauberian theorems, checkpointing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
