Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems

arXiv:2211.01720 · eess.SY, cs.SY, math.ST, stat.TH · Submitted 2022-11-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems".

Dev: Here's the gist of the paper. Response times must be bounded to ensure safe failure rates in real-time systems The paper focuses on using the central limit of response times and an approximation with an inverse Gaussian mixture distribution to estimate failure rates This method provides a practical and simple implementation of backlog estimation using an adapted Expectation-Maximization algorithm to estimate failure rates System Modeling and Definitions The paper considers periodic tasks on a single core system where priorities are ordered decreasingly, meaning the most critical tasks are completed first A task is characterized by its execution time, period, and arrival rate of jobs Key performance metrics include utilization levels like the k-level mean utilization and maximum utilization, as well as deviation measures The system's stationarity is assumed to ensure that the estimation is independent on the arrival time of jobs Response times are defined based on a fixed-priority discarding scheduling policy, where a job is discarded if it misses its deadline Failure Rate Estimation via Mixture Models The failure rate of a task is defined as the limit of the probability that its response time exceeds its period The paper proposes an approximation for this failure rate using a mixture of Inverse Gaussian (IG) distributions This approximation is derived by relating the response time distribution to the central limit theorem built in

1: The estimated failure rate, denoted as ∆IGi, is found by approximating the integral of the response time probability density function using a finite sum based on an IG mixture model Parameter Estimation via EM Algorithm The estimation of the parameters for this IG mixture model—specifically the backlog distribution and its components—is achieved through an adapted Expectation-Maximization (EM) algorithm The E-step involves computing the conditional expectation of a latent variable indicating which component a response time belongs to, and the M-step maximizes this likelihood by computing the best suited parameters, such as the backlog in our case The algorithm is adapted to a reparametrization of the IG distribution that reduces the number of parameters and increases convergence speed Validation and Goodness-of-Fit The quality of the estimation is assessed using goodness-of-fit tests, such as checking if normalized response times are Chi-squared distributed The paper uses the Bayesian Information Criteria (BIC) to choose the number of mixture components (degrees of freedom), favoring more parsimonious models A key test involves checking if normalized response times are Chi-squared distributed as shown in Proposition 3 Simulations and hardware-in-the-loop (HITL) data demonstrate that the estimation is accurate, especially for large quantiles, when mean utilization approaches 1 Future Directions and Applications The work suggests using this statistical learning method to improve scheduling algorithms by incorporating estimated parameters into scheduling decisions Future research can adapt this framework to Earliest Deadline First (EDF) scheduling, extending the central limit derivation from

1: to that paradigm Furthermore, incorporating estimated failure rates into load-balancing processes for multicore partitioned scheduling is proposed as a next step The method can also be used to build an independence test adapted to real-time systems by leveraging the Chi-squared property of IG distributions In this work, we both provide a theoretical and approximated bound on the failure rates of stationary rate-monotonic real-time systems More than bounds, we provide a method that one could potentially improve scheduling algorithms by estimating parameters with inference The estimation is built through an EM algorithm, but this method is not unique and hopefully some more techniques will improve the proposed method The paper concludes that the proposed method can also be useful in the case of dependent execution times References

Paper summary: Rosa: So, looking at "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems", what we've seen is that the authors provide both a theoretical bound on failure rates and an estimation method using an EM algorithm based on inverse Gaussian mixtures.

Dev: The paper tackles the problem of bounding response times in rate monotonic systems by relating them to the central limit theorem and approximating their distribution with an inverse Gaussian mixture >

Rosa: The implication is that we get a way to estimate failure rates practically, rather than just relying on theoretical bounds which only tell you if a system is safe or not >

Taro: It’s about moving from just knowing the rules of the game to actually estimating how likely things are to go wrong in specific operational scenarios, especially when utilization gets high >

Dev: The method is built through an EM algorithm, but they caution that this specific approach isn't unique and that other techniques could improve on it, so it’s a starting point for more research >

Rosa: Overall, the paper gives us a practical tool to estimate failure rates in these stationary rate monotonic systems using statistical modeling of response times >

Conclusion: Rosa: So we're wrapping up this look at "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems."

Dev: Basically, they’ve put together a way to get an estimate of how likely a task is to fail because its response time goes over its period.

Rosa: It moves beyond just saying a system might be safe or not and gives you a statistical handle on the actual failure rates.

Dev: They use this central limit idea, which they connect to their response time distribution, and then they approximate it using an inverse Gaussian mixture model.

Rosa: That approximation is done through an expectation maximization algorithm that’s been tweaked to make the math work faster.

Dev: The authors test this out with simulations and even some hardware in the loop data, showing it actually works well for things like large response times when the system utilization gets close to one hundred percent.

Rosa: It gives us a practical way to get a number that tells us about reliability without having to run every single possible scenario.

Dev: The core idea is taking those estimated parameters, like the backlog distribution in this case, and plugging them back into scheduling decisions.

Rosa: If we can use these failure rate estimates to actually change how the scheduler makes its choices, that could lead to systems that are much more robust under real-world stress.

Dev: But they also flag some things, like the method being dependent on assumptions about stationarity and the choice of those mixture components.

Rosa: Exactly. It’s a tool for inference, not a perfect crystal ball for every single system configuration out there right now.

Dev: So it's a solid step forward for building better real-time systems, but there’s still plenty of work to do to make this method even more general and applicable across different scheduling policies.

Kevin Zagalo, Avner Bar-Hen

inria · Cnam Paris

eess.SY, cs.SY, math.ST, stat.TH

Submitted: 2022-11-03

Updated: 2026-10-27

Comments: Accepted to IEEE Transactions on Computers

DOI: 10.1109/TC.2026.3742489

Code: https://github.com/kevinzagalo/rInverseGaussian

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 78/100

The gist: Response times must be bounded to ensure safe failure rates (also known as deadline miss probabilities) in real-time systems <ref:2211.01720#pg6> The paper focuses on using the central limit of…

Key concepts

Response Time
The time it takes for a task to complete its execution, considering the arrival of jobs. In this paper, response times are analyzed under fixed-priority discarding scheduling policies where tasks miss deadlines if their response time exceeds their period.
Failure Rate
The probability that a task's response time exceeds its period. This is defined as the limit of this probability for stationary systems and is crucial for determining system reliability and schedulability.
Inverse Gaussian (IG) Mixture Distribution
An approximation used to model the distribution of response times. The paper uses a mixture of IG distributions to approximate the true response time distribution, simplifying complex calculations by using a finite sum instead of integrating the full probability density function.

Terminology

Summary

Response times must be bounded to ensure safe failure rates (also known as deadline miss probabilities) in real-time systems <ref:2211. p. 0

Where the paper says it

Many everyday embedded systems, within devices such as airplanes, cars, trains, and spatial probes, operate as real-time systems. To ensure safe failure rates (also known as deadline miss probabilities), response times must be bounded.

01720#pg6> The paper focuses on using the central limit of response times built in [1] and an approximation of their distribution with an inverse Gaussian mixture distribution <ref:2211. p. 0
Where the paper says it

Rate Monotonic real-time systems prioritize tasks according to their arrival rate. This paper focuses on the use of the central limit of response times built in [1] and an approximation of their distribution with an inverse Gaussian mixture distribution.

01720#pg4> Extensive simulations demonstrate that the method is well-suited for the approximation of failure rates <ref:2211. p. 0
Where the paper says it

The distribution parameters and their associated failure rates are estimated through a suitable re-parameterization of the inverse Gaussian distribution and an adapted Expectation-Maximization algorithm. Extensive simulations demonstrate that the method is well-suited for the approximation of failure rates.

01720#pg4>

System Modeling and Definitions

The paper considers periodic tasks on a single core system where task prioritization ensures that the most critical and time-sensitive tasks are completed first to meet deadlines <ref:2211.01720#pg5> A task is characterized by its execution time Ci, with a p. p. 1

Where the paper says it

Task prioritization ensures that the most critical and time-sensitive tasks are completed first to meet deadlines. A task γi is characterized by: 1) its execution time Ci , with a p.

d.f. fi of non-negative and finite support [cmini, cmaxi] and a period pi > 0 <ref:2211. p. 1
Where the paper says it

fi of non-negative and finite support [c min i , cmax i ]. 2) its period pi > 0.

01720#pg5> The mean utilization uk is defined as the k-level mean utilization of Γ as uk = k/i=1 λiE[Ci] <ref:2211. p. 1
Where the paper says it

Let us first introduce some concepts that will be used throughout this paper. 1 Utilization Let us define P k-level mean utilization of Γ as uk = k i=1 λiE[Ci ].

01720#pg5> Stationarity is assumed, meaning that the distribution of the number of jobs arrived in an interval [s, t] is the same as the one over any time interval [u, u + t − s] of size t − s <ref:2211. p. 1
Where the paper says it

4 Stationarity We assume the stationarity of Γ, that we define as the stationarity of all demand processes Wi(t) = PNi(t) j=1 Ci,j , where Ni(t) = P∞ j=1 1[0,t](Ai,j ) is the process counting the jobs of the task γi arrived before instant t ≥ 0. This means that we assume that the distribution of the number of jobs arrived in an interval [s, t] is the same as the one over any time interval [u, u + t − s] of size t − s, i.

01720#pg5> The response time Ri,j can be written as Ri,j = inf[t > 0: βi(Ai,j + t) = 0] <ref:2211. p. 2
Where the paper says it

Hence, it depends on the scheduling policy. For a fixed-prioity discarding scheduling policy, the response time Ri,j can be written as Ri,j = inf{t > 0 : βi(Ai,j + t) = 0}.

01720#pg5>

Failure Rate Estimation Methodology

The paper proposes a method to estimate failure rates by approximating the response time distributions using an inverse Gaussian mixture model <ref:2211.01720#pg4> The key steps involve:

- Theoretical evidence, and extensive simulations, showing that inverse Gaussian mixtures are a suited prior distribution for response times, hence for failure rate estimation <ref:2211.01720#pg4>

- A practical and simple implementation of backlog estimation using an adapted EM algorithm accounting for the statistics of execution times, in order to estimate failure rates <ref:2211.01720#pg4>

The failure rate is estimated through the parameterization provided in Section 3.1, leading to the approximated failure rate ∆IGi = Z ∞ pi h(r;πi, βi)dr <ref:2211. p. 2

Where the paper says it

of the execution time of the task of index i ui mean utilization of level i of Γ umax i maximum utilization of level i of Γ vi standard deviation of level i of Γ vmax i maximum deviation of level i of Γ Ri,j response time of the j-th job of the task of index i Ri response time of the mixture of all jobs of the task of index i hi p. of the response time of the mixture of all jobs of the task of index i Ai,j arrival time of the j-th job of the task of index i Ni counting process of the task of index i Oi offset -arrival time of the first job- of the task of index i pi time separating two consecutive jobs of the task of index i λi rate of arrival of the jobs of the task of index i βi,j backlog of jobs of index strictly lower than i at time Ai,j βˆ i,j approximation of βi,j mi,j distribution of the backlog of jobs of index strictly lower than i at time Ai,j πi distribution of the backlog of index strictly lower than i πi,k weight of the k-th component of the mixture of the response time of the task of index i πˆi,k approximation of πi,k Ki degree of freedom of the approximated failure rate for the task of index i ψ(r; ξ, δ) p.

01720#pg5> The final approximated failure rate is given by ∆IGi = X Ki k=1 πi,k " 1 − Ψ pi;βi,k 1 − ui,β2v 2i! <ref:2211.01720#pg5>

Parameter Estimation via EM Algorithm

An adapted Expectation-Maximization algorithm is used to estimate the parameters of the mixture of IG probability density functions (p.d.f.) <ref:2211. p. 0

Where the paper says it

We outline how to build such adaptive algorithms using the proposed approach in Section 5. The starting point of the failure rate estimation provided in this work is the central limit of response times built in [1], pushing the inverse Gaussian (IG) distribution as a natural arXiv:2211.

01720#pg4> The E-step involves computing the conditional expectation of Zi given (πi, βi) = π(s)i, β(s)i <ref:2211. p. 5
Where the paper says it

The degree of freedom Ki is estimated in the following section. 1 E-step For the (s + 1)th step of the EM algorithm, z (s) i the conditional expectation of Zi given (πi , βi ) = π (s) i , β (s) i is given by z (s) i,j,k = π (s) i,kψi rj ; β (s) i,k h rj ;π (s) i , β (s) i .

01720#pg5> The M-step maximizes the complete log-likelihood Lc(Zi,πi, βi) by maximizing each of the Ki expressions using Newton-like algorithms <ref:2211. p. 5
Where the paper says it

, Ki , (12) and maximizing ℓc2 with respect to β is maximizing each of the Ki expressions Xn j=1 z (s) i,j,k log ψi(rj ; βi,k), k = 1, . , Ki , using Newton-like algorithms (c.

01720#pg4> The degree of freedom Ki is chosen using the Bayesian Information Criteria (BIC) to select a parsimonious model <ref:2211. p. 6
Where the paper says it

The impact of the k-means initialization is extensively studied in [27] in the case of Gaussian mixtures, and shown to outperform standard initialization methods (random, agglomerative hierarchical clustering and sumscore). 4 Degrees of freedom of the mixture of IG The Bayesian Information Criteria (BIC, [28]) is used to chose the degrees of freedom (d.

01720#pg5>

Validation and Goodness-of-Fit

The quality of the MLE is checked by using the link of IG distributions of the jobs of a given task with the χ2 1 distribution <ref:2211.01720#pg5> Proposition 3 states that the failure rate of the IG estimation is equal to ∆IGi = X Ki k=1 πi,k " 1/pi > βi,k 1 − ui−Φ (pi − βi,k 1 − ui)2/νipi! <ref:2211.01720#pg5> Simulations show that when the mean utilization goes to 1, the empirical response time data converges to the inverse Gaussian model <ref:2211. p. 7

Where the paper says it

5: Mean Squared Error (MSE) between the empirical distribution of the simulations and the MLE distribution, of 1 000 instances of the schedule, for the task set shown in Table 2. This figure shows how the empirical response time data converges to the inverse Gaussian model when the mean utilization goes to 1, when assuming both the D/G/1/FP and D/M/1/FP models.

01720#pg5>

Future Directions

Future work can adapt these mechanisms to Earliest Deadline First (EDF) scheduling by extending the central-limit derived from [1] to EDF scheduling <ref:2211.01720#pg5> Incorporating estimated failure rates in the load-balancing process for multicore partitioned scheduling is suggested as a first step towards multicore partitioning <ref:2211. p. 8

Where the paper says it

We claim that incorporating estimated failure rates in the load-balancing process allows to infer the actual latent state of the system into the scheduling decisions. We thus focused on estimating the parameters of failure rates for fixed priority single core scheduling using prior knowledge on the response times distributions, as a first step towards multicore partitioned scheduling.

01720#pg5> The method can also be useful in the case of dependent execution times, though its strong reliance on independence is noted <ref:2211. p. 9
Where the paper says it

However, we have shown how to use it to also detect if execution time are indeed independent. We do not investigate in this paper the reliability of such method, but rather suggest that our method can also be useful in the case of dependent execution times.

01720#pg5>

Appendix A Proof of Proposition 1

The proof for Proposition 1 shows that with Ci,j = x and i−1 k=1 βk(Ai,j) = y, Ri,j converges to an inverse Gaussian variable of mean x+y 1−ui and variance (x+y)2v 2i when ui gets close to 1 <ref:2211.01720#pg5>

Appendix B Proof of Proposition 2

The proof for Proposition 2 uses Hoeffding’s inequality to derive an upper-bound on the conditional probability in (19) <ref:2211.01720#pg5>

Appendix C Proof of Proposition 3

The proof for Proposition 3 uses (15) with (11) and θ = β 1−ui and x = g(r; θ) to show the relationship between normalized response time and the Chi-squared distribution <ref:2211.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. How to improve response time estimation in real-time systems by using an adapted Expectation-Maximization algorithm to estimate parameters of a mixture of Inverse Gaussian distributions, which is a practical and simple implementation of backlog estimation using an adapted EM algorithm accounting for the statistics of execution times.

  2. The improved AI system can perform adaptive scheduling by estimating during run-time the distribution and/or the component where response times belong, as outlined in Section 1.1. This allows for an adaptive scheduling method taking failure rates into account to be incorporated directly into the scheduling process itself.

  3. The system can utilize a re-parameterized Inverse Gaussian distribution, denoted as rIG, which reduces the number of parameters of the mixture model and increases the speed of convergence [of] the estimation algorithm as well as the stability of the estimates.

  4. Failure rates for stationary rate monotonic real-time systems can be estimated using a formula derived from Equation 11, specifically the approximated failure rate is DeltaIG i = X Ki k=1 (1 - Psi pi; beta i,k 1 - ui, beta i2 v squared i !).

  5. The improved system can use the Bayesian Information Criteria to choose the number of components in the mixture model by calculating Ki as argmax k 2 l n(pi, beta i) - (2k - 1) log n, leading to more parsimonious models suitable for estimating during the scheduling process, hence with a small sample size.

  6. The system can perform a goodness-of-fit test on the estimated parameters by checking if "Pn j=1 P delta i(Ri,j - xi hat i) squared / xi squared i Ri,j > Phi-1(1 - alpha) <= n alpha for all alpha in (0, 1)," as shown in Section 4.2.

Abstract

Real-time systems consist of a set of tasks, a scheduling policy, and a system architecture, all constrained by timing requirements. Many everyday embedded systems, within devices such as airplanes, cars, trains, and spatial probes, operate as real-time systems. To ensure safe failure rates, response times-the time required for the exection of a task-must be bounded. Rate Monotonic real-time systems prioritize tasks according to their arrival rate. This paper focuses on the use of the central limit of response times built in and an approximation of their distribution with an inverse Gaussian mixture distribution. The distribution parameters and their associated failure rates are estimated through a suitable re-parameterization of the inverse Gaussian distribution and an adapted Expectation-Maximization algorithm. Extensive simulations demonstrate that the method is well-suited for the approximation of failure rates. We discuss the extension of such method to a chi-squared independence test adapted to real-time systems.

Related papers