The DOI matches its Crossref record.
Probabilistic accuracy bounds for fault-tolerant computations that discard tasks
Abstract
We present a new technique for enabling computations to survive errors and faults while providing a bound on any resulting output distortion. A developer using the technique first partitions the computation into tasks. The execution platform then simply discards any task that encounters an error or a fault and completes the computation by executing any remaining tasks. This technique can substantially improve the robustness of the computation in the face of errors and faults. A potential concern is that discarding tasks may change the result that the computation produces.Our technique randomly samples executions of the program at varying task failure rates to obtain a quantitative, probabilistic model that characterizes the distortion of the output as a function of the task failure rates. By providing probabilistic bounds on the distortion, the model allows users to confidently accept results produced by executions with failures as long as the distortion falls within acceptable bounds. This approach may prove to be especially useful for enabling computations to successfully survive hardware failures in distributed computing environments.Our technique also produces a timing model that characterizes the execution time as a function of the task failure rates. The combination of the distortion and timing models quantifies an accuracy/execution time tradeoff. It therefore enables the development of techniques that purposefully fail tasks to reduce the execution time while keeping the distortion within acceptable bounds.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Cited by
Managing performance vs. accuracy trade-offs with loop perforation
Sidiroglou-Douskos, S., Misailovic, S., Hoffmann, H., & Rinard, M. (2011) · Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering · doi:10.1145/2025113.2025133 · Cited by 505
Self-citationGreen: a framework for supporting energy-conscious programming using controlled approximation
Baek, W., & Chilimbi, T. M. (2010) · Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1806596.1806620 · Cited by 440
Dynamic knobs for responsive power-aware computing
Hoffmann, H., Sidiroglou, S., Carbin, M., Misailovic, S., Agarwal, A., & Rinard, M. (2011) · Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems · doi:10.1145/1950365.1950390 · Cited by 304
Self-citationAn Analysis of the Search Spaces for Generate and Validate Patch Generation Systems
Long, F., & Rinard, M. (2016) · Proceedings of the 38th International Conference on Software Engineering · doi:10.1145/2884781.2884872 · Cited by 167
Self-citation
Metadata
- Authors
- Rinard, M.
- Venue
- Proceedings of the 20th annual international conference on Supercomputing
- Publisher
- ACM
- Published
- 2006-06-28
- Pages
- 324-334
- OpenAlex
- W2014620461
- Cited by
- 183
- References
- 0
- FWCI
- 2.10
- Type
- conference paper
- Language
- en
- Open access
- closed
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. https://app.cochat.ai/papers/10.1145/1183401.1183447
- The paper
- Rinard, M. (2006). Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. Proceedings of the 20th annual international conference on Supercomputing. https://doi.org/10.1145/1183401.1183447
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.