Enhanced deadline

[edwardalee]

Currently, a deadline violation handler for a reaction to be triggered at logical time t is defined to be invoked only after logical time advances to t and all precedent reactions have been invoked and after physical time T > t + d, where d is the deadline. A more useful behavior would be to invoke the deadline handler as soon as it is clear that the deadline cannot be met. In the absence of execution time information, this occurs when physical time T exceeds t + d if there is an event on the event queue with logical time t.

This is realizable, in principle, by setting a timer that invokes a callback at T = t + d. The timer should be set when an event that triggers a reaction with a deadline is put on the event queue. The callback function will check whether the event is still on the event queue and, if so, invoke the handler.

There are some semantic subtleties.

First, what should be the logical time value during the handler's execution? I suggest it be "current logical time," whatever that happens to be, but the handler will also need access to time t.

Second, to enforce mutual exclusion, if any reaction r of the same reactor is running at time T, then the callback function cannot immediately invoke the handler, but must instead arrange for it to be invoked as soon as r finishes.

In federated execution, one interesting use of this feature is to detect the situation where null messages are getting excessively delayed. At the federate that receives these messages, all you have to do is create a periodic timer that triggers a reaction with a deadline. The deadline violation handler will be invoked whenever the spacing between null messages exceeds (in physical time) the period of the timer (a logical time).

[lhstrh]

First, what should be the logical time value during the handler's execution? I suggest it be "current logical time," whatever that happens to be, but the handler will also need access to time t.

To me, this also seems to be the most logical choice.

Second, to enforce mutual exclusion, if any reaction r of the same reactor is running at time T, then the callback function cannot immediately invoke the handler, but must instead arrange for it to be invoked as soon as r finishes.

That also sounds like a sensible solution to me.

All in all, I like this proposal a lot.

[cmnrd]

I suggest it be "current logical time," whatever that happens to be, but the handler will also need access to time t.

This worries me, as it would certainly be a source of non-determinism, and I don't understand yet what the consequences of this could be. Imagine a larger LF program where both the actual reaction and the deadline handler write to a port and thus trigger reactions in downstream reactors.

[edwardalee]

Note that any invocation of a deadline handler introduces nondeterminism. Do you have an alternative suggestion that would be less nondeterministic in any way?

[cmnrd]

Right, but at least now we know when (in logical time) the handler is invoked. I don't have a better suggestion, but I am a bit concerned about loss of functionality and potential loopholes. Imagine this:

reactor {
  timer t(0, 1 sec)
  output out: int
  reaction (t) -> out {=
    out.set(1);
  =} deadline(1 msec) {=
   out.set(-1);
  =}
}

This would send a sequence of 1 and -1 in regular intervals. The downstream reactor could rely on being triggered every second and could interpret -1 as an error value. How could we realize this example with the proposed deadline mechanism?

[edwardalee]

You could get the behavior you want like this:

reactor {
  timer t(0, 1 sec)
  logical action a
  output out: int
  reaction (t) -> out {=
    out.set(1);
  =} deadline(1 msec) {=
   schedule(a, get_intended_time() - get_logical_time();
  =}
  reaction(a) {=
   out.set(-1);
  =}
}

[lsk567]

Before we proceed further, perhaps it is good to have a consensus on what the ideal deadline semantics should be. The goal of having deadlines is to establish a relationship between the advancement of logical time and the (continuously increasing) physical time. If logical time lags behind physical time, there should be some (deadline) handlers that handle this situation.

There are currently 3 options on the table:

1. classical deadlines,
2. preemptive deadlines (which do not disrupt running reactions),
3. lag triggers.

Here is a running example:

reactor A {
    input in:int;

    // reaction 1
    reaction(in) {=
        sleep(1); // Takes 1 sec to finish.
    =}

    // reaction 2
    reaction(in) {=...=}

    // reaction 3
    reaction(in) {=...=} deadline(500 msec) {==}
}

Classical deadlines

Under the semantics of classical deadline, the runtime checks whether a reaction has violated its deadline when this reaction is about to be executed. Classical deadlines are currently implemented in the runtime.

In the running example, if in is present, the runtime

1. checks if reaction 1 has violated its deadline (none). If not, execute reaction 1;
2. checks if reaction 2 has violated its deadline (none). If not, execute reaction 2;
3. checks if reaction 3 has violated its deadline (500 msec). If not, execute reaction 3.

Under this semantics, the sequence of reaction invocation is N1 -> N2 -> N3's handler.

Preemptive deadlines

Under this semantics, the runtime aims to detect deadline violations as soon as possible such that a later reaction's deadline handler can be invoked before an earlier reaction gets executed. This is the semantics proposed in this thread.

In the running example, if in is present, the runtime

1. checks if any enabled deadlines have been violated (500 msec). If not, execute reaction 1;
2. checks if any enabled deadlines have been violated (500 msec). If not, execute reaction 2;
3. checks if any enabled deadlines have been violated (500 msec). If not, execute reaction 3.

Under this semantics, the sequence of reaction invocation is N1 -> N3's handler -> N2.

Lag trigger

The point behind having deadline handlers is to not have logical time lag behind physical time too much. However, an implicit requirement for the deadline handler to even run is that the reaction needs to be triggered. So if reactions don't get triggered, the lag problem persists. @edwardalee thought about having a lag trigger, which looks like this.

reactor A {
   input in:int;

   // Lag handler
   reaction(lag(in, 500 msec)) {=
       // Some handlers.
   =}

   // reaction 1
   reaction(in) {=
       sleep(1); // Takes 1 sec to finish.
   =}

   // reaction 2
   reaction(in) {=...=}

   // reaction 3
   reaction(in) {=...=} deadline(500 msec) {==}

   // reaction 4
   reaction(in) {=...=} lag(in, 500 msec) {==}

   // reaction 5
   reaction(deadline(in, 500 msec)) {=
       // Some handlers.
   =}

   // reaction 6
   deadline d(in, 500 msec);
   reaction(d, in) {=
       // Mutual exclusion
       if (d->is_present) {
           ...
       } else {
           ...
       }
   =}

   // reaction 7
   lag l(500 msec); // Monitors all inputs. Use contained reactors to monitor subsets.
   reaction(l) {==}
}

The advantage is that the lag trigger can allow users to handle lagging without the need to have reactions triggered by some data signals. This feature, when combined with modal models, can express useful patterns like switching from advanced to safe controllers if the lag exceeds some threshold.

[edwardalee]

Just want to point to related issue #403

[erlingrj]

Just a thought about getting the intended behavior without changing syntax too much. Could using "soft deadline" be used to indicate a deadline handler being invoked at the logical time of the reaction. (Which can then execute the reaction afterward? And "firm deadline" indicates a deadline handler triggered ASAP when its associated reaction is on the event-queue and lag has already exceeded the deadline?

A firm deadline implies mutual exclusion while soft deadline does not. So a firm deadline would remove the associated reaction event from the queue. Events produced by the firm deadline might be tagged with the current (non-deterministic) logical time or the logical time of its trigger.

reaction(in) {=...=} soft deadline(10 msec) {==}

reaction(in) {=...=} firm deadline(10 msec) {==} 

[edwardalee]

I suggest we use the following terms:

Implemented:

• lazy deadline: handler invoked only when the reaction is ready to be invoked.
• cooperative lazy deadline: Extension of the lazy deadline to use of lf_check_deadline in reaction body (see AnytimePrime.lf. This handles the situation where the deadline handler is not triggered, but a deadline violation occurs during execution of the regular reaction.

Not yet implemented:

• eager deadline: violation handler invoked as soon as possible after violation becomes inevitable, see #1006. The logical time of the handler may be earlier than the logical time of the event whose deadline is violated.
• cooperative eager deadline: eager deadline where the regular reaction includes calls to lf_check_deadline().
• preemptive deadline: lazy or eager deadline where the regular reaction may get aborted with a longjump, as in #403.
• strongly preemptive deadline: Handler is invoked as soon as a violation becomes inevitable regardless of what else is going on. Such a handler should not have access to any LF features (outputs, state variables, or modes), though it could perhaps schedule physical actions.

I think we can realize all of these except the last with just one more keyword, eager, and an API for using setjump and longjump in the body of a reaction. E.g., to get a preemptive eager deadline, we could do this:

    reaction(in) -> out {=
        lf_preempt_on_deadline(); // Set timer to call longjump.
        if (!setjump()) {
            ... do work that may be aborted
        }
    =} eager deadline {=
       ... handle case where deadline violation occurs before the normal reaction is invoked ...
    =}

I'm not sure the strongly preemptive deadline is a good idea. A better solution may be a lag trigger, as in this:

    reaction(lag > 100 msec) {= ... =}

This reaction would be enabled whenever time is advanced and the lag exceeds the specified threshold. It would be invoked in normal order depending on any other dependencies it may have.

[edwardalee]

See #1379 for Watchdogs, an alternative to eager deadlines that appears to be simpler and more flexible.