From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: X-Spam-Status: No, score=0.8 required=3.0 tests=BAYES_50 autolearn=ham autolearn_force=no version=3.4.5-pre1 Date: 21 Oct 92 18:34:52 GMT From: 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) Subject: Re: What is "real-time"? Message-ID: <1c47scINNqon@tobor.cs.utexas.edu> List-Id: 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).