On the validity of discrete event models
Stanislaw Raczynski
Universidad Panamericana, McLeod Institute for Simulation Sciences
Augusto Rodin 498, 03910 Mexico City, Mexico
Keywords: modeling, simulation, discrete events, validity
ABSTRACT
Discrete event models are commonly used while simulating queuing, manufacturing and similar systems. However, in some cases the concept of events, which duration is equal to zero may be too simplified and the validity of the model questionable. An alternative approach is proposed, called semi-discrete events that permits a finite duration of the event activity. This leads to a model specification where there is no conceptual difference between semi-discrete and continuous events. It is shown that discrete event models may be located in the points of discontinuity in the general space of models (may form singularities). This may have serious consequences, namely the validity of such models may result to be false.
INTRODUCTION
Discrete event models are commonly used in so-called discrete simulation. The other part of the simulation methodology and its implementations is called continuous simulation. These two branches of simulation seem to be totally different though some models are created using combined simulation when the two approaches are being mixed together with or without success. Observe that whatever would be the classification of a model we create, we always pretend to find an abstraction of the real world. Classifying the part of the real world as discrete or continuous, the modeler frequently looks at the real world through a (correct or false) mirror of the simulation tools he/she dominates. In fact, the things we observe in the real word do not divide into continuous and discrete. This is only the deficiency of our modeling tools that suggests such division. Consequently, we tend to see a mass service and queuing systems as "discrete" and to describe almost all apparently continuous physical processes by differential equations, even if no such equations for a given process exist at all.
In one of my previous articles a metric structure for the space of (all) models have been proposed (Raczynski, 1998). This permits us to talk about the convergence of sequences of models and about the continuity of certain mappings in the model space. The point of this article is to suggest that discrete event models may represent singularities in the model space, and certain mappings from a parameter space to the simulation results space may result to be discontinuous at the point when the discrete event model is located. This is closely related to the model validity.
THE DISCRETE TIME AND DISCRETE EVENTS
First of all, it should be emphasized that we will not enter neither into the relativistic approach to the concept of time, nor into the quantum physics. In both fields the time is something far more complicated that what our experience and intuition might indicate. Let us limit to the concept of the real time and the model time. Real time is what our (physical) clocks are trying to measure and indicate. The model time is just a variable in a simulation model, changing its value according to the calculations of the model trajectory. It can be represented by one model variable, or a set of variables, as sometimes occurs in the distributed simulation. Simulating the movements of a galaxy, the model time interval can reach billions of years, while the simulation run needs one hour of real time.
Historically, the model time in early simulation languages like Control and Simulation Language (CSL) used in the middle of the past century and in the early implementations of GPSS was discrete. Then, the new simulation languages used real variables to represent the continuously changing model time. Note that this "continuity" is always an illusion. In the real computer nothing is continuous and the (mathematical) real variables do not exist. Perhaps this is the reason why discrete events gained such a wide field of applications. Other obvious fact is the relatively low computing cost and the high velocity of the discrete-event simulations. Let take a look at the discrete event. This is the change in the model state that occurs in a discrete time instant. In other words, the length of the model time interval during which a discrete event occurs is equal to zero. One can say that the discrete event models are too simplified, because no real physical system can change its state in time zero. But this does not mean that discrete event models are invalid. Remember that what we are looking for are abstractions of the real world. Nobody pretends to create a model that reflects all what occurs in the reality. There are various criteria to check the model validity. Most of them refer to the abstraction or simplification operation that transforms the real model state into the state of a model. Roughly speaking, if the following two operations: transforming (simplifying) the model state and advancing in model and real time lead to the same result (model state) independently of the order we execute them, the model is said to be valid. However, this validity criterion only refers to state transformations and not to passing from a real system to a discrete event model (this rather refers to the model time handling).
Other measure of the model validity is how it approximates the reality. Any simplified model has some characteristics or parameters that, while changed, approximate better or worse the real system. One of such parameters can be the duration D of events. If this time interval is equal to zero, the model events become discrete. In other words, a discrete event model could be treated as the limit case of a series of models with finite duration D of single event execution, while D approaches zero. The question is how the simulation results change if D tends to zero. Let denote the set of the results (outputs) of our model by R(D). If the mapping M from the space of D values (real numbers space) into the results space is continuous, we can say that the discrete event model is valid, because when we pass from semi-discrete evens (with finite duration) to the discrete events model, R(D) tends to R(0) (D approaches zero). Unfortunately, in general, this is NOT the case. In other words, the results provided by a model with very small D could be completely different from the results of the corresponding discrete event model (when D=0). Let see some examples.
First, consider a simple physical system, shown at figure 1.
Figure 1. A model of an electric circuit.
Suppose that all elements of the circuit of figure 1 are ideal ones, so the conductors have resistance equal to zero and no inductance, the switch is an ideal on-off contact and the capacitors have no internal resistance or inductance. This is not an exaggerated simplification. Simulating electric circuit models we almost always make such assumptions. Now, suppose that the initial voltages of the capacitors are U = 1V, W = 0 and that the switch closes at time t = 1. The event we simulate consists in passing electric current through the resistance R, so that, finally, U = 0.5V and W = 0.5V (the capacitors are equal to each other). Theoretically, this event has an infinite duration, and the current approaches zero according to the exponential curve. But in our case we suppose that the event is over when the current is less then 0.001 its initial value. Obviously the duration of the event depends on the resistance R. The current is given by the following formula
Now, let pass with R to zero. The event duration D becomes small, and in the limit we have D = 0 with R = 0. The voltages of the two capacitors at the end of the event are always equal to each other, U = W = U(0)/2 = 0.5V. So, one could say that the model with R = 0 is a valid model of the circuit when R is very small. However, this is not the case. Consider the limit model (R = 0). The total circuit energy before the event (before closing the switch) is equal to U(0)2C/2 = 0.5C. After closing the switch the total energy accumulated in the two capacitors is equal to
So, where the half of the circuit energy disappeared? It is something wrong with the limit model; it is simply a wrong, invalid model of our circuit. If we ask the same question for the model with R>0 (even very small), there is no problem with the energy. A simple calculation of the transient process shows that the half of the initial energy always dissipates on the resistor, independently of its value. So, we cannot replace the model with, R equal to, for example, 0.00000000001ohms by the model with R = 0. From the mathematical point of view the mapping D -> R(D) mentioned before is not continuous at D = 0.
But the above example is perhaps not the most typical for discrete event applications, because it is rather a physical system. However, it shows that a discrete event may not be a limit case of a sequence of finite-duration events, and the discrete case may lie in a discontinuity point in the space of events. Generally speaking, the change of the model state must take certain time interval, because the energy cannot be transferred in time zero. Now, let us consider rather logical than physical model. In the logical problem statement the model state is a more generalized, abstract concept, though it might appear to be simple. In such models, mainly queuing, manufacturing, military etc. we have atomic models like queues or servers, and complex models composed by the smaller elements. There is a vast literature and important theoretical work done in the field, mainly the Discrete Event Specification Formalism (DEVS, see Zeigler 1976, Barros 1996, Chow 1996). What is common in all serious works on DEVS is the problem of simultaneous event treating. Once we admit discrete events, we must face this problem that implies model ambiguity and certain known logical conflicts caused by the possibility of simultaneous events. This is frequently overcome by adding a "select" element to the model specification. This is an algorithm or an additional rule that resolves possible conflicts. Note, however, that this is some artificial, implementation-dependent element that has no corresponding component in the real modeled system.
Any valid model of a real system cannot be language- or implementation-dependent. This means that the difference in the model output implemented on different platforms can differ only due to a particular computer and software resolution and cannot be completely different from each other in the qualitative and logical sense. This makes the treating of simultaneous evens difficult. While running simultaneous events on a single-processor machine, the events occur simultaneously in model time, but not in real time. Any event must be put at one or more event queues and the order of the simultaneous event execution may be random or may depend on the particular hardware or software (for example, the place in the source code where the event specification has been located). This order has nothing to do with any property of the modeled system, but may influence dramatically the simulation results, making the model invalid.
Take a look at the simple model of a duel. The rules are as follows. Two duelists wait for the signal from a judge, in the initial position A (figure 2). When the signal comes, each of them starts walking forward, and when the following signal comes, they turn back and shoot (position B). A simple rule is that each duelist is a perfect shooter, so his bullet kills his adversary after a small time interval. However, he cannot shoot being hit by the shot of the other one and killed. The output from the model is the average number of survivors. Several events occur in the model. Suppose that the two duelists are identical to each other, so they move, turn and shoot in exactly the same moments, so all corresponding events have the same time locations for the two men. Now, consider the event "shoot-and-kill". First, suppose that this event has a finite duration (case 1: D>0). This is due to velocity of the bullet and the small time interval between being hit and die. Obviously, in this case the two duelists kill each other and the number of survivors is equal to zero. This result does not depend on D, and is valid for any D approaching zero, but different from zero.
Figure 2. A model of a duel.
Now, consider case 2, with D=0. In this case the two events "shoot-and-kill" (for the two men) are put into the event queue and scheduled for the same model time. The order of their execution (in the real time) may be random or fixed by the implementation, and it is implementation-dependent. It may also be controlled by certain DEVS selection rule. But, observe that whatever this order would be, the number of survivors is always one, because the duelist who has already been killed cannot shoot. This means that our discrete event model is invalid.
The above example shows that the discrete event model (case 2) is not the limit case of any series of models with non-discrete events, with D approaching zero. In other words, we see again that the mapping from the space of real positive numbers (values of D) into the space of results in not continuous at D=0.
Consider other example, a simple mass-service model in with clients must pass through two consecutive servers without buffers. Any client who cannot occupy a server is being lost and disappears from the model. Suppose that the clients arrive in time intervals equal to one time unit and the service time for each server is equal to one. A new client or that who leaves the first server and intents to seize the following one may not be allowed to do this, because the server is still occupied. In fact, the server will be free at the same model time instant, but the client event (seize the server) has already failed and the client has been lost. The number of lost clients depends again on the implementation, namely on the order of simultaneous event execution. The SELECT feature of the DEVS formalism solves this conflict, but it results to be a non-trivial problem.