Lune

RTSS2021Top-tier venue

Monte Carlo Response-Time Analysis

Sergey Bozhko, Georg von der Brüggen, Björn B. Brandenburg

Abstract

Determining a soft or firm real-time task’s probabilistic worst-case response time is a central goal when quantifying and bounding the probability of deadline misses, but current approaches are either (i) fast, but coarse-grained analytical bounds without precision guarantees, (ii) based on convolution and suffer from high space and time complexity, or (iii) combine convolution with resampling techniques that accrue pessimism in an uncontrolled manner. As a new alternative, this paper provides the first probabilistic response-time analysis method based on Monte Carlo simulation, which provides a controlled trade-off between analysis runtime, the desired degree of accuracy, and the permissible probability of a misestimate. An evaluation shows the proposed Monte Carlo analysis to routinely provide more accurate worst-case deadline failure probability (WCDFP) estimates than prior approaches, especially when considering large task sets (where prior methods struggle). In particular, it is shown to scale to workloads with up to 500 tasks while achieving one to three orders of magnitude better precision than analytical or convolution-based approaches (given an equivalent time budget).

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • CTA: A Correlation-Tolerant Analysis of the Deadline-Failure Probability of Dependent Tasks cites Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests
  • CTA: A Correlation-Tolerant Analysis of the Deadline-Failure Probability of Dependent Tasks cites Critical Instant for Probabilistic Timing Guarantees: Refuted and Revisited
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. 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
  2. CTA: A Correlation-Tolerant Analysis of the Deadline-Failure Probability of Dependent TasksFilip Markovic, Pierre Roux, Sergey Bozhko, Alessandro V. Papadopoulos et al.RTSS 2023 · 8 citations

Builds on1

  1. Generating Utilization Vectors for the Systematic Evaluation of Schedulability TestsDavid Griffin, Iain Bate, Robert I. DavisRTSS 2020 · 71 citations

Related papers

  1. 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
  2. Reducing Worst-Case Deadline Failure Probability for EDF SchedulingFei Guan, Xu Jiang, Weipeng Jing, Nan GuanRTSS 2025
  3. 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
  4. Analytical Approximations in Probabilistic Analysis of Real-Time SystemsFilip Markovic, Thomas Nolte, Alessandro Vittorio PapadopoulosRTSS 2022 · 9 citations
  5. WCDFP Analysis for Real-Time Tasks with Stochastic Release Patterns using Chernoff BoundShining Sun, Chaohai Yu, Xu Jiang, Qingxu Deng et al.RTSS 2025
Dusk over the sea between two cliffs drawn in fine vertical lines