The examples we have seen so far produce an output or accept an input at a precise time, within the limitations of the discrete model of time. The INTERVAL process below produces an output at any time after Min ticks and before Max ticks. The LTS for the process is depicted in Figure 12.4.

Figure 12.4. LTS for OUTPUT (1,3).

OUTPUT(Min=1,Max=3) =
       (start -> OUTPUT[1] | tick -> OUTPUT),
     OUTPUT[t:1..Max] =
       (when (t>Min && t<=Max) output ->OUTPUT
       |when (t<Max)           tick ->OUTPUT[t+1]
       ).

The technique of using choice with respect to the tick action allows us to model processes in which the completion time is variable, for example, due to loading or congestion.

A variation on the previous technique is a process that periodically produces an output at a predictable rate. However, the output may be produced at any time within the period. In communication systems, this kind of timing uncertainty is termed jitter. The JITTER process defined below is an example of how jitter can be modeled. Figure 12.5 depicts the LTS for the JITTER process.

Figure 12.5. LTS for JITTER(2).

JITTER(Max=2) =
       (start -> JITTER[1] | tick -> JITTER),
     JITTER[t:1..Max] =
       (output -> FINISH[t]
       |when (t<Max)   tick  -> JITTER[t+1]
       ),

FINISH[t:1..Max] =
       (when (t<Max)  tick -> FINISH[t+1]
       |when (t==Max) tick -> JITTER
       ).

Timeouts are frequently used to detect the loss of messages in communication systems or the failure of processes in distributed systems. Java provides a version of the wait() synchronization primitive that takes a timeout parameter – a wait() invocation returns either when notified or when the timeout period expires. The most elegant way to model a timeout mechanism is to use a separate process to manage the timeout, as shown below for a receive operation with a timeout. The timeout and receive processes are combined into a RECEIVER process.

TIMEOUT(D=1)
       = (setTO          -> TIMEOUT[0]
         |{tick,resetTO} -> TIMEOUT
         ),
     TIMEOUT[t:0..D]
       = (when (t<D) tick     -> TIMEOUT[t+1]
         |when (t==D)timeout  -> TIMEOUT
         |resetTO             -> TIMEOUT
         ).

     RECEIVE = (start   -> setTO -> WAIT),
     WAIT    = (timeout -> RECEIVE
               |receive -> resetTO -> RECEIVE
               ).

     ||RECEIVER(D=2) = (RECEIVE || TIMEOUT(D))
                     >{receive,timeout,start,tick}
                     @{receive,tick,timeout,start}.

In addition to tick, the start, receive and timeout actions are declared as low priority in the RECEIVER composite process. This is because maximal progress requires that an action take place when all the participants in that action are ready. However, the participants in interface actions depend on the system into which RECEIVER is placed, so we should not apply maximal progress to these actions within the RECEIVER process but later at the system level. Consequently, we give interface actions the same priority as the tick action. All internal actions have a higher priority. The minimized LTS for RECEIVER, which hides the internal actions concerned with setting and resetting the timeout, is depicted in Figure 12.6.

Figure 12.6. LTS for RECEIVER(2).

A version of the countdown timer model introduced in Chapter 2 is given below.

COUNTDOWN (N=3)   = COUNTDOWN[N],
     COUNTDOWN[i:0..N] =
       (when(i>0)  tick -> COUNTDOWN[i-1]
       |when(i==0) beep -> STOP
       ).

The COUNTDOWN process outputs a beep action after N ticks and then stops. The implementation is given in Program 12.2. The translation from the model is straightforward. Each invocation of the tick() method decrements the integer variable i. When i reaches zero, the next invocation of pretick() performs the beep action and the timer stops by removing itself from the time manager. The operation of TimeManager is described in the next section.

class TimedCountDown implements Timed {
  int i; TimeManager clock;

  TimedCountDown(int N, TimeManager clock) {
    i = N; this.clock = clock;
    clock.addTimed(this); // register with time manager
  }

  public void pretick() throws TimeStop {
    if (i==0) {
        // do beep action
        clock.removeTimed(this); // unregister = STOP
    }
 }

 public void tick(){ --i; }
}

The next example implements the producer – consumer model of section 12.1.1. To keep the code succinct, the timed class definitions are nested inside the ProducerConsumer class of Program 12.3. The class creates the required instances of the Producer, Consumer and TimeManager classes.

class ProducerConsumer {
  TimeManager clock = new TimeManager(1000);
  Producer producer = new Producer(2);
  Consumer consumer = new Consumer(2);
  ProducerConsumer() {clock.start();}

  class Consumer implements Timed {...}
  class Producer implements Timed {...}
}

For convenience, the PRODUCER process is listed below:

PRODUCER(Tp=3) =
       (item -> DELAY[1]),

DELAY[t:1..Tp] =
       (when(t==Tp) tick -> PRODUCER
       |when(t<Tp) tick -> DELAY[t+1]
       ).

Initially, the producer outputs an item and then waits for Tp clock ticks before outputting another item. The timed class that implements this behavior is listed in Program 12.4.

class Producer implements Timed {
    int Tp,t;

    Producer(int Tp) {
      this. Tp = Tp; t = 1;
      clock.addTimed(this);
    }

    public void pretick() throws TimeStop {
      if (t==1) consumer.item(new Object());
    }

    public void tick() {
      if (t<Tp) { ++t; return; }
      if (t==Tp) { t = 1; }
    }
 }

An instance of the Producer class is created with t=1 and the consumer.item() method is invoked on the first pre-tick clock phase after creation. Each subsequent tick increments t until a state is reached when another item is output. The behavior corresponds directly with PRODUCER.

Now let us examine how the item() method is handled by the consumer. The timed model for the consumer is shown below. The consumer waits for an item and then delays Tc ticks before offering to accept another item.

CONSUMER(Tc=3) =
       (item -> DELAY[1] | tick -> CONSUMER),
     DELAY[t:1..Tc] =

(when(t==Tc) tick -> CONSUMER
       |when (t<Tc) tick -> DELAY[t+1]
       ).

The implementation of CONSUMER is listed in Program 12.5.

class Consumer implements Timed {
  int Tc,t; Object consuming = null;

  Consumer(int Tc) {
    this. Tc = Tc; t = 1;
    clock.addTimed(this);
    }

    void item(Object x) throws TimeStop {
      if (consuming!=null) throw new TimeStop();
      consuming = x;
    }

    public void pretick() {}

    public void tick() {
      if (consuming==null) return;
      if (t<Tc) { ++t; return;}
      if (t==Tc) {consuming = null; t = 1;}
    }
  }

In the Consumer class, the tick() method returns immediately if the consuming field has the value null, implementing the behavior of waiting for an item. The item() method sets this field when invoked by the producer. When consuming is not null, the tick() method increments t until Tc is reached and then resets consuming to null indicating that the item has been consumed and that another item can be accepted. Effectively, consuming represents the DELAY states in the model. If the producer tries to set consuming when it is not null then a TimeStop exception is thrown. This signals a timing inconsistency in exactly the same way that a time-stop deadlock in the model is the result of a timing inconsistency. TimeStop is thrown if the producer tries to output an item when the previous item has not yet been consumed. As we see in the next section, a TimeStop exception stops the time manager and consequently, no further actions are executed. The implementation of producer – consumer has exactly the same property as the model. For correct execution, Tc must be less than or equal to Tp. Note that, in the Consumer class, the method pretick() has no implementation because the class has no outputs.

The operation of the two-phase clock cycle should now be clear. Methods on other objects are invoked during the pre-tick phase and the changes in state caused by these invocations are recognized in the tick phase. This ensures that actions complete in a single clock cycle. However, this scheme only approximates the maximal progress property of timed models. Maximal progress ensures that all actions that can occur happen before the next tick. Our implementation scheme only gives each timed object one opportunity to perform an action, when its pretick() method is executed. A multi-way interaction between timed objects thus requires multiple clock cycles. An example of a multi-way interaction would be a request action followed by a reply followed by an acknowledgment (threeway). Maximal progress in the model ensures that such a multi-way interaction would occur within a single clock cycle if no intervening tick events were specified. We could implement a multi-phase clock scheme to allow multi-way interaction in a single clock cycle, however this complexity might be better dealt with by reverting to a thread-based implementation scheme. In fact, the examples later in the chapter show that the two-phase scheme is sufficiently powerful to implement quite complex systems that exhibit the same behavior as their models. We take care that multi-way interaction within a single clock cycle is not required. This usually means that we introduce an intervening tick in the model, for example between a request and a reply.

In addition to the ease with which models can be translated into implementations, the event-based implementation scheme has the advantage, when compared to the thread-based scheme, that we do not have to synchronize access to shared objects. The activations of the tick() and pretick() methods of a timed object are indivisible with respect to other a ctivations of these methods. This is because the methods are dispatched sequentially by the time manager. Method dispatch incurs much less overhead than context switching between threads. Consequently, the event-based scheme is more efficient in systems with large numbers of time-driven concurrent activities. An example of such a system is presented in the final section of the chapter.

The generator process GEN, defined below, generates a parcel every T units of time. Each parcel contains the number of its destination. The generator picks a destination for a parcel using non-deterministic choice.

range Dest = 0..3
set Parcel = {parcel[Dest]}

GEN(T=3) =
  (enter[Parcel] -> DELAY[1] | tick -> GEN),
DELAY[t:1..T] =
 (tick -> if (t<T) then DELAY[t+1] else GEN).

The destination bins are property processes that assert that the parcel delivered by the routing network to the bin must have the same destination number as the bin.

property
    BIN(D=0) = (dest[D].parcel[D] -> BIN)
               +{dest[D][Parcel]}.

We have subdivided the routing network into three stages. Each stage has an identical structure. The parameter to a stage determines its level in the routing network. The structure of the STAGE composite process is depicted in Figure 12.9.

Figure 12.9. STAGE structure.

The composition expression which Figure 12.9 represents graphically is:

||STAGE(L=0) =
        ( a:CHUTE || b:CHUTE || g:SWITCH
        || s:SENSORCONTROLLER(L)
        )/{ enter/a.enter,   b.enter/{s.sense,a.leave},

g.enter/b.leave, s.setSwitch/g.setSwitch,
            left/g.leave[0], right/g.leave[1],
            tick/{a,b,g}.tick
          } >{enter,left,right,tick}
             @{enter,left,right,tick}.

Each physical chute in the physical device is modeled by a set of CHUTE processes. A CHUTE process models the movement of a single parcel through a segment of a physical chute. To model a chute that can have n parcels dropping through it, we need n CHUTE processes. In modeling the system, we use two processes and so we are modeling a physical chute that can accommodate only two parcels. The CHUTE process is given below:

CHUTE(T=2) =
       (enter[p:Parcel] -> DROP[p][0]
       |tick            -> CHUTE
       ),
     DROP[p:Parcel][i:0..T] =
       (when (i<T)  tick     -> DROP[p][i+1]
       |when (i==T) leave[p] -> CHUTE
       ).

A parcel enters the chute and leaves after T units of time. We must be careful when composing CHUTE processes that the resulting composition has consistent timing. For example, the following system has a time-stop.

||CHUTES = (first:CHUTE(1) || second:CHUTE(2))
                /{second.enter/first.leave,
                  tick/{first,second}.tick}.

It happens when a parcel tries to enter the second CHUTE before the previous parcel has left. Time-stop in this context can be interpreted as detecting a parcel jam in the physical device. For consistent timing in a pipeline of CHUTE processes, each process must have a delay which is the same or greater than the delay of its successor.

This process detects a parcel by observing the action caused by a parcel passing from one CHUTE to the next. Based on the destination of the parcel, it computes how the switch should be set. This routing function depends on the level of the stage. Because the network is a binary tree, it is simply (destination > Level)&1 (in this expression context, > is the bit shift operator and & the bit-wise and operator). The function returns either zero, indicating left, or one, indicating right. SENSORCONTROLLER is not a timed process since we assume that detection of the parcel and computation of the route take negligible time. Each execution occurs within a clock cycle.

SENSORCONTROLLER(Level=0)
       = (sense.parcel[d:Dest] -> setSwitch[(d>Level)&1]
          -> SENSORCONTROLLER).

During the time that a parcel takes to pass through the parcel switch, it ignores commands from the SENSORCONTROLLER. This models the physical situation where a parcel is passing through the switch and consequently, the switch gate is obstructed from moving.

range Dir = 0..1 //Direction  0  =  left,  1  =  right

SWITCH(T=1)   = SWITCH[0],
SWITCH[s:Dir] =
  (setSwitch[x:Dir] -> SWITCH[x]    //accept switch command
  |enter[p:Parcel]  -> SWITCH[s][p][0]
  |tick             -> SWITCH[s]
  ),
SWITCH[s:Dir][p:Parcel][i:0..T] =
    (setSwitch[Dir]         -> SWITCH[s][p][i]  //ignore
    |when (i<T) tick        -> SWITCH[s][p][i+1]
    |when (i==T)leave[s][p] -> SWITCH[s]
    ).

The SWITCH process extends the behavior of the CHUTE process with an additional component of its state to direct output and an extra action to set this state. SWITCH can be implemented by deriving its behavior, using inheritance, from the implementation of CHUTE.

Having completed the definition of all the elements of the PARCEL_ROUTER model, we are now in a position to investigate its properties. We first perform a safety analysis of a minimized PARCEL_ROUTER(3). This system feeds a new parcel every three timing units into the routing network. This produces the following property violation:

Trace to property violation in BIN(0):
            enter.parcel.0
            tick
            tick
            tick
            enter.parcel.1
            tick
            tick
            tick
            enter.parcel.0
            tick
            tick
            tick
            enter.parcel.0
            tick
            dest.0.parcel.0
            tick
            tick
            enter.parcel.0
            tick
            dest.0.parcel.1

The trace clearly shows that a parcel intended for destination one has ended up in BIN zero. However, while it may be obvious to the reader why this has occurred, it is not clear from the trace since we have hidden the intermediate events that occur in each stage. We can elicit more information from the model in a number of ways. We can make internal actions visible and rerun the analysis or we can investigate the problem using the animator tool provided by LTSA. The second approach has the advantage that we do not need to modify the model in any way. We simply select STAGE as the target for analysis (with default level parameter as 0) and run the Animator using the following menu to specify the actions we wish to control.

menu TEST = {enter[Parcel],tick}

The trace depicted in Figure 12.10 was produced by initially choosing an enter.parcel.0 action followed by three tick actions, then enter.parcel.1 followed by five ticks. This is the trace produced by the safety violation, without the subsequent parcel entries. The Animator trace clearly exposes the reason for the violation. The first parcel is still in the switch when the sensor detects the second parcel and tries to set the switch to direction 1. Since the first parcel is in the switch, the s.setSwitch.1 action is ignored and the switch does not change. Consequently, the second parcel follows the first in going to the left when it should have been switched to the right.

Figure 12.10. Animation trace for STAGE(0).

The physical interpretation of the problem is that parcels are too close together to permit correct routing. We can check this intuition by analyzing a system with a slower parcel arrival rate, PARCEL_ROUTER(4). Safety analysis finds no problems with this system and progress analysis demonstrates that the TIME property is satisfied.

In the next section, we describe a simulation of the parcel router based on the model. This implementation faithfully follows the model in allowing parcels that are too close together to be misrouted.

The entities that comprise the Space Invaders game have behavior in common with respect to the way that they move about in the game space. We model this common behavior as the SPRITE process listed below. The behavior of the spaceship, missiles and aliens is defined using this process.

SPRITE =
       (create[x:D][y:D] -> SPRITE[x][y]
       |tick -> SPRITE
       |pos.undef -> SPRITE
       ),
     SPRITE[x:D][y:D] =
       (pos[x][y] -> SPRITE[x][y]
       |tick ->
        (north -> if y>0   then SPRITE[x][y-1] else END
        |south -> if y<MAX then SPRITE[x][y+1] else END
        |west  -> if x>0   then SPRITE[x-1][y] else END
        |east  -> if x<MAX then SPRITE[x+1][y] else END

| {rest,action[x][y]} -> SPRITE[x][y]
        )
       ),
     END = (end -> SPRITE).

Before a sprite is created, its location is undefined. A query using the action pos will return the undef value for its location. After the create action, pos returns a valid coordinate for the sprite's current location. At each clock tick, a sprite can move in one of four directions, or it can remain in the same position (rest action). The sprite implementation described in the next section allows a sprite to move in one of eight directions; however, four directions are sufficient detail for modeling purposes. In addition to moving, a sprite can instigate an action during a clock cycle. When a sprite moves out of the game space, it indicates that it has terminated by performing the end action. In an implementation, a sprite would then be garbage collected. In the model, the sprite goes back to the state in which it can be created. As described in Chapter 9, we use cyclic behavior to model dynamic creation. The set of actions that the SPRITE process can engage in – excluding tick and the position query pos –is specifiedby:

set Sprite =
  {north,south,west,east,rest,action[D][D],create[D][D]}

An alien is a sprite that moves down the screen. Consequently, we can specify its behavior by constraining the movement of the SPRITE process. In the model, an alien starts at the top of the screen and moves vertically down; in the implementation, it can also move diagonally down.

ALIEN_CONSTRAINT =
       (create[D][0] -> MOVE),
     MOVE =
       (south -> MOVE | end -> ALIEN_CONSTRAINT)
       +Sprite.

     ||ALIEN = (SPRITE || ALIEN_CONSTRAINT).

The constraint permits an alien to be created at any x-position at the top of the screen and only permits it to move south and then end when it leaves the screen. The ALIEN composite process permits only these actions to occur since the constraint has the Sprite alphabet.

The behavior of the missile sprite is defined in exactly the same way. In this case, the missile is only permitted to move north, up the screen.

MISSILE_CONSTRAINT =
        (create[D][MAX] -> MOVE),
     MOVE =
       (north -> MOVE | end -> MISSILE_CONSTRAINT)
       + Sprite.

     ||MISSILE = (SPRITE || MISSILE_CONSTRAINT).

The spaceship has more complex behavior. It is constrained to moving horizontally at the bottom of the screen, either east or west, or staying in the same position, rest. It is created in the center of the screen and is constrained not to move off the screen. The spaceship can perform an action, which is used to create a missile, as explained later. In fact, the implementation permits the spaceship to move up and down the screen as well. However, horizontal movement is sufficient detail for us to gain an understanding of the operation of the system from the model.

SPACESHIP_CONSTRAINT =
        (create[MAX/2][MAX] -> MOVE[MAX/2]),
     MOVE[x:D] =
        ( when (x>0)  west -> MOVE[x-1]
        | when (x<MAX) east -> MOVE[x+1]
        | rest -> MOVE[x]
        | action[x][MAX] -> MOVE[x]
        ) + Sprite.

     ||SPACESHIP =(SPRITE || SPACESHIP_CONSTRAINT).

Collision detection is modeled by the COLLIDE process which, after a tick, queries the positions of two sprites and signals a collision through the action explode if their positions coincide. Undefined positions are excluded. In the implementation, the detection of a collision results in the creation of an explosion sprite that displays a series of images to create the appropriate graphic appearance. In the model, we omit this detail.

COLLIDE(A='a, B='b) =
       (tick -> [A].pos[p1:Coord] -> [B].pos[p2:Coord]
        -> if (p1==p2 && p1!='undef && p2!='undef) then
              ([A][B].explode -> COLLIDE)
           else
              COLLIDE
       ).

The composite process SPACE_INVADERS models a game that, in addition to the spaceship, permits only a single alien and a single missile to appear on the screen. This simplification is required for a model of manageable size. However, we have defined sprites as having cyclic behavior that models recreation. Consequently, the alien can reappear in different start positions and the spaceship can launch another missile as soon as the previous one has left the screen. The model captures all possible behaviors of the combination of spaceship, alien and missile.

To model launching a missile, we have associated the spaceship's action with the missile's create by relabeling. Two collision detectors are included to detect spaceship–alien and alien–missile collisions.

||SPACE_INVADERS =
        ( alien   :ALIEN
        || spaceship:SPACESHIP
        || missile:MISSILE
        || COLLIDE('alien,'spaceship)
        || COLLIDE('missile,'alien))
        /{spaceship.action/missile.create,
          tick/{alien,spaceship,missile}.tick}
        >{tick}.

Safety analysis of SPACE_INVADERS does not detect a time-stop and progress analysis demonstrates that the TIME progress property is satisfied. Further, the progress properties:

progress SHOOT_ALIEN={missile.alien.explode}
progress ALIEN_SHIP ={alien.spaceship.explode}

are satisfied, showing that both alien – missile and alien – spaceship collisions can occur. To gain an understanding of the operation of the model, we can animate it to produce example execution traces. An alternative approach to producing sample traces is to use safety properties as follows. Suppose we wish to find a trace that results in a collision between an alien and a missile. We specify a safety property that the action missile.alien.explode should not occur and analyze the system with respect to this property:

property ALIEN_HIT = STOP + {missile.alien.explode}.
||FIND_ALIEN_HIT = (SPACE_INVADERS || ALIEN_HIT).

The trace produced is:

Trace to property violation in ALIEN_HIT:
          alien.create.1.0
          spaceship.create.2.4
          tick
          alien.south
          spaceship.west
          missile.pos.undef
          alien.pos.1.1
          spaceship.pos.1.4
          tick
          alien.south
          spaceship.action.1.4 – missile launched
          missile.pos.1.4
          alien.pos.1.2
          spaceship.pos.1.4
          tick
          alien.south
          missile.north
          missile.pos.1.3
          alien.pos.1.3
          missile.alien.explode

Exactly the same approach can be used to find a trace leading to a spaceship – alien collision.

The emphasis of the Space Invaders model is not so much on demonstrating that it satisfies specific safety and liveness properties but rather as a means of investigating interactions and architecture. After all, the program is far from a safety-critical application. However, in abstracting from implementation details concerned with the display and concentrating on interaction, the model provides a clear explanation of how the program should operate. In addition, it provides some indication of how the implementation should be structured. For example, it indicates that a CollisionDetector class is needed and confirms that a Sprite class can be used to implement the common behavior of missiles, aliens and the spaceship.

The display for the Space Invaders program is handled by the two classes depicted in Figure 12.15. A Sprite is created with an initial position and an image. The SpriteCanvas maintains a list of sprites. Every clock tick, the SpriteCanvas calls the paint() method of each sprite on its list. The sprite then draws its image at its current position.

Figure 12.15. Sprite and SpriteCanvas classes.

The move() method has a direction parameter that specifies one of eight directions in which the sprite can move. It is called by a subclass each clock cycle to change the position of the sprite. The collide() method tests whether the sprite's bounding rectangle intersects with the sprite passed as a parameter. The hit() method is called by the collision detector when a collision is detected. PosX() and PosY() return the current x and y coordinates of the sprite.

The collision detector maintains a list of the alien sprites and missile sprites and a reference to the spaceship sprite as shown in Figure 12.16. Every clock cycle, the detector determines whether each alien has collided with either a missile or the spaceship. If a collision is detected, the hit() methods of the sprites involved in the collision are invoked.

Figure 12.16. CollisionDetector class diagram.

The method listed below is the implementation provided for the hit() method in the Alien class.

public void hit() {
  new Explosion(this);
  SpaceInvaders.score.alienHit();
  SpaceInvaders.detector.removeAlien(this);
  remove(); // remove from SpriteCanvas
}

The method creates a new explosion sprite at the same location as the alien, records an alien hit on the scoreboard and removes the alien from the collision detector and the display. The CollisionDetector, Alien, Missile and Spaceship classes implement the essential behavior of the game. These classes correspond to the COLLIDE, ALIEN, MISSILE and SPACESHIP model processes.

The SpaceInvaders applet class creates the spaceship, the alien generator, the missile launcher and the score board in addition to the display, time manager and collision detector as shown in Figure 12.17.

Figure 12.17. SpaceInvaders class diagram.

The AlienGenerator waits for a random number of clock cycles and then creates a new alien with a randomly chosen start position and a random downward direction. The MissileLauncher creates a new missile when the space bar is pressed. The x-coordinate of the new missile is the current position of the spaceship. The classes included in Figure 12.17 provide the infrastructure for scoring and the creation and display of sprites.

The collision detector and display run during the pre-tick clock phase; the remaining program actions, such as sprite movement, occur during the tick phase. This permits the display to render a consistent set of positions and for the effect of hits to be computed during tick processing. However, in reality, we could implement this sort of program using only a single-phase clock. This is because the clock ticks rapidly and, since the screen is updated every cycle, any inconsistencies which resulted from an action happening over two clock cycles rather than one would not be visible to a user.