Re: What is "real-time"?

[dog.ee.lbl.gov!news!vela!m.cs.uiuc.edu!ux1.cso.uiuc.edu!uwm.edu!cs.utexas .edu!news-is-not-mail@ucbvax.Berkeley.EDU (Al Mok)]

This is an article that I posted a few years ago.

*This is a long message*

  Now that we have heard so many definitions of a real-time system,
I would like to take a different tack. I don't think definitions are
that important. If there are new and interesting problems, good people
will go solve them regardless of what they are called; and if we do
a good job, the folks in the trenches will eventually listen to us.
What we need to answer is why and how "time" enters into design
considerations in real-time systems. This is a fair question since
conventional wisdom dictates that programs should be designed to
function "correctly" independent of hardware speed. To answer this
question, consider the follow reasons why timing constraints are
necessary and/or desirable.

*  Time is an explicit parameter in ensuring system integrity in some
applications. For example, the control surfaces of some modern aircrafts
must be adjusted at a high rate to prevent catastrophic destruction. This
places an upper bound on the response time of the avionics software system.
Lower bounds are also needed, as in the case of an operating system which
requires a potential intruder to wait for some minimum time before retyping a
password that has been entered incorrectly. In these cases, the "physics"
of the application dictates the timing requirements.

*  Time is an essential synchronization mechanism for solving certain
task coordination problems. An example is the Byzantine Generals problem
for which it has been proven that there is no asynchronous solution.
However, a solution is possible if the generals adopt the synchronous
protocol of voting in rounds. Each round of voting imposes a timing
constraint on the good generals. Another example of time as an essential
synchronization mechanism is the self-stabilization problem of state machines
in a distributed environment. Here, a set of state machines are required
to always reach a safe configuration in the global (joint) state space in
a bounded number of steps from any initial configuration. The machines
are allowed to communicate with one another by passing messages only.
It has been proved that a solution to this problem is impossible unless
some form of timeout is allowed. A solution to this problem requires a
machine to be able to determine if a communication channel is empty, e.g.,
by asking the sender to stop sending and then examining the input buffer
after a set period of time. This imposes a timing constraint on the
communication network.
   It should be noted that timing constraints are required in the above two
examples to introduce synchrony so that the task coordination problems
can be solved. Even though timing constraints are not identified explicitly
as such (they are introduced by way of the control abstractions: voting in
rounds, testing for an empty channel), they are nevertheless needed to
solve the problems. I have a suspicision that there is an interesting
theory about how partial synchrony imposed by timing constraints can
help solve otherwise unsolvable reliability problems; I am really curious
about this. For those of you who are interested, Nancy Lynch and her group
at MIT are looking at the Byzantine Generals problem (again!) from this angle.

*  Time is a powerful control mechanism which can be exploited to solve
problems more efficiently. An example can be found in communication protocols
which use rate control to improve throughput, e.g., the NETBLT protocol
proposed by Dave Clark's group at MIT. In these protocols, the receiver
guarantees the sender that it will be able to process incoming packets 
at a certain rate, or alternatively, it will meet the deadline associated
with each packet. Since the sender does not need to wait for an acknowledge
from the receiver, network throughput can be significantly improved, especially
for networks where the round-trip transmission time is long compared
with the width of a packet. This is going to be very important for
fiber optics communication systems. Another example of time as a powerful
control mechanism is a solution to the distributed election problem in
the case of an Archimedean ring. Here, a set of processors arranged in a 
ring wants to elect a leader by passing messages around. It has been shown
that if the processors work at a pace that are not too different (at most
a bounded ratio) from one another, the number of messages that are required
to elect a leader can be reduced to less than the theoretical lower bound
required in the asychronous case.
  In reality, the world is often neither completely synchronous nor
completely asynchronous. I think the systolic array folks have
learned this lesson (correct me if I am wrong, you guys with Warped
minds out there). Timing constraints are a useful means to introduce partial
synchrony to systems. How we can exploit the partial synchrony to gain
efficiency is an open problem. I should point out that in this case, we should
design algorithms which must not cause catastrophic failure if a timing
constraint is not met. Rather, an exception may be generated and system
performance should be able to degrade gracefully. However, the important
point remains that our design objective is to meet the timing constraints.
If analysis shows that the timing constraints cannot be met, there is little
hope to reap the performance benefits.
  I am not advocating the imposition of arbitrary timing constraints;
a discipline needs to be developed to allow us to use timing constraints
as control mechanisms in a systematic way.

  Having said all of the above, let me give you an "academic definition"
of a real-time system which does not have the word "time" in it:

       A real-time system is one that must synchronize with processes whose
       progress it cannot directly control.

  But don't let this definition fool you into believing that you don't
need "time", as the foregoing discussion shows.

(Actually, my favorite response to the query "Define real-time system
research?" is: "Define VLSI research?" I am not saying this in jest; there
is indeed quite a bit of similarity between the two).