How to prove that a system is real-time?

I'm writing a paper on the system I designed which upon receiving an event, performs a number of calculations and publishes the result to several subscribers. I can calculate the amount of time it takes from the moment the system is informed about the event, to the moment when all subscribers successfully received the calculation results. I perform multiple experiments to measure the amount of time for a various number of subscribers.

In my paper, I'm claiming that my system is capable of real-time responses to the first event. Could you please give me some hints that how I can prove that based on the data I collected? Thanks

• You need to show that the latency is very low, not only in the average case but also with high probability. You can plot the percentiles of the latency distribution (up to a change of axes, this is the CDF of the latency distribution). – Yuval Filmus Jun 27 '17 at 19:58

You need to provide a more precise description of your system and real-time requirements.

If you are interested in only the timeliness and timeliness predictability of the response to the first event, your question is about that one event response and not about the subsequent events responses and thus the system.

You didn't specify your required timeliness and timeliness predictability for responding to that event. It sounds like you are satisfied with your empirical measurements for subsequent responses to varied numbers of recipients. So for the first event response, you need to specify your desired response time constraint, such as a deadline. Then you need to specify the desired predictability of that response's timeliness.

Perhaps you want to a' priori know that the deadline will always be met--i.e., that the response is deterministic (deterministic is one end-point on the scale of predictability). If so, you need to identify what presumptions about your system and its execution environment you make for that prediction; that is called a system model.

Your question indicates that your measurements do not cause you to expect that subsequent responses be deterministic--instead you expect that if the first response is deterministic, your subsequent response measurements have been empirically predicted accurately.

There is a large body of literature about determining worst case execution times (the first response latency in your case), and the presumptions that are necessary for those times to be accurate. Formal proof that your first response time is deterministic may or may not be feasible, depending on the unstated presumptions you are making. (In general, such proofs get rapidly more difficult as more things are presumed to be more dynamic instead of all being static.)

But if instead of requiring that the first response time be deterministic, you are either satisfied with or forced to concede that your system model provides a non-deterministic first response time, you have to explicitly deal with the response time predictability.

There is a vast body of theory and practice on that topic in general (although not in the conventional real-time computing field).

In your case, you could simply do sensitivity experiments to measure and establish bounds on the variability of the first response timeliness, by varying parameters of your system model.

To convert that into analytical predictability, you can do probability distribution function fitting. For example, perhaps your measured first response times are normally distributed with means and variances based on your measurements. While not a proof, that gives you an analytical way to reason about that response time.

• My answer is discussed in detail on real-time.org (which I am currently updating). – E. Douglas Jensen Sep 6 '17 at 19:16

It depends on your definition of "real-time system". A standard definition is: a system is real-time if it will respond within $T$ seconds, with probability at least $P$. Here you need to fill in the parameters $T,P$; e.g., it might be $T = 1$ millisecond and $P = 0.999$.

How do you prove that this condition is met? One way is to find a way to generate random workloads, from the same distribution as the system will be exposed to in practice, and count how often the system meets the deadline and how often it doesn't. Another way is to prove a theorem (e.g., with formal methods) about the maximum time it might take to respond; see the literature on worst-case execution time analysis. The latter might be particularly challenging in many cases.

There's an entire literature on this topic, that you can read more about.

• Your answer refers to "system" when his question is focused on a single task (the first event response time). Even if the OP can prove that task is "real-time" by which he implies that it is deterministic (or even if he is satisfied with bounds or perhaps a pdf), that says nothing about the real-time properties of the rest of his system. That works for him, since he has empirically measured the subsequent event response times, thus characterizing how "real-time" the whole system is. Your answer would not be considered acceptable to the real-time computing community since they require P=1.0. – E. Douglas Jensen Jul 1 '17 at 14:06
• @E.DouglasJensen, OK -- thank you for writing a better answer! – D.W. Jul 1 '17 at 14:40