koorio.com
海量文库 文档专家
当前位置:首页 >> IT/计算机 >>

Distributed Discrete-Event Simulation_图文

Distributed Discrete-Event Simulation
JAYADEV MISRA
Department of Computer Sciences, The University of Texas at Austin, Austin, Texas 78712

Traditional discrete-event simulations employ an inherently sequential algorithm. In practice, simulations of large systems are limited by this sequentiality, because only a modest number of events can be simulated. Distributed discrete-event simulation (carried out on a network of processors with asynchronous message-communicating capabilities) is proposed as an alternative; it may provide better performance by partitioning the simulation among the component processors. The basic distributed simulation scheme, which uses time encoding, is described. Its major shortcoming is a possibility of deadlock. Several techniques for deadlock avoidance and deadlock detection are suggested. The focus of this work is on the theory of distributed discrete-event simulation. Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems
deadlocks; 1.6.1
-

distributed applications; D.1.3

[Programming Techniques]:

Concurrent Programming; D.4.1 [Operating Systems]: Process Management?

[Simulation and Modeling]: Simulation Theory

General Terms: Algorithms, Theory, Verification Additional Key Words and Phrases: Asynchronous simulation, deadlock detection and recovery, deadlock prevention, message communicating processes, modeling interaction by message communication

INTRODUCTION

This survey presents an entirely new approach to the problem of system simu? lation. A system simulation is typically car? ried out as a repetition of the following sequential steps: Fetch one event from a data structure, carry out one step of simu? lation, and (possibly) update the data struc? ture. Such simulations are practical only when the number of events being simulated is modest. Recent advances in computer and com? munication systems have resulted in de? mands for new tools for their analyses. Mathematical modeling techniques have so far proved inadequate in dealing with these systems, and simulation seems to be the

only viable alternative. Unfortunately, sim? ulation is proving to be inadequate because of the sheer magnitude of the problem. For instance, a telephone switch generates about 100 internal messages in completing a local call. Large telephone switches can handle 100 or more calls per second. Thus, simulation of a telephone switch for 15 minutes of real time requires the simulation of nearly 10 million messages, which will require several hours on a very fast uniprocessor. One alternative is to exploit the cost benefits of cheap micro/minicomputers and high-bandwidth lines by partitioning the simulation problem and executing the parts in parallel. Unfortunately, however, the typical simulation algorithm does not easily

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. ? 1986 ACM 0360-0300/86/0300-0039 $00.75

Computing Surveys, Vol. 18, No.1, March 1986

40

?

Jayadev Misra

CONTENTS

INTRODUCTION 1. AN OVERVIEW OF SYSTEM SIMULATION 1.1 System Simulation Problem 1.2 Distributed Simulation 1.3 History 2. SEQUENTIAL SIMULATIONS OF SYSTEMS 2.1 Physical Systems 2.2 What Is Simulation? 2.3 The Sequential Simulation Algorithm 3. DISTRIBUTED SIMULATION: THE BASIC SCHEME 3.1 A Model of Asynchronous Distributed Computation 3.2 Basic Scheme for Distributed Simulation 3.3 Partial Correctness of the Basic Distributed Simulation Scheme 3.4 Features of the Basic Distributed Simulation Scheme 4. DISTRIBUTED SIMULATION: DEADLOCK RESOLUTION 4.2 Deadlock Resolution Using Null Messages 4.1 Overview of Deadlock Resolution

4.3 Correctness of the Simulation Algorithm 4.4 Discussion 4.5 Demand-Driven and Recovery 5. SUMMARY AND CONCLUSION ACKNOWLEDGMENTS REFERENCES
-

Null Message Transmission

4.6 Circulating Marker for Deadlock Detection

partition for parallel execution. An entirely new approach to simulation for multipro? cessors is required. This survey presents such an approach. The text is organized in five sections. Section 1 describes the need for distributed simulation; it gives a quick survey of the system simulation problem, the sequential simulation algorithm and its shortcomings. The scope of the paper and a history of distributed simulation are also included in that section. In order to make the paper 1. AN OVERVIEW OF SYSTEM SIMULATION self-contained, basic notions of sequential 1.1 System Simulation Problem simulation are introduced and explained in Section 2. A proof that the sequential sim? We consider the problem of simulating ulation algorithm works correctly is given physical systems, also called networks, that in that section; surprisingly, the author consist of one or more physical processes. could not find such a proof in any simula? Each physical process operates autono? tion book. It is then shown why this scheme mously, except to interact with other cannot be readily parallelized. Section 3 physical processes in the system. The introduces the basic distributed simulation interaction is by messages. Contents of a
Computing Surveys, Vol.

scheme, which is shown to be partially cor? rect. It is shown that this scheme may result in deadlock. Several different ap? proaches for deadlock resolution are dis? cussed in Section 4. Section 5 contains a summary and possible directions for future investigation. We believe that distributed simulation offers a promising approach to speeding up simulation. The basic theory has been developed; it remains to experiment with various alternative heuristics to ensure that substantial performance gains over sequen? tial simulation can be achieved. The prob? lem of deadlock and its resolution are at the core of the performance issue. There is some indication that reasonable perfor? mance gains may be expected at least for simulations of certain classes of queuing networks [Peacock et al. 1979a, 1979b; Quinlivan 1981]. However, several large? scale studies, with a number of different heuristics for deadlock resolution, are needed before any claims about perfor? mance can be made. We hope that this paper will spur interest in such studies. This paper does not introduce a new simulation language, because distributed simulations can be written using sequential simulation languages for simulating the physical processes, and message communi? cation languages for describing interactions among component machines. We also avoid a number of traditional issues in simula? tion: pseudorandom number generation, statistical analysis of the outputs, etc. Methods developed in these areas for se? quential simulation still apply [Fishman 1978] . Our goal in this paper is to show how the body of actual simulation can be distributed among a set of interacting machines.

18, No. 1, March 1986

Distributed Discrete-Event Simulation

?

41

message sent by a (physical) process de? pend on the characteristics of the process (its initial state, its rules of operation) and the messages that the process has received so far. We describe the problem and the termi? nology more precisely in the next section. We note that many real systems can be modeled in terms of processes and messages as described above. For example, in a com? puter system, CPU, disks, memory, and job entry terminals may be thought of as pro? cesses; the CPU may interact with a disk by sending it messages requesting or releas? ing disk space; a job entry terminal may interact with the CPU by sending it mes? sages, which are in fact jobs or tasks to be executed. Detailed examples are given in the next section. Typical steps in constructing and using a simulation program consists of
(1) starting with a real system and under?

lator running on asynchronous machines) from a synchronous system (the physical system, running in real time). We further restrict ourselves to discrete-event simula? tions; we assume that events in the physical system-in our case, message transmis? sions-happen at discrete points in time.
1.1. 1

Traditional Approach to System Simulation

standing its characteristics, (2) building a model from the real system in which aspects relevant to simulation are retained and irrelevant aspects are discarded, (3) constructing a simulation of the model that can be executed on a computer (simulations other than computer pro? grams are not considered here), and (4) analyzing simulation outputs to under? stand and predict the behavior of the real system. In addition, the model and the simulation must be verified and may be refined during steps (2) and (3), perhaps iteratively, if they do not meet the expectations. In this paper, we look at only one step-step (3)-of the entire simulation process. What is typically called a model in step (2) is actually our physical system; we show how to go from a physical system to a computer program for simulation that is distributed and hence may be concurrently executed on several machines. We do not consider the problem of constructing a physical system descrip? tion from the real system, nor do we con? sider how to analyze simulation outputs to predict the behavior of the real system. Stated another way, we show how to con? struct an asynchronous system (the simu-

Traditionally, discrete-event system simu? lations have been done in a sequential man? ner. A variable clock holds the time up to which the physical system has been simu? lated. A data structure, called the event list, maintains a set of messages, with their associated times of transmissions, that are scheduled for the future. Each of these mes? sages is guaranteed to be sent at the asso? ciated time in the physical system, provided the sender receives no message before this message transmission time. At each step, the message with the smallest associated future time is removed from the event list, and the transmission of the corresponding message in the physical system is simu? lated. Sending this message may, in turn, cause other messages to be sent in the future (which then are added to the event list) or cause previously scheduled mes? sages to be canceled (which are removed from the event list). The clock is advanced to the time of the message transmission that was just simulated. This form of simulation is called event driven, because events (i.e., message trans? missions) in the physical system are simu? lated chronologically and the simulation clock is advanced after simulation of an event to the time of the next event. There is another important simulation scheme, time-driven simulation, in which the clock advances by one tick in every step and all events scheduled at that time are simu? lated. We do not discuss time-driven simulation in this paper.
1.1.2

Drawbacks of Sequential Simulation

The nature of the event-list mechanism dictates a sequential simulation, since in each cycle of simulation only one item is removed from the event list, its effects
Computing Surveys, Vol.18, No.

I, March 1986

42

?

Jayadev Misra

simulated, and the event list, possibly, up? dated. This is unfortunate; the algorithm cannot be readily adapted for concurrent execution on a number of processors, since the event list cannot be effectively parti? tioned for such executions. We contend that the sequentiality inherent in the event-list structure is a major impediment to the widespread use of simulation. Com? plex computer and communication systems of the future will be intractable mathemat? ically and therefore will have to resort to simulation for their performance evalua? tions. Current simulation techniques will prove inadequate for these systems be? cause, with current technology, only a mod? est number of events can be simulated. It is necessary to take a radically new ap? proach to simulation that will utilize the power and cost benefits of small computers and high-bandwidth communication lines.
1.2 Distributed Simulation

Several distributed simulation algo? rithms have appeared in the literature. They all employ the same basic mechanism of encoding physical time as part of each message. The basic scheme they use may cause deadlock. Various distributed simu1ation algorithms differ in the way they resolve the deadlock issue.
1.3 History

Distributed simulation offers a radically different approach to simulation. Shared data objects of sequential simulation-the clock and event list-are discarded. In fact, there are no shared variables in this algo? rithm. We suggest an algorithm in which one machine may simulate a single physical process; messages in the physical system are simulated by message transmissions among the machines. The synchronous na? ture of the physical system is captured by encoding time as part of each message transmitted between machines. We show that machines may operate concurrently as long as their physical counterparts operate autonomously; they must wait for message receptions to simulate interactions of the corresponding physical processes. Distributed simulation offers many other advantages in addition to the possible speedup of the entire simulation pro? cess. It requires little additional memory compared with sequential simulation. There is little global control exercised by any machine. Simulation of a system can be adapted to the structure of the available hardware; for instance, if only a few ma? chines are available for simulation, sev? ral physical processes may be simulated (sequentially) on one machine.
Computing Surveys, Vol.

Sequential simulation has a long history; Franta provides a discussion of a number of prominent simulation languages and their relative merits [Franta 1977]. Among the many simulation packages introduced recently, we mention DEMOS, SAMOA, and MAY [Birtwistle 1979; Lonow and Unger 1982; Bagrodia et al. N.d. ] . DEMOS is a discrete-event modeling package imple? mented in SIMULA [Dahl et al. 1970]. It provides an extensive list of features for event scheduling, data collection, and re? port generation. SAMOA uses Ada as the base language [U.S. DoD 1982 ] . MAY pro? vides a very small set of constructs for message communication; these features have been used to build an extensive library for simulations of computer and commu? nication networks. The minimality of MAY makes it possible for it to be implemented even on personal computers. The idea of distributed simulation was proposed by Chandy in 1977 in a series of lectures at the University of Waterloo, and independently by R. E. Bryant. Papers by Chandy and Misra [1979], Chandy et al. [1979], and Bryant [ 1977] contain the basic ideas of distributed simulation, the problem of deadlock, and schemes for deadlock res? olution. Peacock et al. [1979a, 1979b] and Holmes [1978] have proposed mechanisms for avoiding deadlock by periodic use of probe messages. Empirical work by Peacock et al. has shown that their method is indeed viable: The time needed for simulation of a class of queuing networks steadily de? creases when the number of processors available for simulation increases. Empiri? cal investigations by Seethalakshmi and Quinlivan showed that the method is also efficient for acyclic physical systems and that performance can be substantially improved if there is adequate space for

18, No.1, March 1986

Distributed Discrete-Event Simulation

?

43

buffering messages [Seethalakshmi 1979; Quinlivan 1981] . Chandy and Misra have subsequently suggested a scheme for deadlock detection and recovery [Chandy and Misra 1981] . Reynolds suggested using common memory among neighbors to avoid deadlock [Rey? nolds 1982] . A notable departure from these schemes is one proposed by Jefferson based on virtual time [Jefferson 1985]. A perform? ance analysis of this scheme appears in Lavenberg et al. [1983]. The virtual time approach is still being developed and it is a little premature to include it in this survey. Bezivin and Imbert propose an approach in which each process in the simulator maintains a local time, and an overall global time is maintained by a central pro? cess [Bezivin and Imbert 1983] . Christo? pher et al. propose precomputing minimum wait time along all paths in a network so that delay information may be propagated rapidly among nonneighboring processes [Christopher et al. 1983]. Kumar has combined some recent work in deadlock and termination detection with the basic simulation scheme [Kumar 1986; Misra 1983 ] . Behaviors of these algorithms on a wide class of practical simulation problems are currently being investigated, both analytically and using empirical tech? niques.
2. SEQUENTIAL SIMULATIONS OF SYSTEMS

tional simulation terminology, each pp is described by a set of events and each event has an associated time of occurrence. Fur? thermore, there is a dependency relation among all events in the system; if the pair of events (e, e ') is part of the dependency relation, we say that e' depends on e. De? pendency relation captures our intuitive understanding of the order in which events must occur in the system; no event can occur unless all the events on which it depends have already occurred. Clearly, we must then require that the dependency re? lation not be cyclic, that is, it should be an irrefIexive partial order; furthermore, the time associated with an event e' must be no less than the associated time of any event e on which it depends. We next give an example that clarifies the notion of events and dependencies.
Example 2. 1 (Car Wash)

This section introduces the problem of sys? tem simulation. A precise definition of sim? ulation is given. The sequential simulation algorithm using the event-list structure is presented and proved. It is shown why the sequential simulation scheme cannot be readily adapted for parallel execution.
2.1 Physical Systems

We consider physical systems, also called
networks, consisting of a finite number of physical processes (abbreviated as pp's).

The following example is a variation of one appearing in Birtwistle et al. [1973]. A car wash system consists of an attendant and two car washes, abbreviated CW1 and CW2. Cars arrive at random times at the attendant. The attendant directs cars to CW1 or CW2 according to the following rule: If both car washes are busy, that is, washing cars, any arriving car is queued at the attendant; if exactly one car wash is idle, the car at the head of the queue, if any, is sent to that idle car wash; if both car washes are idle, the car at the head of the queue, if any, is sent to CWI. CW1 spends 8 minutes and CW2, 10 minutes in washing a car. Given some distribution of car arrivals, it is necessary to compute the average amount of time a car spends at the car wash (including the washing time) and the average length of the queue that builds up at the attendant. We do not compute the above statistics; we simply show the sequence of events and message transmis? sions in two different views of the car wash problem. The entire system can be described by listing all possible events-all possible car arrivals and their subsequent washings? and dependencies between them. We re? strict ourselves to describing part of this system.
Computing Surveys, Vol. 18, No. 1, March 1986

Each pp represents some component of the real system to be simulated. For instance, in a computer system, the CPU, each disk, each memory bank, and each job entry ter? minal may be thought of as a pp. In tradi-

44

?

Jayadev Misra

cars enter car wash

cars leave car wash

Figure 1.

Schematics of car flow.
Table 1.

The schematic diagram of the flow of cars is given in Figure 1 . Initially both CWI and CW2 are idle. Assume that 6 cars, Cl through C6, arrive at the attendant at times 3, 8, 9, 14, 16, 22. An event in this system is either a car arriving at some point, that is, at the at? tendant, CWl, or CW2, or a car leaving the car wash. We assume that the driving time from the attendant to CWI or CW2 is zero. Also, the washing of a car begins as soon as it arrives at CWI or CW2. The chrono? logical sequence of events is given in Table 1. Dependencies among events is shown in the directed graph of Figure 2; a directed line from event ej to event e2 denotes that event e2 depends directly on event ej. If an event e' depends on event e, then simulation of e must precede simulation of e'. Conversely, if e, e' are independent, that is, there is no dependency relation between them, then they may be simulated concurrently or, equivalently, in arbitrary order. Thus, two independent events, such as event 8 (C4 arrives at the attendant) and event 12 (C3 leaves car wash) are inde? pendent and hence can be simulated con? currently. We find it convenient to dispense with the notion of event; we model a physical system as a set of pp's that operate auton? omously to change their own states and that interact by sending and receiving mes? sages. Such a model is possible because if event e' at process q depends on event e at process p, then process p may send a mes? sage to process q after it completes execu? tion corresponding to event e, and q, upon receiving this message (and other messages corresponding to other dependencies of e') may carry out the actions necessary for
Computing Surveys, Vol. 18, No. I, March 1986

A Sequence of Events in the Car Wash

Event number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Time 3 3 8 8 9 11 11 14 16 18 18 19 19 22 27 27 28 35

Event Cl arrives at the attendant Cl arrives at CWI C2 arrives at the attendant C2 arrives at CW2 C3 arrives at the attendant Cl leaves car wash C3 arrives at CWI C4 arrives at the attendant C5 arrives at the attendant C2 leaves car wash C4 arrives at CW2 C3 leaves car wash C5 arrives at CWI C6 arrives at the attendant C5 leaves car wash C6 arrives at CWI C4 leaves car wash C6 leaves car wash

implementation of e'. Message transmis? sion delays are zero, that is, any message sent at time t is received by the intended recipient at t. (Recall that we are describing a physical system, not the computer system on which the simulation is to run.) If it is necessary to model delays in the real-world system (viz., driving time from attendant to a car wash in the last example), then either the sender of a message idles for some time before sending the message or the recipient of a message idles for some time after receiving the message; another possibility is to model the communication medium as a process incorporating the delay.
Example 2.1 (continued)

We now present the car wash viewed as a message-passing system. The car wash sys? tem has 5 pp's: the source, which generates

Distributed Discrete-Event Simulation
Figure 2.

?

45

Schematics of events in a car wash.

attendant

source

Figure 3.

Schematics of message flow in the car wash system.

cars at the prescribed times, the attendant, CWI, CW2, and the sink (exit). The sche? matic diagram of message communications among these pp's is given in Figure 3. Note that we have possible message flow paths from CWI and CW2 to the attend? ant. This is because the attendant must know when a car wash becomes idle. (In this particular problem, the attendant can keep track of the times at which the last cars were sent to CWI and CW2 and, since the washing times are fixed, can deduce the times at which CWI and CW2 will next become idle. This means that the attendant is simulating CWI and CW2. In general it will not be possible, or preferable, to do so in a simulation.) A complete list of mes? sages for this example is shown in Table 2, with corresponding event numbers from Table 1. Each message has a sender, a receiver, and message content. In our case the content is either a car number or the status (idle) of a car wash. This example shows how to model event interactions by message transmissions. In particular, if an event at one pp causes events to happen at several other pp's, we shall have to model such event dependen? cies by several message transmissions. Sec? ond, the chronological order of simulations

of events in sequential simulation (de? scribed later) guarantees that every event simulation precedes the simulation of events that depend upon it. Our approach in distributed simulation dispenses with chronological simulations of events. There are two conditions that are met by every physical system imaginable: realiza? bility and predictability. We assume that both these conditions hold for all physical systems we consider.
Realizability. A message sent by a pp at time t is a function of its initial state, t, and the messages it has received up to and including t.

Realizability says merely that a pp can? not guess any message it will receive in the future. Note that we admit the possibility of a message that is received at t affecting a message that is sent at t. An example of a pp in which this instantaneous cause? effect is seen is given below.
Example 2.2 (Instantaneous Message Transmission)

Consider a pp that acts as a merge point for several pp's. Schematically, such a pp, A, is shown in Figure 4. Messages arriving at A, either from the top or from the
Computing Surveys, Vol. 18, No.1, March 1986

46

?

Jayadev Misra
Table 2.

A Sequence of Message Transmissions in the Car Wash System

Message number
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Event number

Time message sent 0 0 3 3 8 8 9 11 11 11 14 16 18 18 18 19 19 19 22 27 27 27 28 28 35 35

Message sender CWI CW2 Source Attendant Source Attendant Source CWI CWI Attendant Source Source CW2 CW2 Attendant CWI CWI Attendant Source CWI CWI Attendant CW2 CW2 CWI CWI

Message receiver Attendant Attendant Attendant CWI Attendant CW2 Attendant Sink Attendant CWI Attendant Attendant Sink Attendant CW2 Sink Attendant CWI Attendant Sink Attendant CWI Sink Attendant Sink Attendant

Content Idle Idle Cl Cl C2 C2 C3 Cl Idle C3 C4 C5 C2 Idle C4 C3 Idle C5 C6 C5 Idle C6 C4 Idle C6 Idle

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

A.

I--JlIIII]
Queue
A merge point pp.

Figure 4.

bottom, are instantaneously sent to the queue on the right. Therefore, a message sent by A at t depends upon messages re? ceived at t. It may be argued that pp A cannot be physically constructed. However, this pp may represent a real-world entity, where the interval between reception and transmission of a message is small enough to be ignored altogether in the modeling process. Such merge points are often used in queuing network descriptions of systems.
Computing Surveys, Vol.18, No. 1, March 1986

such that the messages sent by the pp along the cycle can be determined up to t + ?, given the set of messages that the pp receives up to and including t.

Predictability. Suppose the physical system has cycles, that is, a set of processes PPo, ... , PPn-l, where PPi sends messages to PPi+l (and perhaps to other pp's) and receives messages from PPi-l (and perhaps other pp'S).1 Suppose that the message, if any, sent by PPi at some time t depends on what PPi receives at t, for all i; then we have a circular definition where the mes? sage received by every PP at t is a function of itself. In order to avoid such situations, we require that for every cycle and t there is a pp in the cycle and a real number ?,f > 0,

Predictability guarantees that the system is "well defined" in the sense that the out? put of every PP up to any time t can be computed given the initial state of the system.
1

All arithmetic in pp subscripts is modulo

n.

Distributed Discrete-Event Simulation

?

47

[>-t'1 I 1 I 1 I
source

A

·

B

·

c

Figure 5. sink

Schematic diagram of the example assembly line.

Table 3.

Job Generation Times and Service Times in the Example of Figure 5

Jobs Work station Job generation times Source Service times
B
A

2 5 12 2
4 7

3 30 1 2
1

4

32 5
7 4

C

10 15 3

We next consider some typical simula? tion examples and show that they satisfy the realizability and predictability condi? tions.
Example 2.3 (Car Wash-Realizability and Predictability)

We consider the car wash problem intro? duced in Example 2.1. Each pp's output at time t depends only upon the messages it has received up to t. Of particular interest is the behavior of the attendant. If it re? ceives an "idle" message from either of the car washes at time t and the queue is not empty at t, then it sends a message at t. Therefore, the realizability condition is satisfied. The predictability condition is satisfied because each cycle contains one of CW1 or CW2 and, given the input to CW1 (CW2) up to t, we can predict the output from it up to t + 8 (t + 10).
Example 2.4 (Assembly Line)

queue when it is free, services that job, and then sends it to the queue of the following work station. All work stations service the jobs in a first come, first served (FCFS) basis. It is desired to find the expected number of jobs in the queue of each work station and the expected waiting time for jobs at each work station. Specifically, consider an assembly line consisting of three work stations, A, B, and C, which services four jobs identified as 1 , 2 , 3, and 4 . Schematically, the assembly line is shown in Figure 5. The times at which the source generates jobs and the service time of each work station for each job are given in Table 3. The source (call it work station 0), the sink (call it work station 4), and each work station are pp's. PPi sends messages to PPi+! , i = 0, 1, 2, 3. The source sends messages (which represent jobs) to work station 1 at times 5, 7, 30, and 32. If a job j, j > 1, arrives at a work station at time t, then its service at this work station begins either immediately (at t) if the work station is then idle, or it begins immediately after the departure of the (j - l)th job from the work station. Let Aj be the time of arrival of job j at some work station, let D j be the time of departure of job j from this work station, and let S j be the service time for job j at this work station. Then we have
Do=O;

j= 1, 2, . . . . Using the service times and generation times of jobs given in the previous table, we can construct the departure times from work stations, that is, times at which mes? sages are sent, as in Table 4. Each work station's output at time t de? pends only on the jobs it has received up to t, and therefore the realizability condition is satisfied. The predictability condition is trivially satisfied since there is no cycle in the physical system.
Computing Surveys, Vol. 18, No. 1, March 1986

An assembly line consists of a series of n work stations. Jobs enter the assembly line at work station 1; when a job has been serviced at work station i, it proceeds to work station (i + 1), i = 1, 2, . . . , n - 1; a job leaves the system after being serviced at work station n .Service times at different work stations are random variables; jobs may be queued at a station awaiting service. A work station takes one job from its input

48

?

Jayadev Misra
Times at Which pp's Send Messages in the Example of Figure 5

Table 4.

rectly simulates a physical system if it is
possible for the logical system to predict the

pp Source
A

1
5 9 21 23

Message
2 7 19 36 39 3 30 31 38 40 4 32 37 45 49

B C

Example 2.5 (A Computer System)

Imagine a computer installation that con? sists of a central processing unit (CPU) and two peripheral processors, proc1 and proc2. Jobs enter the CPU, spend some time there, and then branch to one of the peripheral processors with some given probability. Upon completion of processing at the peripheral processor, a job may leave the system or return to the CPU with some probability. The schematic diagram of the system is shown Figure 6. This system has pp's for the source, the sink, merge points Ml and M2, branch points Bl and B2, the CPU, proc1, and proc2. Each message represents the trans? fer of a job from one pp to another. The realizability property holds because no pp bases its behavior on anticipation of the future. Probabilistic decisions at Bb B2 cause no difficulty because the inputs to BI, B2 up to time t determine their outputs up to time t (though the outputs may be different at different times owing to the probabilistic nature). We can realistically assume that each processor spends nonzero time in processing a job. Therefore the sys? tem also has the predictability property. This concludes our discussion of using physical systems to model real-world sys? tems. From now on we assume that we are dealing with physical systems with the properties of realizability and predictabil? ity. Now we define the meaning of simula? tion for such physical systems.
2.2 What Is Simulation?

exact sequence of message transmissions in the physical system. That is, if t1, t2, , ti, are the times at which the messages ml, m2, ... , mi . . . are transmitted in the physical system and tl ::; t2 . . . ::; ti ::; . . . , then the logical system should be able to output the sequence ?tl, mi), (t2, m2), ... , (ti, mi), ... ). The logical system may not actually print the sequence ( ... (ti, mi) . . . ) . All that is desired is that it should be possible to do so from the logical system. Clearly a physical system is a simulation of itself. We wish to construct logical sys? tems that may not operate at the same speed as the physical system. Our goal is to construct a logical system out of a machine or machines where the speeds of processors and communication links (if any) are arbitrary. In other words, we wish to duplicate the behavior of a synchronous physical system using asynchronous logical components. It should be observed that we can carry out the typical functions of simulation? analyze data, predict performance or future behavior, generate reports, etc. -using the logical system. We do not address these issues in this paper; we merely observe that since it is possible to create the sequence of physical message transmissions in the logical system, all interactions can be re? constructed and analyzed.
? ? ? ? ? ?

Example 2.6 (Message Transmission in the Assembly Line Example)

A simulation of the assembly line of Example 2.4 should be able to predict the following message sequence. This sequence is derived from Table 4. In the following, a message consists of (sender id, receiver id, message content). We write a 4-tuple (t, s, r, m) to denote that at time t, pp s sends a message to pp r with content m. ?5, source, A, 1), (7, source, A, 2), (9, A, B, 1) (19, A, B, 2), (21 B, C, 1), (23, C, sink, 1 ) , (30, source, A, 3), (31, A, B, 3), (32, source, A, 4), (36, B, C, 2), (37, A, B, 4), (38, B, C, 3), (39, C, sink, 2), (40, C, sink, 3), (45, B, C, 4), (49, C, sink, 4?

We wish to build a simulator, or a logical system consisting of logical processes (ab? breviated lp) , to simulate a physical system. We use "simulation" in a rather strict sense: We say that a logical system corComputing Surveys, Vol. 18, No.1, March 1986

Distributed Discrete-Event Simulation

?

49

Figure 6.

Schematic diagram of job flow in a computer system that has a CPU and two peripheral processors: a, mean time between arrival of jobs from the outside source a r? ndom variable ; teo mean time spent by a job at the CPU, a random variable; t" m an . time spent by a Job at the peripheral processor 1 (procl), a random variable' t2 mean time ?pent y a job at the peripheral processor 2 (proc2), a random variable; Ci, ro ability of a Job gomg ?o proc1; {3, probability of a job exiting the system; M" M2, merge points; B" B2, branch pomts.

?

?

? b

2.3 The Sequential Simulation Algorithm

Two major data objects used by the sequen? tial simulation algorithm are the clock and event list, which are described as follows:
Clock. A real-valued variable. It gives the time up to which the corresponding physi? cal system has been simulated; that is, all messages (t, m) sent in the physical system with t < clock, can be deduced from the logical system at any point in its execution. Event list. A set of tuples of the form (ti, mi), where ti ? clock and mi is a message. (We assume that the identities of the sender and the receiver are parts of the message.) A tuple (ti, mi) is in the event list means that, in the physical system, if the sender of mi receives no message at any t, clock ::: t < ti, then it sends mi at ti and sends no other message at any time t, clock::: t ::: ti.

sponding entries in the event list are shown as follows: 9 clock: event list 1/(19, A, B, 2), (21, B, C, 1 ) , ( 00, C, sink, -), (30, source, A, 3)1 This snapshot of the simulation corre? sponds to the point in the physical system where the source has produced jobs 1 and 2, and job 1 has been processed at A and sent to B. The source has one more job scheduled for production; A has scheduled to send job 2 to B at time 19, provided A receives no more jobs between 9 and 19; B has scheduled to send job 1 to C at time 21, provided it receives no more jobs before then; C has scheduled no message because it has received no jobs. It should be noted that each entry (t, m) the event list is conditional. An entry (t, m) may not actually occur in the physi? cal system, because this message transmis? sion may be canceled if the sender of m receives a message prior to t. In fact, it is impossible to construct general-purpose sequential simulations without canceling events from the event list. For example, cancellation is required in the simulation of a system with preemption: Scheduled departure of a job from a server for some future time may have to be canceled (and recomputed) owing to the arrival at the server of a job that preempts the previous job.
III

It is required that for every PPi there be at least one event-list entry (ti, m;) in which PPi is the sender. If a pp sends no message in the future, unless it receives further mes? sages, the corresponding event-list entry will be ( 00, m), where the message content in m is arbitrary. A similar entry, ( 00, m), will always be in the event list for a pp that has terminated.
Example 2.7 (A Snapshot in Sequential Simulation of the Assembly Line)

.

In simulating the assembly line of Example 2.4, a possible value of clock and corre-

Computing Surveys, Vol. 18, No. 1, March 1986

50

?

Jayadev Misra

sequentially in arbitrary order, a possible simulation may result in pp B sending m' to pp A . This example illustrates that guarantee that the first message to be sent events should be simulated in the order of at or after the current value of clock is mes? their dependencies (m' is dependent on m sage m and that it is sent at time t. This is in this example). Simulation in the order the content of the following theorem, upon of dependencies also guarantees chronolog? which sequential simulation is based. ical order. Certain sequential simulation languages, such as GPSS [Franta 1977], provide the user with facilities for defining Theorem 1 orderings among simultaneous events. In Let (t, m) be an entry in the event list such this case, information defining orderings that t < t' for every other entry (t', m') in must be kept with tuples in the event list. the event list. Then the message m is trans? Distributed simulation is based on the mitted at time t in the physical system and dependency order and hence avoids this no other message is transmitted at til, where problem. clock :S til < t. A tuple (t, m) in the event list is a small? Proof. If message m is not transmitted est tuple if t :S t' for every (t', m') in the at t, it must be because some other message event list, and, if t = t', then message m' is transmitted at or before t (and at or after does not precede m Ithis has to be deduced clock), which causes the sender of m to from additional facts stored with m' and cancel transmission of m. Consider the first mI. Note that there may be several smallest message m' to be so transmitted; it must tuples and they may be simulated in arbi? be transmitted at t' where clock :S t' :S t. trary order. The simulation algorithm, given below, The sender of m' could not have received works as follows. In each step a smallest any message between clock and t', because such a message would be the first message tuple is removed from the event list, its transmitted after clock. Then (t', m') must effects are simulated (causing possible ad? be an entry in the event list, because the ditions to and deletions from the event list), sender of m' sends its message without and the clock is advanced to the time as? receiving any other message after the cur? sociated with this message transmission. rent clock value and before t'. Since t' :S t, This algorithm is given in a pseudopro? it contradicts our choice of (t, m). Hence gramming notation below. the result. 0
2.3.1

Let (t, m) be an entry in the event list where t is smaller than t' for every other (t', m') in the event list. We can then

Simulations of Simultaneous Events

2.3.2

The Sequential Simulation Algorithm (See Figure 7)

We assumed in Theorem 1 that there is a unique tuple (t, m) in the event list, where t is smaller than t', for all other (t', m'). In a sequential simulation, two message transmissions that happen simultaneously in the physical system, that is, at the same time t, must be simulated in some order. Simulating them in arbitrary order can lead to problems, as in the following: pp A plans to send a message m to pp B at time t; pp B is an alarm clock that is scheduled to go off, that is, to send a message m' to pp A at time t, unless it receives a message from pp A before or at t. In the physical system, pp B will not send m' to pp A. However, if these message transmissions are simulated
Computing Surveys, Vol.18, No. 1, March 1986

The correctness of this algorithm should be obvious from our previous discussions. Note that the sequential simulation algo? rithm is capable of producing the sequence of message transmissions in the physical system; it simply prints (t, m), whenever it removes (t, m) from the event list.
Example 2.8 (A Sequence of Snapshots in the Simulation of the Assembly Une)

We consider the assembly line example and show in Table 5 a partial sequence of event lists and clock values.

Distributed Discrete-Event Simulation
Initialize:: clock := 0; event list := I(ti, mJ I message mi will be sent at ti unless the sender of mi re? ceives a message before ti; one such entry exists for each pp as the senderj. Iterate:: while termination criterion is not met do remove a smallest tuple (t, m) from the event list; simulate the effect of transmitting m at time t; IThis may cause changes in the event list. Note however that any addition or deletion, (t', m ') to the event list will have t' ? t.1 clock := t endwhile
Figure 7.

?

51

simulation may be carried out by a set of communicating processes. We limit our dis? cussion here to a basic scheme, one which can result in deadlock. More sophisticated schemes that resolve deadlock are discussed in the next section.
3. 1 A Model of Asynchronous Distributed Computation

The sequential simulation algorithm.

Table 5.

Partial Sequence of Event Lists and Clock Values

Clock 0

Event list ?5, source, A, 1), (00, A, -, ), ( 00, B, -, ), ( 00, C, -, ) ?7, source, A, 2), (9, A, B, 1), ( 00, B, -, ), ( 00, C, , ) ?30, source, A, 3), (9, A, B, 1), ( 00, B, -, ), (00, C, -, ) ?30, source, A, 3) (19, A, B, 2), (21, B, C, 1), ( 00, C, , )
-

Smallest tuple (5, source, A, 1)

5

(7, source, A, 2)

7

(9, A , B, 1)

9

(19, A, B, 2)

Notes on Parallel Execution. It should be obvious that to process more than one tuple at once, say, both (t, m) and (t', m'), we must be sure that these two events are independent, that is, that execution of one will not in any way affect the execution of the other. This requires us to know more about the cause-effect relationship among messages. We consider these issues in the next section and develop a basic scheme for distributed simulation.
3. DISTRIBUTED SIMULATION: THE BASIC SCHEME

A distributed system consists of a finite number of processes and directed channels connecting some pairs of processes. To dis? tinguish these processes from physical processes, we call them logical processes or lp's. Each lp may execute sequential code and two special commands: receive and send. In a send, an lp names an outgoing channel and a message that is to be sent along that channel. Execution of the send results in the message being deposited on the named outgoing channel; the sender then proceeds with the execution of its code. Each message takes an arbitrary but finite time to reach its destination. Mes? sages sent along a channel are delivered in the sequence in which they are sent. In a receive command, an lp names one or more incoming channels from any one of which it wishes to receive a message. An lp wish? ing to receive may have to wait until a message arrives along one of the incoming channels. Note that our communication protocol is extremely simple and can be implemented on many existing machine architectures. A set of lp's D is deadlocked at some point in the computation if all of the follow? ing conditions hold: (1) every lp in D is either waiting to receive or is terminated; (2) at least one lp in D is waiting to receive; (3) for any lpi in D that is waiting to receive from some lpj, lpj is also in D, and there is no message in transit from lpj to lpi. It follows then that none of the lp's in D will carry out any further computation since they will remain waiting for each other.
3.2 Basic Scheme for Distributed Simulation

In this section we introduce a model of distributed computation and show how a

To simulate any given physical system, we construct a distributed logical system as follows. We will associate one lp with each
Computing Surveys, Vol.18, No.1, March 1986

52

?

Jayadev Misra

pp; lpi will simulate the actions of PPi . If PPi can send messages to PPh there is a channel from lpi to lpj. An lp can simulate the actions of a pp up to time t if the lp knows the initial state and all messages that the corresponding pp receives up to time t. This is because, from the realizability property, no future message (message received by the pp after time t) can affect the pp's behavior at t. We note further that an lp may be able to simulate a pp beyond time t, even though it knows its input messages only up to time t, as shown in the following example.
Example 3.1 (An Ip May Predict the Future)

minj Itjl. where t/ s are the channel clock values of all incoming channels to that lp, and the minimum is taken over all these incoming channels. We call Ti the clock value of lpi. Hence, lpi can safely simulate PPi up to Ti; that is, it can deduce every message that PPi sends up to time Ti? Also, lpi may be able to deduce pp/s message transmissions beyond Ti? In any case, lpi will send messages corresponding to all the messages it can deduce for PPi. The basic simulation algorithm followed by lpi is sketched next; we assume that all messages are sent at t > ° in the physical system.
3.2.1

Consider a typical nonpreemptive first come, first served (FCFS) server, which spends exactly 10 units of time servicing each job. Assume that a job arrives at time t when this server is idle. From this infor? mation about input messages up to time t, we can predict the behavior of the server up to time t + 10: It will produce no output between times t and t + 10, but it will output a message at t + 10, sending the job that has been serviced to its next destination. From these observations, we can con? struct an algorithm for distributed simula? tion. We note that the times at which pp's send messages must be encoded into the message that the lp's send: If messsage m is sent by PPi to PPj at time t, message (t, m) will be sent by lPi to lpj at some point during We make a chronology requirement: If an lp sends a sequence of messages ( . . . (ti, m;), (t i+1o mi+l ) . . . ) to another lp, then t i < ti+l . . . . The implication of this requirement is that if lpi receives (t, m) from lpj, then it knows all messages that PPi receives from PPj up to and including time t, because any future message will have a higher t component. Define the channel clock value of a chan? nel to be the t component of the last message received along that channel; the channel clock value is ° if no message has been received along that channel. Clearly, every lpi knows all messages received by the corresponding PPi up to time Ti =
Computing Surveys. Vol.18, No. I, March 1986

Basic Distributed Simulation Algorithm for 'Pi (See Figure 8)
'

Note. The lp's that have no incoming channels are called source lp s. Each source lp also follows this algorithm: It simply sends messages until the simulation com? pletion criterion is met. A sink lp simply receives messages and otherwise does not affect the simulation.
Example 3.2 (Distributed Simulation of the Assembly Line)

Let us review the assembly line example (Example 2.4 ). In the following, we have one lp each for the source, the sink, work station A, work station B, and work station C. See Table 3 for the job generation and processing times. Figure 9 shows the messages sent by each lp; an arrow from (t, m) to (t', m') means that sending of (t, m) precedes sending of
(t', m').

simulation.

Note in this example that the source can send its messages to A without waiting for any input; A can send the ith message to B only after receiving the i th message from the source, etc. Two messages on different lp's between which there is no sequence of arrows are independent and hence may be transmitted simultaneously in the simulator. For instance, (32, Source, A, 4), (31, A, B, 3), (36, B, C, 2), (23, C, Sink, 1) can possibly be transmitted simultane? ously. The five lp's form a pipeline through which each job passes. If the speeds of the

Initialize:: Ti := ° IAli messages received by PPi up to Ti, are now known to lp,j while simulation completion criterion is not met do Isimulate PPi up to Ti by doing the following!:: for each outgoing channel, compute the sequence of messages ?t" m,l, (t2, m2) ... (tn m,?, where t, < t2 . . . < t, and, PPi sends mj at time tj along this channel; send each message in sequence along the appropriate channel; INote: All messages sent by PPi up to Ti can be deduced by lpi and sent; also some messages to be sent beyond Ti may be predicted by lpi and sent. Only new messages that have not been sent before are sent. Also note that some or all of these message sequences may be empty.! Ireceive messages and update Ti until Ti changes value!:: Tf:= Ti; while T[ = Ti do wait to receive messages along all incoming channels; upon receipt of a message, update lpis internal state and recompute Ti, the minimum over all incoming channel clock values endwhile endwhile
Figure 8.

Distributed Discrete-Event Simulation

?

53

Basic distribution algorithm for lpi.

Source:
A: B: C:

(5, Source, A, 1) (9, A, B, 1)

-->

(7, Source, A, 2) (19, A, B, 2)

--> --> --> -->

(30, Source, A, 3) (31, A, B, 3) (38, B, C, 3) (40, C, Sink, 3)

-->

(32, Source, A, 4) (37, A, B, 4) (45, B, C, 4) (49, C, Sink, 4)

! !

(21, B, c, 1) (23, C, Sink, 1)

-->

! !

! !

-->

!

(36, B, c, 2)

-->

! !

-->

-->

Figure 9.

(39, C, Sink, 2)

!

!

-->

!

Messages sent by each lp.

lp's are approximately equal, and the trans? mission delays between lp's are approxi? mately equal, then the pipeline should work at full efficiency; one job is input and one job is output per cycle after an initial delay of three cycles. This is about the simplest simulation example one can think of. We study a harder example next.

Example 3.3 (A Primitive Computer system) (See Figure 10)

We have one lp each for the source, the CPU, Proc1, Proc 2, M, B and the sink. For this example, assume that jobs arrive at the CPU from the source every 5 time units starting at time 3, that jobs spend 1 unit at the CPU, that jobs alternately go to Proc1 and Proc2 from B, and that a job spends 5 units at Proc1, 18 units at Proc2, and no time at B or M. We show the sequence of messages and their dependencies in Fig? ure 11. (To simplify the diagram, we have

not shown the arrows between messages at a pp.) Note the behavior of the lp correspond? ing to M. Assume that it first receives (27, Proc2, M, 2) from the lp corresponding to Proc2. This is possible if, for instance, the lp corresponding to Proc2 were consid? erably faster than the one corresponding to Proc1. Then the lp for M can only infer that it will not receive any other message from the lp corresponding to Proc2 with time component smaller than 27. However, it cannot assert anything about messages from Proc1; it can thus simulate pp M only up to time o. Suppose that it next receives (45, Proc2, M, 4); it must still wait. The next input is, say (9, Proc, M, 1). Then the lp corresponding to M can assert that it knows all inputs that M receives up to time 9 and hence predict all of M 's outputs at least up to 9; therefore, it can output (9, M, Sink, 1), since jobs spend no time at M. The rest of the outputs of M are easy to see. Finally, note that M cannot output
Computing Surveys, Vol. 18, No.1, March 1986

54

?

Jayadev Misra

? M-""III
sink Figure 10.

A primitive computer system.

Source: (3, Source, CPU, 1) (8, Source, CPU, 2) (13, Source, CPU, 3) (18, Source, CPU, 4) (23, Source, CPU, 5) CPU: (4, CPU, B, I )

i

(9, CPU, B, 2)

J.

(14, CPU, B, 3)

J.

(19, CPU, B, 4)

i

!
B: ( 4 , B , Procl , I) P?l, (9, p

1
(9, B , Proc2, 2) l

!

P?2'

E

J

2' M' 2)

'0p

?l' M'

?

( 1 4 , B , ProcI , 3 )

( 19, B, Proc2, 4 )

!

(24, CPU, B, 5)

J.

!

(24, B , Procl, 5 )

P?l' M' 5)

(", Pw" , M, ')

M:

(9, M, Sink, I )
Figure 1 1 .

(27, M, Sink, 2 )

(29, M, Sink, 5)

Sequence of messages and their dependencies.

(45, M, Sink, 4) at the very end, because it does not know whether it will receive a message with a t component lower than 45 from the lp corresponding to Proc1. An extra message with a t component exceed? ing 45 must be sent from Proc1 to M to "flush out" this message. We discuss this issue later.
3.3 P artial Correctness of the Basic Distributed Simulation Scheme

Correctness of a distributed simulation algorithm consists of two parts: (1) If a message m is transmitted in the physi? cal system at time t, then (t, m) is trans? mitted in the simulator; (2) if (t, m) is transmitted in the simulator, then message m was transmitted at time t in the physical system. These statements are not quite true for the basic distributed simulation scheme just presented. As we observed in the last example, job 4 is sent at time 45 from M to the sink in the physical system, but the corresponding message is never sent in the simulator. Therefore, we can prove only one
Computing Surveys, Vol. 18, No.1, March 1986

part of the correctness condition stated above: Whatever is transmitted in the sim? ulator actually happens in the physical sys? tem. We are postponing discussion of the converse statement-if message m is trans? mitted at time t in the physical system, then (t, m) is transmitted in the simula? tor-to the next section. Define a simulation to be correct at some point if it meets the following two condi? tions: ( 1 ) If message m is sent at time t along channel e in the physical system, and t is less than or equal to the channel clock value of channel e at this point in simula? tion, then (t, m) has been sent along chan? nel e in the simulation; (2) if (t, m) has been sent in the simulation, then message m is sent at time t in the physical system. We note that, in a simulation that is correct at some point, every lp must have received a correct input sequence along every incoming channel, that is, every message on this channel that has been transmitted in the physical system up to this channel clock value has been received along this channel in the simulation, and

Distributed Discrete-Event Simulation

?

vice versa. We assume that every lp cor? rectly simulates the corresponding pp; that is, any message sent by an lp is correct
provided that all messages it has received prior to sending this message are correct.

Example 3.4 (A Deadlocked Subsystem in a Distributed Simulation)

55

Clearly a simulation is correct if and only if every lp has sent correct output sequences along every outgoing channel. Theorem 2 follows by applying induction on the number of messages transmitted in the simulation.
Theorem 2

Simulation is correct at every point. Proof. Simulation is obviously correct, by definition, when no message has been transmitted in the simulation. Assume that a simulation is correct up to some point. The next messsage in the simulation is sent by some lpi. Since simulation is correct prior to this message transmission, lpi has received correct input sequences so far. From our assumption that lpi correctly sim? ulates PPi, the output sequences of lpi, in? cluding the last message sent, are correct. Every other lp has sent correct sequences so far, from the inductive hypothesis. Hence the simulation is correct following the last message transmission. D

Consider a physical system in which the source sends messages to a branch point B, and B routes the messages to Proc1 or Proc2. After some finite time, each message is sent from Proc1 or Proc2 to a merge point M, after which it enters a network N (see Figure 12). Consider the case in which B sends every message to Proc1. Then in the simulation, the lp corresponding to M will never receive a message from Proc2. Hence the channel clock value for the chan? nel (Proc2, M ) will remain at ° and the lp for M will never send a message. The sub? system N will thus never receive a message. We show another example in which dead? lock arises owing to a circular pattern of waiting among the lp's.
Example 3. 5 (Cyclic Waiting in a Distributed Simulation) (See Figure 13)

In a similar manner, we can derive the following result.
Theorem 3

All messages sent by one lp to another are chronological in their time components.
3.4 Features of the Basic Distributed 3.4. 1 Simulation Scheme

The Problem of Deadlock

Theorem 2 tells us only that whatever is transmitted in the simulator corresponds to a message in the physical system. As we have noted earlier, not all messages in the physical system are transmitted in the sim? ulator using the basic simulation scheme. In fact, the next example shows a system in which no message is transmitted to a subsystem in the simulator.

Consider a network of three processes and a source, shown schematically in Figure 13. The number on each channel is the channel clock value; that is, the last message sent from x to y and received by y had a t component of 20, and so on. Suppose that none of x, y, z will now send a message unless they receive a message, that is, they can predict no future messages. We can see that z will not send a message unless x first sends a message to y. Hence x need not wait for z; it can process the next message from the source. However, none of the lp's corresponding to x, y, z have this global knowledge; they only have local knowledge of the behavior of each individual pp. Therefore, x cannot proceed unless it receives from z, z cannot proceed unless it receives from y, and y cannot proceed unless it receives from x, leading to a deadlock.
3.4. 2

Simulation Snapshot

In a sequential simulation, it is possible to assert that the simulator has completed simulation up to the time given by the clock: every pp must have been simulated up to this point in time. We cannot make
Computing Surveys, Vol.18, No.1 , March 1986

56

?

Jayadev Misra

sou rce

B

Figure 12.

A distributed simulation that does not progress.
20

Figure 13.

15

A distributed simulation that deadlocks.

a similar statement for distributed simula? tion, because each lp may have simulated the corresponding pp to a different point in time. For instance, in the example of the primitive computer system (Example 3.3), we can assert at the end that the lp's have simulated the corresponding pp's as follows: (Source: 23)(CPU: 24), (B: 24), (Proc1: 29), (Proc2: 45), (M : 29). Let T, the clock value of the simulator, be the minimum of all ip clock values. We can assert that at any point in the simulation, the physical system has been simulated up to the simulator's clock value, even though some individual lp's may have simulated the corresponding pp's far beyond T.
3.4.3

the behavior of the corresponding pp. We have shown that, if each lp behaves cor? rectly, the simulation as a whole behaves correctly. This observation may lead to ma? jor simplifications in designing complex simulations. In fact, distributed simula? tions can be implemented using existing sequential simulations; instead of reporting to a central event-list manager, an lp sends messages. In all other respects, the core of the simulation remains unchanged.
4. Distributed Simulation: Deadlock Resolution

Encapsulation of Physical Processes by Logical Processes

In distributed simulation, the radical de? parture from sequential simulation is the lack of any global control. (We show dead? lock resolution without global control in the next section.) Since a pp is simulated entirely by one lp, various different simu? lations of a pp can be attempted by substi? tuting different lp's for it. Furthermore, the correctness of simulation can be checked one lp at a time-the proof of correctness is naturally partitioned among lp's, that is, we show that each lp correctly simulates
Computing Surveys, Vol. 18, No. 1, March 1986

We have seen in the last section that the basic distributed simulation scheme may lead to deadlock even in acyclic networks. In this section we present several different approaches to resolution of deadlock. We comment on some of the most viable ap? proaches to deadlock resolution.
4.1 Overview of Deadlock Resolution

In all the examples we have seen so far, the simulator clock value (i.e., the minimum of all lp clock values) remains at some final value T forever. If T is smaller than the point up to which we need to run the sim? ulation, we have to apply some other

Distributed Discrete-Event Simulation

?

57

Figure 14.

A physical system with loop.

value, then lpi advances the simulation of PPi up to Ti? At this point lpi predicts for each outgoing channel, a sequence of mes? sages that the PPi would have sent. Thus lp, typically generates ? (tjl ' mjl), (tj2 ' mj2), . . . ) for transmission to lpj, for every j to which it has outgoing channels. Some of these sequences may be empty, in which case no message is sent to the correspond? ing lp. Suppose that lpi can further predict that after transmission of this message se? quence PP i will not send any more messages to PPj until time tj? Then, in the new scheme, lPi sends (tj, null) to lpj after send? ing the genuine message sequence. Since lpi knows the state of the corresponding pp up 4.2 Deadlock Resolution Using Null to time Ti, it can predict all messages (that Messages are to be sent) and absence of messages, at We postulate a new kind of message to be least up to Ti? Therefore, every outgoing used by the simulator: (t, null ) sent by lpi channel will have a last message on it with to lpj means that PPi sends no message to time component equal to or greater than PPj between the current channel clock value Ti? Note that, in any iteration, only the last of the channel from lpi to lpj and t; there? message sent along a channel may be a null fore, any future message from lpi to lpj will message. have a t-component exceeding t. Clearly Reception of a null message is treated in null messages have no counterpart in the the same manner as the reception of any physical system. A null message is used to other message: It causes the lp to update announce absence of messages. Absence of its internal state, including the clock value, messages in a physical system at time t is and (possibly), to send messages. recognized by no message being transmit? Suppose it is required to simulate the ted at that time. Unfortunately, the basic physical system up to some time T. Then scheme of the last section cannot guarantee every source must send messages until the absence of messages to an lp without send? t component of the last message equals T; ing it an actual (nonnull) message having if no nonnull message exists with this prop? a higher t-component value. erty, then finally, (T, null) should be sent. We now propose modifications to the basic algorithm of Section 3 to incorporate Example 4.1 null messages. Let us first review the basic distributed simulation scheme of the last Consider the physical system shown sche? section. Ti denotes the clock value of lpi. matically in Figure 14. We study the progress of one possible Whenever lpi receives a message, it properly updates Ti, and, if Ti changes in simulation run of this physical system. The scheme to advance the simulation. For instance, in the example of the primitive computer system (Example 3.3), the lp cor? responding to M cannot proceed any fur? ther unless it is told that Proc1 will never send it a message. In Example 3.5, lp x must be told that it will never receive any input along zx until x first sends a message. The first scheme we describe, using null messages, is effectively an implementation of this idea [Bryant 1977; Chandy and Misra 1979]. We also discuss some other schemes that avoid deadlock using different kinds of overhead messages.
Computing Surveys, Vol. 18, No. 1, March 1986

58

?

Jayadev Misra

every input channel must have sent mes? sages (t ', m'), t' ? t, along every outgoing channel; (2) every message that has been sent has been received when simulation loops through the system twice; that is, the terminates. Note that (1) could not be as? first time a job arrives at B2 , it is sent back serted in the basic scheme because an lp to M1, and on the second arrival at B2 it is need not send out messages with high? sent to the sink. er t-component values than the input Table 6 shows a succession of message messages. transfers, where each horizontal row is a We now claim that the channel clock time slice and each entry corresponds to a value for every channel is at least T. If not, single activity of one of the processes. It is consider a channel eJ for some lp, whose evident that several activities may happen channel clock value is t1, with tl < T. Ac? cording to the above observation, there ex? concurrently. ists a channel e2, which is an incoming 4.3 Correctness of the Simulation Algorithm channel to this lp, such that e2's channel The partial correctness results of the last clock value is t2, where t2 S t1. Continuing section still apply. The only difference now in this manner, we can construct a sequence is the presence of null messages. We define of channels, el , e2, .. ., ei, . . . such that for the simulation to be correct at some point, all i, ei+l is a predecessor channel of ei and ti+l S ti, and we have tl < T. Since the if it is correct according to the definition of physical network is finite, eventually we Section 3 after ignoring null messages. either (i) get to a source lp, or (ii) have a cycle of channels. In the first case, since Theorem 4 every source lp sends messages until the t Simulation is correct at every point. component of the last message sent is T, Proof. The proof is almost identical to we cannot have channel clock value of any the previous proof and hence omitted outgoing channel of a source lp smaller than T.In the second case, all channel clock here. 0 values in the cycle are equal to tl and The next theorem shows the power of tJ < T. From the predictability property adding null messages: We show that we (Section 2), for this cycle and this t1, there have a deadlock-free system that can sim? exists a pp, say PPJ , whose outputs can be ulate a physical system up to any desired determined beyond t1, given its inputs up time. to t 1 ? Hence, IpJ has some messages to send, which contradicts our assumption that the Theorem 5 simulation has terminated. Therefore, the Assume that every source p rocess sends mes? channel clock value of every channel is at sages until the t-component of a message least T, and hence the simulation clock equals T. Then every lp will simulate the value is at least T. We have implicitly used the fact that, for corresponding pp, at least up to T. any finite T, only a finite number of mes? Proof. Consider the point at which the sages may be transmitted in the logical simulation terminates, that is, at which all system. This is derived from the predicta? messages that have been sent have been bility property, in which the parameter E, received and no lp has any outstanding f > 0, is a fixed quantity. A more rigorous message to send. The following observation proof of this boundedness property may be is critical: For every lp (except a source lp) found in Chandy and Misra [ 1979]. 0 there exists an incoming channel to that lp whose channel clock value is less than or 4.4 Discussion equal to the channel clock value of every outgoing channel from that lp. This obser? It is interesting to note that the sim? vation follows because (1) an lp that has ulator never deadlocks; If the physical received messages at least up to t along system deadlocks, the simulator continues
X for 2 time units. Jobs are routed alter? nately to Y and Z from B 1 ? Y processes a job for 1 unit and Z for 4 units. Every job
Computing Surveys, Vol. 18, No. 1, March 1986

source sends out jobs that are processed at

S tep

Soure:e Snd.

Ree:

" 1

" 1 Snds

Ree:

X

Table 6.

X

Message Transmissions in the Simulation of Example 1

Snds ( 2 . nulll

Ree
11 1

11 II I 1 Sends Y Sends Z

Ree

Y

Y

Snds l PolU

Ree

Z

Z

1 2 3 4 5 6

t.,mlll

Snds

Ree
H 2

" 2 Snds

Ree
11 2

11 11 2 2 Snds " Snds S ink

( 2, 001]) ( 2 , null ( 2 , null ( 2 , .w.1l

9 11

a

7

2 (3,l2) ( ,J1 (6 , J 3 )
( 3, J,. J.null

(2,J ) 1

3,001.1;

2. null

6,.w. 1

(4. nul)) 6, .w.1l 3, .w. ll

I, ooll

o,.w.I 3,tull;

l, ruU 3, nuU
l,nu11 ( I , null )

(l,Jul1l (I, nUll
( 2,.1 ) ( 3,nul11 1 (4,J ) 1 ( 3 ,J ) 2

3,null )

( 3 , null )

10

p....u 1r1, J1 )
( 3 , .1 ) 2 (6,J 3

12
13 14

P ,J1ull
( 3 , null ( 3, null

IS
16 17

( 6 , J ) ( 4 ,J 1) 2 (6,J ) 2

( 3, null

( 4 , J ) (4 , nu11 1 (4 , 6 , null) ( 6 ,J ) 2

?)

19
20 21 22 23 24 25 26 (5,J ) 1 (4,J1uD) (4plll)

18

(5oJ l ) (6 , J 2 (8,nJl.(
(/I,nlil

(4,Jill

O,null

(7, ndl

(4,rull ( 5o l ) l

It,JlUll)
5 ,1 1) k4,P.1ll (5 ,J ) 1 (4,null) ( 4 ,null ) ( 5 ,J ) 1 ( 5 , nul/l)

10,?

( 50 J1)

(I.,ntlll)
(6, rull) (5 , J 1

(1.0) 2)

(7, mll) ?rai1)

.-

60

?

Jayadev Misra

computation by transmitting null messages with increasing t values. This correctly sim? ulates the corresponding physical situation, in that, while time progresses, no messages are transmitted in the physical system and the simulator terminates with every clock value at least at T. The simplicity of this scheme is one of its most attractive points. It requires small coding changes to send out null messages. Furthermore, the require? ment of unbounded buffers between two lp's is not really necessary. The same re? sults hold if there are only a finite number of buffer spaces between every lpi and lpj, and lpi has to wait to send if all buffer spaces are currently full. The proof that there is no deadlock in this situation is essentially contained in Chandy and Misra [ 1979]. The metric of interest in performance calculations is the turnaround time, that is, the amount of time it takes to complete the simulation, rather than processor utiliza? tion, that is, the fraction of time the pro? cessors are utilized. In fact, one would ex? pect the processors to be lightly utilized. The other parameter of interest, line band? width, has not received adequate attention. Empirical studies show that this scheme is quite efficient for acyclic networks [Seethalakshmi 1979] . Several factors seem to affect the efficiency in general networks:

topologies. Their conclusions are: "For some topologies of queueing networks models, this approach results in a speedup in the total time to complete a given simu? lation. However, for other topologies, es? pecially those with loops, the speedup may not be significant." They also investigated several different ways of partitioning the physical network so that more than one pp may be implemented on one lp. (2) Time-Out Mechanisms to Prevent Null Message Transmission. A slight modification to the scheme of this section may save a considerable number of message transmissions. A null message (t, m) has no effect if it is followed by another message (t', m'), t' > t. Therefore, it may be effi? cient to delay transmissions of null mes? sages in the hope that future messages received by an lp would make it unneces? sary to transmit them at all. Clearly, the amount of time T that an lp waits before transmitting a null message is of impor? tance. If T 0, we have the algorithm as stated in this section. If T = 00, null mes? sages are never transmitted, and then we have the basic algorithm of Section 3, which may lead to deadlock. Other values of T are of potential interest, but no empir? ical studies have been performed for other values. (3) Amount of Buffering on Channels. The number of buffer spaces on channels (1) Degree of Branching in the Network. seem to have substantial effects on per? Consider a network with one source and formance [Quinlivan 1981; Seethalakshmi one sink. The number of distinct paths 1979] . When the number of buffer spaces between the source and the sink is a (rough) was reduced to 0, senders had to wait until measure of the amount of branching in the the receivers were ready to receive, and a network. Null messages tend to get created considerable amount of time seemed to be at branches and they may proliferate at all spent in waiting. The number of buffer successive branches (if not subsumed). So, spaces was then increased and the following one would expect that the fewer the number rule was used to annihilate null messages: of branches, the better the performance. Any message put in the buffer after a null Empirical studies seem to confirm this message (and therefore with a higher t com? [Seethalakshmi 1979] . Theoretically, opti? ponent) annihilates any null message ahead mum efficiency is achieved for a tandem of it still in the buffer. The annihilation network (the assembly line example of Sec? rule is somewhat similar to the time-out tion 2, Example 2.4), and excellent results mechanism. It was found that, in the sim? are obtained for low-branching-type net? ulation of a certain class of queuing net? works. In general, acyclic networks exhibit works, the performance improved rapidly until the number of buffer spaces on reasonably good performance levels. Experiments were carried out by Peacock a channel approached 10, increased less et al. [ 1979a, 1979b] on networks of various rapidly until about 20, and remained
=

Computing Surveys, Vol. 18, No. 1, March 1986

Distributed Discrete-Event Simulation

?

61

essentially unchanged thereafter. However, these numbers cannot be applied directly to other problems; we expect these numbers to depend on the type of problem and the speeds of processors and lines. Next, we describe two different schemes that limit the number of null message transmissions. In the query-reply scheme (4.5), no null message is transmitted along a channel( y, z) until z demands to have ( y, z)'s clock value increased; y may then be forced to send a null message incre? menting the channel clock value of ( y, z). In the circulating marker scheme (4.6), a single marker is used to carry null mes? sages. It is not clear that either of these schemes is superior to the basic scheme, where null messages are transmitted after a proper time-out. Only empirical investi? gations can settle these issues.
Transmisision

from Pi to Pi+b for all i, 0 :s i < n. In addition, the query contains ti , clock value of the channel ( Pi+I , Pi) , for all i, o :s i < n . It is obvious that tj ? tj +I and O :s j < n - l. A reply for a query contains the query and a new clock value for the last channel in the query; that is, for a query ( p . . . y x ), there is a new (larger) clock value for channel (x, y). Additionally, a reply may contain one or more messages. In the fol? lowing we use "y has query (p . . . y) " as a Boolean proposition that is set true or false in the algorithm. Actions of Ip y are de? scribed by the following rules. (1) Initiating a query ::
if time-out then y has a

query(y).

(2) Upon receiving a reply to query ( p . . . y x ) ::
advance channel clock value of (x y) and receive messages, if any, in the reply; y has query (p . . . y).

4.5 Demand-Driven Null Message

Suppose that, on the basis of time-out, Ip z asks Ip y to advance the clock value of ( y, z). Such an advance is always possible if ( y, z)'s current clock value is less than y's clock value (which is the minimum of channel clock values of (x, y), for all x). In this case y sends a message, possibly null, advancing ( y, z)'s clock value. However, if ( y, z)'s clock value equals y's clock value, then no advance may be possible. In this case y has to advance its own clock first, making the same kind of request of all ip x for which (x, y)'s clock value equals y's clock value. Hence, effectively the request has been propagated by y. Only when y's clock value increases beyond ( y, z)'s clock value can y send a message to z increment? ing ( y, z)'s clock value. The propagations of requests may form a cycle, in which case a deadlock is detected. We sketch the algorithm below for an Ip y. A query is a message that is sent by one Ip to another to request that a channel clock value be advanced; queries will be propagated, in general. Hence, we assume that a query contains the path it has tra? versed and the channel clock values of all channels along the path; query ( Po PI . . . Pn) denotes a query initiated by Po and sent

(3) Ip y has or receives query ( p . . . z y) Iwhere the sequence may have only one element yl ::
if y appears more than once in the query then detect deadlock I recovery from deadlock is treated belowl

else if lp y can advance the channel clock value of (y z) then send reply to z (including the query, the new channel clock value and mes? sages, if any) else send query (p . . . z y x) to every x for which clock value of channel (x y) = clock value of Jp y (unless such a query has been sent and no reply is yet received).

A query eventually leads to either detection of a deadlock or increase of some channel clock value; we refer the reader to Chandy and Misra [ 1982] and Chandy et al. [ 1983] for the essential ideas in the proof of this claim. Consider the situation in Example 3.5. A query initiated by y is received by x, propagated to z, and then propagated to y, which detects deadlock. If the query were initiated by x, it is sent to z and is propa? gated by z to y; then y replies, advancing the channel clock value of ( y, z) to 20, z
Computing Surveys, Vol. 18, No. 1, March 1986

62

?

Jayadev Misra

sends the query to y again, and y sends the mation for deadlock detection, as described query to z, which detects deadlock. below. Resolution of deadlock is surprisingly Each lp has a I-bit flag to show whether difficult. In the above example x can detect the lp has received or sent a message since deadlock, but it cannot, in general, advance the last departure of the marker from the its own clock to 25, the channel clock value lp. We say that an lp is white if it has of the channel outside the deadlocked set. neither received nor sent a message since This is because the physical process x may the last departure of the marker from the send out a message, say at time 22, if it lp; the lp is black otherwise. Initially all ip's receives no message between 20 and 22 are black. The marker declares deadlock along either input channel. This is certainly when it finds that the last N ip's that is conceivable, for example, if x is an alarm has visited were all white when it arrived clock that is set at time 20 to go off at time at the lp, where N is the number of chan? 22 unless it is canceled before that time. nels in the network. The algorithm is cor? Therefore, lp x's clock value cannot be ad? rect if messages between two lp's, including vanced to 25. Resolution of deadlock may the marker, are received in the order sent; be accomplished by determining the mini? see Misra [ 1983] for a precise description mum of the "next event times": For every and proof of this result. lp in the deadlocked set, the time at which We can use this scheme to detect and a message will be sent (provided no further recover from deadlock. The marker, in ad? message is received up to then) is deter? dition to keeping the number of white lp's mined, and the clock value of the lp with it has seen since it last saw a black lp, the minimum clock value is advanced to carries the minimum of "next-event-times" this time. This calculation may be carried for the white lp's it visits: Each white lp out in a centralized or decentralized fash? can report the time of the next event, as? ion; in fact, the query may carry the next suming it receives no further messages, to event time for each lp it has seen, in which the marker, and the marker merely keeps case the detection of deadlock can also de? track of the smallest of these, and the cor? termine which lp may restart and at what responding lp. When the marker detects deadlock, it knows the next event time and clock value. the lp at which this next event occurs. Therefore, it can restart that lp. Alter? 4.6 Circulating Marker for Deadlock nately, a central process may broadcast Detection and Recovery (send messages to all ip's) to advance their A suggestion has been made in Chandy and clocks to the next event time in the system. Misra [ 1981 ] to let the basic simulation The overhead messages in this case are scheme deadlock, detect deadlock, and for marker transmissions. If deadlocks are recover from it. We now discuss two meth? infrequent, the marker may move slowly. ods for deadlock detection and recovery. In this case the deadlock may be detected Consider a marker that continuously cir? some time after it occurs, but the propor? culates in a network. It follows a cycle of tion of overhead messages to genuine mes? channels such that it traverses every chan? sages will be low. nel of the network sometime during a cycle. An elegant variation of this deadlock de? Such a cycle exists if the network is tection scheme has been discovered by strongly connected; new channels may be Chandy [unpublished notes] and refined by added to the network to make it strongly Kumar [ 1986]. As before, there is a marker connected. The marker is merely a special that visits the lp's. However, it visits them type of message. It initially starts at some in an arbitrary fashion, with the only re? lp. If an lp receives the marker, its obliga? quirement being that it visit each lp even .. tion is to send the marker (along its desig? tually. It collects the following information nated route) within a finite time of being from an lp when it visits it: (1) status idle (i.e., not having anything more to of the lp (an lp is idle if it will send no send). We let the marker carry some infor- more messages unless it first receives a
Computing Surveys, Vol. 18, No. I, March 1986

Distributed Discrete-Event Simulation

?

63

message; it is nonidle, otherwise), and (2) number of messages received along every input channel and number sent along every output channel of the lp. This information overwrites any previous information col? lected from that lp. Note that the infor? mation collected by a marker may become obsolete if an lp receives messages, becomes nonidle, and/or sends messages after the marker collects the information from the lp. Yet, the marker can declare deadlock if the information it has collected shows that every lp is idle and, for every channel, the number of messages sent equals the number of messages received. These schemes have to be modified for detecting deadlocks within a subnetwork in the logical system; we can determine, through preprocessing, the subnetworks that may deadlock, and then we can assign markers to these subnetworks.
5. SUMMARY AND CONCLUSION

In this section, we summarize the discus? sions about distributed simulation, its status, problems, and future research directions. We hope to have demonstrated that distributed simulation may be applied in every situation in which sequential dis? crete-event simulation may be applied. Our examples have been predominantly from the area of computer systems, since a queuing network description of a computer is a physical system. However, our physical systems encompass a large variety of real? world applications. Implementation of distributed simulation is possible in any language that allows creation of message communicating processes. The assignment of logical processes to physical processors should follow the guide? line that the message traffic among pro? cessors be as low as possible. Message communication may be accomplished either through a common memory (mes? sages are deposited in a common memory by the sender and removed by the receiver) or by other interaction mechanisms among processors. The important criterion is how loosely coupled the processors are. If two processors are tightly coupled, that is, if the logical processes on these processors ex-

change a large number of messages, then the processors must also exchange at least that many messages, and the message traffic will be heavy. If processors are loosely coupled, they can operate autono? mously, that is, without communicating with other processors, for longer periods of time. It is also easier to avoid deadlock among a set of logical processes if they are simulated on one processor, because a cen? tralized scheduler, employed for message communication, can also detect deadlock. Static partitioning of the physical net? work among a fixed number of processors requires preprocessing prior to simulation. Preprocessing is useful for many other rea? sons, too. In the circulating marker algo? rithm, preprocessing is needed to determine a (static) cyclic path for the marker. Pre? processing could also be used to partition the lp's such that the amount of branching is reduced and cycles are mostly contained within one processor. Preprocessing can de? termine other simulation parameters for time-out, sizes of buffers on channels, etc. This is an area that has been extensively studied for sequential simulations. It needs to be studied again for distributed simula? tion, since the problems are somewhat different in nature. We have sketched several variations of the basic scheme for deadlock resolution. There is little evidence yet of the superior? ity of any one scheme. The large number of heuristics suggests that some combina? tion may be appropriate for particular prob? lem domains. For instance, if we use a set of uniform processors, among which mes? sage communication is expected to be reg? ular, we can expect that deadlock will rarely arise, and therefore a (slowly) circulating marker scheme would be preferable. Also, the marker can be used to collect statistical information about the simulation itself, and hence the simulation parameters, such as time-outs, can be dynamically changed. We have not discussed specific hardware architectures that can support simu? lation. There has not been enough experi? mentation with distributed simulation to know where it spends most of its time, and whether any architectural improve? ment would be useful for all distributed
Computing Surveys, Vol.18, No.1, March 1986

64

?

Jayadev Misra

simulation problems. At present, any architecture that supports processes and communication among them would be appropriate. Currently, the most important problem in distributed simulation is the empirical investigation of various heuristics on a wide variety of problems to establish (1) which heuristics work well for which problems and on which machine architectures, (2) how to partition the physical system among a fixed set of processors, and (3) how to set simulation parameters such as time-outs and buffer sizes.
ACKNOWLEDGMENTS

CHANDY, K M., AND MISRA, J. 1981.

CHANDY, K M., AND MISRA, J. 1982.

Asynchronous distributed simulation via a sequence of parallel computations. Commun. ACM 24, 4 (Apr.), 198-205.

CHANDY, K M., MISRA, J., AND HOLMES, V. 1979. CHANDY, K M., MISRA, J., AND HAAS, L. M. 1983.

A distributed algorithm for detecting resource deadlocks in dis? tributed systems. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Ontario, Can? ada). ACM, New York, pp. 157-164. Distributed simulation of networks. Comput. Netw. 3, 105-113.

Distributed deadlock detection. ACM Trans. Comput. Syst. 1, 2 (May), 144-156.

CHRISTOPHER, T., EVENS, M., GARGEYA, R. R., AND LEONHARDT, T. 1983. Structure of a distributed

This research has been supported by a grant from the Air Force Office of Scientific Research under grant AFOSR 85-0252. I am deeply indebted to my friend and colleague, K M. Chandy of The University of Texas, Austin, for his help, advice, and stimulating ideas. I am thankful to the Computer Systems Lab at Stanford University, and in particular to Susan Owicki, for providing a proper environment for the initial preparation of this paper. I am grateful to Doug DeGroot, formerly of IBM, Yorktown Heights, and Devendra Kumar of The University of Texas, Austin, for their editing efforts and helpful comments on the first draft of this man? uscript. Unusually thorough reviews by two anony? mous referees and the help and guidance of Dick Muntz, associate editor of Computing Surveys, are deeply appreciated.
BAGRODIA, R., CHANDY, K M., AND MISRA, J. N.d.

DAHL, O. J., MYHRHAUG, B., AND NYGAARD, K 1970.

simulation system. In Proceedings of the 3rd In? ternational Conference on Distributed Computing Systems (Ft. Lauderdale, Fla.). IEEE, New York, pp. 584-589.

Simula 67 Common Base Language. Norwegian Computing Centre, Oslo, Norway. Principles of Discrete Event Simulation. Wiley, New York.

FISHMAN, G. S. 1978. FRANTA, W. R. 1977.

Process View of Simulation . Elsevier Computer Science Library, Operating and Programming Systems Series, P. J. Denning, Ed. Elsevier North-Holland, New York.

HOLMES, V. 1978.

Parallel algorithms on multiple processor architectures. Ph.D dissertation, Com? puter Science Dept., Univ. Texas at Austin, Aus? tin, Tex. Virtual time. ACM Trans. Prog. Lang. Syst. 7, 3 (July), 404-425.

JEFFERSON, D. R. 1985. KUMAR, D. 1986.

REFERENCES

Ph.D dissertation (in preparation). Computer Science Dept., Univ. Texas at Austin, Austin, Tex.

A message-based approach to discrete-event sim? ulation. IEEE Trans. Softw. Eng. , to appear.

LAVEN BERG, S., MUNTZ, R., AND SAMADI, B. 1983.

BEZIVIN, J., AND IMBERT, H. 1983.

BIRTWISTLE, G. M., DAHL, O. J., MYHRHAUG, B., AND NYGAARD, K 1973. Simula Begin. Auerbach,

Adapting a sim? ulation language to a distributed environment. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Ft. Lauder? dale, Fla.). IEEE, New York, pp. 596-603. BIRTWISTLE, G. 1979. DEMOS: A System for Dis? crete Event Simulation. Macmillan Press, New York.

Philadelphia.

BRYANT, R. E. 1977.

CHANDY, K M., AND MISRA, J. 1979.

Simulation of packet commu? nication architecture computer systems. Tech. Rep. MIT, LCS, TR- I 88, Massachusetts Institute of Technology, Cambridge, Mass.

Distributed simulation: A case study in design and verifica? tion of distributed programs. IEEE Trans. Softw. Eng . SE-5, 5, 440-452.

PEACOCK, J. K, WONG, J. W., AND MANNING, E. G.

Performance analysis of a rollback method for distributed simulation. In Performance '83, A. K Agrawala and S. K Tripathi, Eds. North Holland, New York, pp. 1 17-132. LONOW, G., AND UNGER, B. 1982. Process view of simulation in Ada. In 1982 Winter Simulation Conference (San Diego, Calif., Dec. 6-8). IEEE, New York, pp. 77-86. MISRA, J. 1983. Detecting termination of distributed computations using markers. In Proceedings of the 2nd ACM Principles of Distributed Computing (Montreal, Ontario, Canada). ACM, New York, pp. 290-293. PEACOCK, J. K, WONG, J. W., AND MANNING, E. G. 1979a. Distributed simulation using a network of processors. Comput. Netw. 3, 1, 44-56. 1979b. A distributed approach to queuing net? work simulation. In Proceedings of the Winter Simulation Conference (San Diego, Calif.). IEEE, New York, pp. 399-406.

Computing Surveys, Vol. 18, No. 1 , March 1986

Distributed Discrete-Event Simulation
QUINLIVAN, B. 1981.

?

65

Deadlock resolution in distrib? uted simulation. Master's thesis, Computer Sci? ence Dept., Univ. Texas at Austin, Austin, Tex.

SEETHALAKSHMI, M. 1979.

REYNOLDS, P. 1982.

Received February 1 985; final revision accepted May 1 986

A shared resource algorithm for distributed simulation. In Proceedings of the 9th International Symposium on Computer Architec? ture (Austin, Tex.). IEEE, New York, pp. 259-266.

A study and analysis of performance of distributed simulation. Master's thesis, Computer Science Dept., Univ. of Texas at Austin, Austin, Tex.

U.S. DoD 1982. Reference Manual for the ADA Pro? gramming Language. U.S. Department of De? fense.

Computing Surveys, Vol. 18, No.1, March 1986


推荐相关:

discrete-event-simulation_图文.ppt

discrete-event-simulation_工学_高等教育_教育专区。slides on discrete event ...Some uniform, some normally distributed. A Truck may go back to the ...


A TERAGRID-ENABLED DISTRIBUTED DISCRETE EVENT AGENT....pdf

A TERAGRID-ENABLED DISTRIBUTED DISCRETE EVENT AGENT-BASED EPIDEMIOLOGICAL SIMULATION_IT/计算机_专业资料。Winter Simulation Conference 仿真会议论文 ...


Using_Simulation_for_Large-scale_Distributed_System....pdf

Using_Simulation_for_Large-scale_Distributed_System_信息与通信_工程科技_专业...Discrete-event simulation - Can simulate a cluster with thousands of nodes ...


...Speculative, Synchronous, Discrete-Event Simulation.pdf

Chamberlain, “Analytic Performance Model for Speculative, Synchronous, Discrete-Event Simulation,” in Proc. of 14th Workshop on Parallel and Distributed ...


...of Structural Systems Using Discrete-Event Simulation.pdf

Reliability Assessment of Structural Systems Using Discrete-Event Simulation_专业...a simply supported beam subjected to a uniformly distributed load, w , is...


Unsynchronized parallel discrete event simulation.pdf

Unsynchronized parallel discrete event simulation_英语学习_外语学习_教育专区。ABSTRACT Distributed synchronization for parallel simulation is generally classified as ...


1 PARALLEL DISCRETE-EVENT SIMULATION USING PVM.pdf

Distributed discrete-event simulation. Computing Surveys, 18(1):39-65, March 1986. David M. Nicol and Richard M. Fujimoto. Parallel simulation today. ...


Concurrent vector discrete-event systems_图文.pdf

Concurrent vector discrete-event systems_信息与通信_工程科技_专业资料。628 ...data base management systems, and distributed computer and communication networks...


A DISCRETE-EVENT SIMULATION MODEL FOR THE RE-DESIGN....pdf

A DISCRETE-EVENT SIMULATION MODEL FOR THE RE-DESIGN OF A RECONFIGURABLE ...Distributed Discrete-E... 27页 1下载券 Parallel discrete even... 11页...


...for queueing networks parallel simulation.pdf

Key-words: Discrete event simulation, Distributed Simulation, Queueing networks (Resume : tsvp) ? ? A version of this report has been presented at ...


DISCRETE-EVENT SIMULATION USING SYSTEMC INTERACTIVE....pdf

DISCRETE-EVENT SIMULATION USING SYSTEMC INTERACTIVE SEMICONDUCTOR FACTORY MODELING...(scheduled or statistically distributed), setup procedures (especially for ...


...distributed discrete event simulation in Java.pdf

Formax Web-based distributed discrete event simulation in Java - Fornax: Web-based Distributed Di...


...a Distributed Full-System Simulation Framework a....pdf

Implementation of a Distributed Full-System Simulation Framework as a_专业资料...and harnessing ideas from parallel discrete-event simulation, the framework enab...


Distributed Discrete Event Simulation Optimistic Pr....pdf

Distributed Discrete Event Simulation Op


...method be applied to discrete-event simulation.pdf

Can the regenerative method be applied to discrete-event simulation_专业资料...(n + m) is distributed according to ' independently of X (n), and ...


...in Distributed Discrete Event Simulation.pdf

Abstract Stability of Event Synchronisation in Distributed Discrete Event Simulation_IT认证_资格考试/认证_教育专区。This paper is concerned with the behaviour ...


An E cient Conditional-knowledge based Optimistic Simulation ....pdf

Index Terms: Distributed simulation, time-warp, discrete-event simula- Abstract tion, optimistic computations, distributed algorithms. 1 Introduction Discrete-...


...analysis of distributed real-time systems_图文.pdf

SEW uses analytical models to quickly (in minutes) analyze large distributed systems. SEW is not a discrete-event simulation toolset; it therefore does ...


...in Development of a Parallel Discrete-event Simulation ....pdf

Case Study in Development of a Parallel Discrete-event Simulation Syst_专业...2 IDES DESIGN IDES, an Infrastructure for Distributed Enterprise Simulation, ...


...distributed discrete event simulation in Java.pdf

Formax Web-based distributed discrete event simulation in Java - In this paper we present an envi...

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com