How is real-time computing defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?
$\begingroup$
$\endgroup$
6
-
6$\begingroup$ Are you looking for a formal definition? What do you hope to obtain from such a definition? Or are you more interesting in a computational model that takes into account time? $\endgroup$– Dave ClarkeJul 15, 2011 at 15:52
-
$\begingroup$ Just like Raphael said, my experience is that "real time" is mostly an engineering term. I believe some definitions of "real time" computing amount to "A hard real-time problem is one for which the correctness of algorithms solving it depends on the amount of time taken to finish the computation," or something along those lines. Given this definition, I find Raphael's proposed formalization in terms of some kind of constant-time complexity metric pretty reasonable. In other words, what he said. $\endgroup$– aegrisomniaJul 15, 2011 at 20:06
-
$\begingroup$ Such models might also have been studied in descriptive complexity (which is strongly related to complexity of queries in databases). $\endgroup$– KavehJul 18, 2011 at 19:27
-
$\begingroup$ @Kaveh: How is query complexity related to real-time computing? $\endgroup$– Dave ClarkeJul 18, 2011 at 20:58
-
$\begingroup$ @Dave, just a guess. Someone might have studied real-time database access. $\endgroup$– KavehJul 19, 2011 at 1:35
|
Show 1 more comment
5 Answers
$\begingroup$
$\endgroup$
Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something.' Now you have to decide what a 'something' is but let me give a concrete example. Let's say that the input arrives one symbol at a time and you want to output the answer to a query as soon as a new symbol arrives. If calculating that output takes constant time per new symbol then you might say the algorithm runs in real-time. An example of this is real-time exact string matching, which outputs whether a pattern matches the latest suffix of a text in constant time per new symbol. The text is assumed to arrive one symbol at a time.
However, an engineering answer will be less worried about "constant time" and more worried about it happening fast in practice and in particular fast enough that the result can be used by the time it is needed. So for example in robotics, if you want to play ping-pong it is useful for the robot to be able to work out where the ball is and move to hit it as the ball arrives, and not after the ball has passed. The asymptotic time complexity of the underlying algorithms will perhaps be of less interest there than just the observation that the code works out the location quickly enough. To give another example, if you want to render video and can do it at 25 frames per second then it is reasonable to say that the rendering is happening in real-time.
So basically you have two answers. One for the theoreticians/algorithmists and one that just says that you are doing the work as you need it on the fly.
EDIT: I should probably add that one extra feature one should require of even a constant time algorithm is that the time complexity is not amortised. In this context, real-time == unamortised constant time.
$\begingroup$
$\endgroup$
Maybe related to your question, you can look at streaming algorithms. This model has some "real-time" flavor in some sense.
You can also look at results on real-time language recognition by cellular automata. For instance this paper. There are quite a lot of papers on this subject.
$\begingroup$
$\endgroup$
Contrary to the various vague uses, I argue that:
Real-time computing in general is about the degree to which task time constraints are satisfied acceptably well with acceptable predictability according to application- and situation-specific acceptability criteria, given the current circumstances (overloads, failures, etc.). The general case of real-time is soft real-time. Hard real-time is a special case about always meeting all hard deadlines (not all deadlines are hard). Most systems that are real-time to any significant degree are soft.
I explain this in detail at http://real-time.org/_new/Print2HTML/Microsoft_PowerPoint_-_new_rt.org_draft_0.html.
$\begingroup$
$\endgroup$
I have a feeling you're looking for a model that reflects the engineering meaning of "real time", but let me just point out there is something that theorists call real time (and is inspired by engineering "real time"). Look at this post by Lipton and the references there: http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/
answered Sep 26, 2011 at 15:46
$\begingroup$
$\endgroup$
I would say "real-time" means you have contracts on the behavior of the machine over time; specifically with regards to how long a function will take to execute, and ordering guarantees when the system has a choice of multiple tasks to complete.
