Design of output control reactions

[Soroosh129]

Preamble

Imagine the following federated program:

target C;
reactor Fed {
    input in:int;
    output out:int;
}
federated reactor {
    fed = new Fed();
}

For a federated program, this is changed to the following via an AST transformation¹:

In other words, the generator can produce 4 different kinds of network reactions and an action, each carrying a different responsibility. The generated reactions and the action are selectively generated for each network port depending on its type.

Next is a brief description of what each generated node does:

For each network output port (e.g., out):

1. Network Sender: Get the message from federate's (fed's) out port and send it to a destination federate
2. Network Output Control: If fed is not going to produce anything on out at the current tag, send a PORT_ABSENT instead. This reaction is triggered at all valid tags.

For each network input port (e.g., in):

3. Network Input Control: If fed's input port is neither present nor absent wait until a PORT_ABSENT message is received, or until the Safe-To-Assume-Absent (STAA) offset expires, or until it receives a Tag Advance Grant (TAG) with an equal or larger tag from the RTI. This reaction is triggered at all valid tags.
4. Network Receiver: Will be triggered by Action if fed receives a message from another federate on port in.

• Action (L): A physical or logical action that is triggered by federate.c when a message arrives for in from an upstream federate. This action will in turn trigger a Network Receiver.

Issue at hand

The listed generated network reactions are all marked unordered to prevent a deadlock from occurring, where a federate is blocked on receiving an input before it can produce an output or vice versa. Nonetheless, this might interfere with their objective.

Network Input Control and Network Receiver are not mutually exclusive, meaning that the execution of one does not interfere with the execution of the other. If a Network Input Control for a given port is executing, it means that the port is still neither present nor absent. This reaction waits until the status of the port has changed. If Network Receiver is executing, that means the port is present. Therefore, sooner or later, the Network Input Control will realize this and exit. Thus, both can remain unordered and execute in an arbitrary order.

The same is not true for Network Sender and Network Output Control. These two reactions have logic in them that is mutually exclusive at a given tag. If Network Output Control is executed at a tag and sends a PORT_ABSENT to the destination, under no circumstances should the corresponding Network Sender execute at the same tag. Otherwise, the destination will be informed that the port is absent at this tag, but then later will receive a value from the same federate for the same tag on the same port, violating the semantics of LF.

One way to enforce this exclusivity is for Network Output Control to have a priority that is lower than all reactions in fed that have out in their effect (thus, it will execute only after all those reactions, if triggered, are finished). This way, it can directly check the status of out, and if it is absent, it can be sure that the corresponding Network Sender will never be triggered at the current tag. I had assumed that declaring a source dependency on fed.out will achieve this. Therefore, the Network Output Control reaction in our example is defined as reaction(outputControlReactionTrigger) fed.out.

The issue seems to be that since the Network Output Control already has a trigger that is triggered at all valid tags, it appears that it can be executed sometimes without the status of fed.out becoming fully known (in other words, without executing all triggered reactions in fed that have out in their effect). This is true even if fed.out is a trigger (not a source) to this control reaction. My surprise is that why doesn't this mechanism interfere with the work of the Network Sender reaction? Imagine the following fed:

reactor Fed {
    input in:int;
    output out:int;
    reaction(in) -> out {= // First reaction. =}
    reaction(in) -> out {= // Second reaction. =}
}

Why doesn't the first reaction cause the Network Sender to send an output to the destination federate before the second reaction gets to execute? Is it because the Network Sender doesn't have another trigger?

Solution

Since the aforementioned solution does not work, two new approaches are proposed:

1. Put the Network Output Control directly after the last reaction in fed or any reactor instantiated within fed that produce a value on out.
2. Create a top-level Network Output Reactor alongside fed that contains both the Network Output Control reaction and the Network Sender reaction. This reactor has to be generated for each output port.

The downside of the first approach is that it might somewhat interfere with mutations, since deleting a nested reactor will also delete the network output control reaction within it.

For the second approach, there are a few design considerations. First, the C target does not have a generic type. This makes it harder to produce the Network Output Reactor as just one reactor class that adapts to each network output port using parameters. It might be easier to just produce a new reactor class for each network output port. Second, we currently selectively produce network control reactions for each federate. The same principle should have to carry to the network output reactor. Perhaps, the federate instance should keep a record of these generated network output reactor classes, or some sort of string name matching should be performed on the name of these network output reactors.

Footnotes

1. Here is the source code for the transformed program:

   target C;
   reactor Fed {
       input in:int;
       output out:int;
   }
   federated reactor {
       fed = new Fed();
       
       /************ Handling network output *************/
       input outputControlReactionTrigger:int;
       // @label Network Sender (unordered)
       reaction(fed.out) {=
           // Send data to destination
       =}
       // @label Network Output Control (unordered)
       reaction(outputControlReactionTrigger) fed.out {=
           // Send an absent to the destination
       =}
       
       /************ Handling network input *************/
       // @label Triggered by federate.c
       logical action in:int;
       input inputControlReactionTrigger:int;
       // @label Network Input Control (unordered)
       reaction(inputControlReactionTrigger) in {=
           // Wait until in becomes present or STP expires
       =}
       // @label Network Receiver (unordered)
       reaction(in) -> fed.in {=
           // Send the received message to fed
       =}
   }
   

   ↩

[lhstrh]

I've been advocating the use of generated NetworkReceiver and NetworkSender reactors all along (see page 111 of my thesis, for instance). As you know, we've encountered similar problems in the past but with inserted delays, which we also addressed by generating reactors instead of reactions. The "unordered reactions" actually have been polluting our compiler APIs pretty badly, and I would gladly get rid of them. I would:

• create "network receiver" and "network sender" reactor classes in exactly the same way we do this for generated delays (and generalize to avoid code duplication)
• name instances of generated reactors such that they:
  • do not clash with user-defined instances
  • specify which federate they are meant for

One thought I had was that it might make more sense to perform the required AST transformations on a per-federate basis rather than for the entire program (after which elements non-essential to a particular federate have to be filtered out), but this may require a more substantial redesign of the compiler than you might be willing to carry out.

[Soroosh129]

One thought I had was that it might make more sense to perform the required AST transformations on a per-federate basis rather than for the entire program (after which elements non-essential to a particular federate have to be filtered out), but this may require a more substantial redesign of the compiler than you might be willing to carry out.

Yes, this occurred to me as well. We might be able to even call doGenerate for individual federates if we perform the relevant AST transformation before that function is called. This can get us one step closer to what is described here.

[edwardalee]

On this:

The same is not true for Network Sender and Network Output Control. These two reactions have logic in them that is mutually exclusive at a given tag. If Network Output Control is executed at a tag and sends a PORT_ABSENT to the destination, under no circumstances should the corresponding Network Sender execute at the same tag. Otherwise, the destination will be informed that the port is absent at this tag, but then later will receive a value from the same federate for the same tag on the same port, violating the semantics of LF.

Actually, I think Network Sender and Network Output Control can be executed in any order. Neither should be executed before the status of Fed.out is known because they will both have levels greater than any reaction that writes to Fed.out. Therefore, when they are executed, if Fed.out has no output, then it is unambiguously absent. If Network Sender is invoked first, it will either send or not send depending on this status. If Network Output Control is invoked first, it should send a null message only if Fed.out is absent. So the order of invocation should not matter. The reason we are seeing the Network Output Control executing too early is because of the chainID bug. It is getting a chainID that does not overlap with that of the reactions that write to Fed.out, and hence the runtime erroneously thinks it can run in parallel with those. If we set all the chainIDs to 1, this bug should go away.

However, a potential for deadlock remains because of another problem. The Network Input Control reaction is being assigned level 0 even if it actually has a direct dependence on the Network Sender (i.e., there is a feedback loop, possible through other federates). The Network Sender is guaranteed to have a level bigger than 0. Hence, with all chainID = 1, we are assured that Network Input Control will execute first. It will block waiting for input that it will never receive because the Network Sender cannot run (it has a higher level).

The solution, I think, is that levels should be assigned to reactions before the federation gets broken into unconnected graphs. If we do that, then if Network Input Control has a direct dependence on Network Sender, it will be assured of having a higher level (and, once we fix the chainIDs, an overlapping chainID). Hence, it will not be able to execute until Network Sender has executed. If Network Sender does not produce an output, then we rely on Network Output Control to execute and send a null message. Network Output Control will also have a level less than that of Network Input Control and hence can execute (even its chainID does not overlap). There will be no harm in Network Output Control and Network Input Control running in parallel.

So the short answer:

1. Set all chainID = 1 until we figure out how to fix them.
2. Assign levels before breaking apart the federation with an AST transformation.

[Soroosh129]

Neither should be executed before the status of Fed.out is known because they will both have levels greater than any reaction that writes to Fed.out.

I agree. The original explanation meant to convey that if a Network Output Control reaction sends a port absent at a given tag, then the corresponding Network Sender reaction should never be triggered at that tag. However, that would be indirectly because of the dependency on Fed.out. Your explanation is a lot more direct and to the point.

The solution, I think, is that levels should be assigned to reactions before the federation gets broken into unconnected graphs.

That seems like a reasonable solution. There is an initial roadblock to this though. The Network Receiver and the Network Input Control reactions have dependencies on an action, not a port. Therefore, they will still be assigned level 0. This solution might require inserting these network reactions using the network input ports, and then after assigning levels, replacing these ports with the appropriate action.

[edwardalee]

Before the AST transformation, Network Receiver and Network Input Control will not exist, and neither will the action they depend on. This gets rather tricky, though. A level is assigned to an instance of a reaction, not the Reaction object in the AST. So I think there will need to be the following phases:

1. Using the original AST, construct an instance graph and assign levels.
2. Perform the AST, and construct a new instance graph.
3. For each node in the new instance graph that matches a node in the old one, inherit the level.
4. For each node in the new instance graph that has no level, assign it a level equal the minimum of its downstream nodes, and then increment the levels of all the downstream nodes by one.

This seems rather complex to me. Maybe there is a better way. Perhaps, for example, whenever the AST transformation breaks a connection, it makes a record of the original connection, and when the reaction graph is constructed, it somehow makes use of this annotation... Dunno.

Actually, here is a third idea: Instead of assigning level 0 to Network Input Control and Network Receiver, assign them level N, where N is the total number of reactions in the program. Anything downstream of them will get level N + 1, N + 2, etc. These levels are guaranteed to be higher than anything that would otherwise have been assigned to them, thereby ensuring that if there are any outputs that do not depend on inputs, those reactions will execute first. This requires careful thought about what will happen when multiple federates form a ring with multiple complex dependencies between them. Like this:

[Soroosh129]

An update on this:

We have changed the AST transformation that is done on federated programs. In short, the new AST transformation preserves the dependencies between federates. This new design will facilitate a level assignment to network reactions that more accurately reflects the structure of the federation as a whole. Previously, dependencies between federates were cut during the AST transformation, losing valuable information for level assignment.

For example, imagine the following program:

target C;
reactor Fed {
    input in:int;
    output out:int;
}
main reactor {
    fed1 = new Fed();
    fed2 = new Fed();
    
    fed1.out -> fed2.in;
    fed2.out -> fed1.in;
}

The new AST transformation will create the following program for a federated variant of the aforementioned program:

I will not go into details about the role of each reaction and action, since the original post here explains these. The thing to focus on here is the highlighted connections. The only change here is that these highlighted connections were previously not there. This would result in incorrect level assignments to the network reactions. Now, these connections are deliberately added during the AST transformation.

However, the burden is now on target language developers to account for these connections to make sure that they will not cause any issues in the user programs. Notice that for each highlighted connection, the source is in a different federate than the destination. It might be a dangerous situation, depending on how the target is designed, if a federate containing the source tries to directly write to the destination port that is not in the federate.

For the C target, we get around this issue by calling the removeDisconnectedNetworkPorts() API in GeneratorBase (maybe this API belongs to another class) after levels are assigned. This API removes all the references to the added destination triggers in the network (receiver/input control) reactions. This works because the C target resolves all dependencies during compile time. This functionality would, however, have to be replicated in C++, TS, and Rust targets at runtime if they would like to add/extend their support for federated programs.

[lhstrh]

Rather than performing AST transformations, assigning levels, and then (partially) rolling back said AST transformations (as well as how they are reflected ReactorInstance), we could also compute the extra dependencies for each federate implied by direct feedthrough from other federates it is connected to, and just add those edges directly to the reaction instance graph (where the levels are computed).

If we collect these extra edges, we can also pass them along to the code generators of targets that perform a topological sort at runtime. In any case, I think this approach will be the easiest to take for the TypeScript target, so we could take a stab at implementing it and then comparing notes with the current C code generator.

The steps would be:

• for each federate, compute a causality interface (i.e., determine which of the federate's outputs depend on which of the federate's inputs)
• determine for each federate which extra dependencies are implied by connections between federates (in this scenario, a federate's input becoming dependent on one or more of its outputs)
• for each reaction triggered by such input port, record a dependency on each reaction that produces values on it's corresponding output port(s)