CTA: A Correlation-Tolerant Analysis of the Deadline-Failure Probability of Dependent Tasks
Filip Markovic, Pierre Roux, Sergey Bozhko, Alessandro V. Papadopoulos, Björn B. Brandenburg
Abstract
Estimating the worst-case deadline failure probability (WCDFP) of a real-time task is notoriously difficult, primarily because a task's execution time typically depends on prior activations (i.e., history dependence) and the execution of other tasks (e.g., via shared inputs). Previous analyses have either assumed that execution times are probabilistically independent (which is unrealistic and unsafe), or relied on complex upper-bounding abstractions such as probabilistic worst-case execution time (pWCET), which mask dependencies with pessimism. Exploring an analytically novel direction, this paper proposes the first closed-form upper bound on WCDFP that accounts for dependent execution times. The proposed correlation-tolerant analysis (CTA), based on Cantelli's inequality, targets fixed-priority scheduling and requires only two basic summary statistics of each task's ground- truth execution time distribution: upper bounds on the mean and standard deviation (for any possible job-arrival sequence). Notably, CTA does not use pWCET, nor does it require the full execution-time distribution to be known. Core parts of the analysis have been verified with the Coq proof assistant. Empirical comparison with state-of-the-art WCDFP analyses reveals that CTA can yield significantly improved bounds (e.g., a lower WCDFP than any pWCET-based method for 70% of the workloads tested at 90% pWCET utilization and 60% average utilization). Beyond accuracy gains, the favorable results highlight the potential of the previously unexplored analytical direction underlying CTA.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Probabilistic Response-Time-Aware Search for Transient Astrophysical Phenomena cites What Really is pWCET? A Rigorous Axiomatic Proposal
- Monte Carlo Response-Time Analysis cites Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests
- Towards Principled Budget Enforcement in Real-Time Systems cites What Really is pWCET? A Rigorous Axiomatic Proposal
- Critical Instant for Probabilistic Timing Guarantees: Refuted and Revisited cites Monte Carlo Response-Time Analysis
- Critical Instant for Probabilistic Timing Guarantees: Refuted and Revisited cites Efficiently Approximating the Worst-Case Deadline Failure Probability Under EDF
Cited by top-tier papers2
Builds on6
- Generating Utilization Vectors for the Systematic Evaluation of Schedulability TestsDavid Griffin, Iain Bate, Robert I. DavisRTSS 2020 · 71 citations
- Monte Carlo Response-Time AnalysisSergey Bozhko, Georg von der Brüggen, Björn B. BrandenburgRTSS 2021 · 28 citations
- Efficiently Approximating the Worst-Case Deadline Failure Probability Under EDFGeorg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen et al.RTSS 2021 · 18 citations
- What Really is pWCET? A Rigorous Axiomatic ProposalSergey Bozhko, Filip Markovic, Georg von der Brüggen, Björn B. BrandenburgRTSS 2023 · 16 citations
- Critical Instant for Probabilistic Timing Guarantees: Refuted and RevisitedKuan-Hsun Chen, Mario Günzel, Georg von der Brüggen, Jian-Jia ChenRTSS 2022 · 15 citations
Related papers
- A Distribution-Agnostic and Correlation-Aware Analysis of Periodic TasksFilip Markovic, Georg von der Brüggen, Mario Günzel, Jian-Jia Chen et al.RTSS 2024 · 5 citations
- Reducing Worst-Case Deadline Failure Probability for EDF SchedulingFei Guan, Xu Jiang, Weipeng Jing, Nan GuanRTSS 2025
- Analytical Approximations in Probabilistic Analysis of Real-Time SystemsFilip Markovic, Thomas Nolte, Alessandro Vittorio PapadopoulosRTSS 2022 · 9 citations
- In Search of Butterflies: Exceedance Analysis for Real-Time Systems under Transient OverloadMatteo Zini, Filip Markovic, Daniel Casini, Alessandro Biondi et al.RTSS 2024 · 1 citation
- Reliability Test based on a Binomial Experiment for Probabilistic Worst-Case Execution TimesLuis Fernando Arcaro, Karila Palma Silva, Rômulo Silva de Oliveira, Luís AlmeidaRTSS 2020 · 2 citations
