Discrete Event

The Discrete Event (DE) Model of Computation defines a semantics for a network of Actors that produce discrete events, and whose executions are triggered by discrete events. A discrete event is a value with a time associated with it that is global on the level of the model. Each event also has, as a destination, an associated input port on an Actor. This destination is determined by a relation connecting to this input port the output port, or model input, from which the event is produced, or enters the model, respectively.

When an event exist in the model, at a particular time, with an input port on an Actor as its destination, this Actor must respond to the event at the associated time. This response may be to produce no output. However, if output events are produced, the time associated with these events must be equal to or later than that of its inputs. This constraint ensures weak causality.

Furthermore, for the currently implemented form of the Discrete Event MoC in Ptolemy II, in a model every dependency cycle along the reaction to and production of events must have at least one Actor that produces events strictly later in associated time than those of its inputs. In more recent conceptions of these semantics this restriction is lifted to a strictly broader monotonicity condition.

This MoC is a Synchronous one, since at the time associated with every event in the model, associated with the relation connected to its destination, each relation can be determined uniquely to either have a single event associated with that same time, or have no event at that time, in which case the output of the Actor or model input connected to such a relation is said to produce absent. In other words, like the Synchronous Reactive model, at each Reaction event a unique value, including absent, can be determined at each relation.

DE models are extensively used in simulation of networks, queueing systems, and digital circuits.

References

Semantics and Theory

  1. Edward A. Lee, Jie Liu, Lukito Muliadi and Haiyang Zheng, "Discrete-Event Models," a chapter from
    Claudius Ptolemaeus, Editor, "System Design, Modeling, and Simulation Using Ptolemy II", Ptolemy.org, 2014. (included in the release as $PTII/doc/books/systems/PtolemyII_DigitalV1_02.pdf)
    The models provided in this chapter are also available online.
  2. Baccelli, F., G. Cohen, G. J. Olster and J. P. Quadrat (1992). Synchronization and Linearity, An Algebra for Discrete Event Systems. New York, Wiley.
  3. Cassandras, C. G. (1993). Discrete Event Systems, Modeling and Performance Analysis, Irwin.
  4. Cataldo, A., E. A. Lee, X. Liu, E. Matsikoudis and H. Zheng (2006). "A Constructive Fixed-Point Theorem and the Feedback Semantics of Timed Systems." Workshop on Discrete Event Systems (WODES), Ann Arbor, Michigan, July 10-12.
  5. Lee, E. A. (1999). "Modeling Concurrent Real-time Processes Using Discrete Events." Annals of Software Engineering 7: 25-45.
  6. Liu, X., E. Matsikoudis and E. A. Lee (2006). "Modeling Timed Concurrent Systems." CONCUR 2006 - Concurrency Theory, Bonn, Germany, August 27-30,Springer.
  7. Ramadge, P. J. G. and W. M. Wonham (1989). "The control of discrete event systems." Proceedings of the IEEE 77(1): 81-98.
  8. Zeigler, B. P., H. Praehofer and T. G. Kim (2000). Theory of Modeling and Simulation, Academic Press.

Simulators and Tools

  1. Edward A. Lee, Jie Liu, Lukito Muliadi and Haiyang Zheng, "Discrete-Event Models," a chapter from
    Claudius Ptolemaeus, Editor, "System Design, Modeling, and Simulation Using Ptolemy II", Ptolemy.org, 2014. (included in the release as $PTII/doc/books/systems/PtolemyII_DigitalV1_02.pdf)
  2. Varga, A. (2001). The OMNeT++ Discrete Event Simulation System. Proceedings of the European Simulation Multiconference (ESM'2001), Prague, Czech Republic, June 6-9.

Distributed DE

  1. Chen, G. and B. K. Szymanski (2002). Searching for Parallelism in Discrete Event Simulation. Summer Computer Simulation Conference, San Diego, CA, Relevant to Ptides.
  2. Jefferson, D. (1985). "Virtual Time." ACM Trans. Programming Languages and Systems 7(3): 404-425.
  3. Misra, J. (1986). "Distributed Discrete Event Simulation." ACM Computing Surveys 18(1): 39-65.