Lune

RTSS2024Top-tier venue

A Distribution-Agnostic and Correlation-Aware Analysis of Periodic Tasks

Filip Markovic, Georg von der Brüggen, Mario Günzel, Jian-Jia Chen, Björn B. Brandenburg

Abstract

Real-time tasks often exhibit correlated execution-time distributions due to common factors such as shared caches, resources, and inputs. Yet state-of-the-art probabilistic analysis still overlooks the impact of correlation, a gap that has been highlighted as a major open problem in the field. This paper responds to the open problem with the first correlation-aware analysis (CAA) of periodic tasks with stochastic execution times. The proposed analysis, which derives response-time distributions to infer upper bounds on deadline-failure probabilities, applies to a novel task model that incorporates information about both intra- and inter-task dependencies. In addition, the paper shows how to statistically infer the two model parameters using confidence intervals obtained via nonparametric bootstrapping. Notably, the inference method described is distribution-agnostic, meaning that it does not assume any particular probability distribution a priori, thereby eliminating a major risk of misclassifying the ground-truth execution behavior. By design, CAA dominates state-of-the-art correlation-tolerant analysis (CTA). The significantly better accuracy of CAA is demonstrated via experiments with synthetically generated workloads, while a case study based on the WATERS’ 17 industrial challenge provides a proof-of-concept of the statistical inference method.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Probabilistic Response-Time-Aware Search for Transient Astrophysical PhenomenaDaisy Wang, Marion Sudvarg, Filip Markovic, Jeremy Buhler et al.RTSS 2025

Related papers

  1. 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
  2. Monte Carlo Response-Time AnalysisSergey Bozhko, Georg von der Brüggen, Björn B. BrandenburgRTSS 2021 · 28 citations
  3. Towards Principled Budget Enforcement in Real-Time SystemsJoseph Goh, James H. AndersonRTSS 2024 · 1 citation
  4. 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
  5. 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
Dusk over the sea between two cliffs drawn in fine vertical lines