Removal of blocking unordered reactions from federated programs

[lhstrh]

The current federated architecture (also see #608) employs blocking unordered reactions dubbed "input control reactions" to allow for cyclic connection topologies in federations. While this approach clearly works, it requires the use of many dedicated threads, most of which are simply waiting or inactive most of the time. There are concerns about scalability of the approach, as well as a perceived difficulty to understand the current state of a federate, which is mainly a concern for when debugging. @arengarajan99 and I have been discussing ways of doing this differently. Here are some observations made during our conversation:

• Input control reactions are meant to temporarily prevent reactions that have been triggered from executing in case they are causally influenced by network input ports the value of which at the current time is not yet known. Such an upstream network port becoming present can trigger new reactions that have precedence over reactions that have already been triggered; the already-triggered reactions thus have to be put on hold.
• At compile time, it can be statically determined for each reaction which upstream network ports causally influences it. This information can easily be carried over in the generated code.
• For each reaction, when it gets triggered, it can be checked whether all upstream network ports are known. If they are not known, the reaction can simply be set aside in a set of pending reactions.
• When a new network input arrives, the port can be marked as "known" and the list of pending reactions iterated over to see whether there are any reactions that can be moved to the reaction queue.
• This set of pending reactions is likely very small because only reactions that are in the current "frontier" of triggered reactions end up there.
• The number of ports that exert causal influence over any given reaction is likely also small.
• An additional analysis can be done to reduce the number of network ports to check for any given reaction. The intuition here is that if a reaction can only be triggered by other reactions that are blocked, then their upstream network ports must already be known by the time they are allowed to execute and trigger said reaction. We need a proof for this, but it's not clear that such optimization is actually necessary.

[edwardalee]

This seems reasonable. The statement "the reaction can simply be set aside in a set of pending reactions" may be a little is misleading, however, because we have be careful to not confuse "set aside" with completion of the reaction. So it may not be quite so simple. The system has to behave as if the reaction takes a long time to execute, so that any dependent reactions are also blocked.

[lhstrh]

Yes, depending reactions will also be blocked. Causal influence of network ports is transitive, so any reaction that is causally influenced by a reaction that is side aside will itself also be be set aside. By "set aside" I just mean stored in a "pending set," to be pushed onto the reaction queue whenever all upstream network ports have their status known.

[arengarajan99]

It appears like the overarching problem with this solution has to do with determining whether we have something ready on a port before we can propagate a port status to downstream dependencies. As it stands, we accomplish this using busy waiting on reading from a port using sockets. I have a possible solution to this that doesn't require additional threads to block, but requires more centralized control of the entire socket. Rather than reading synchronously from a socket, we can set a connection to be async using fcntl.

(Note: The below explanation also works on Ubuntu using Epoll with similar implementations)
On MacOS, you are able to asynchronously monitor sockets through the use of KQueue, or Kernel Queue Service where you specify a socket as async and attach its network to a KEvent that will run in the background without needing an additional thread. Though this won't interrupt your current thread, you can probe the KQueue at anytime to see any events ready to be processed. In the case of sockets, we can setup KEvents to asynchronously read socket packets into a Queue, and we can probe said queue at any good time to pull socket events without having to busy wait on our current thread.

The way this may work is to start the federate by setting up a KQueue and KEvents for the federates socket to listen on both input (and possibly output) ports. We will start by running any events that are not blocked by port statuses. Once we exhaust the queue, we can read off of the KQueue to see if we have any network messages to process. Once processed, depending on whether its a read or write, you process said event. If its an input port indicating its status (absent or present w/ a value), we can set a global value for the port being ready and go through a waiting reaction queue to see if all its global value for input ports are set before enqueuing said reaction onto the reaction queue. Depending on what test cases fail, we would need to tweak when to poll the KQueue.

Per my discussion with Edward, this seems like a middle ground solution between busy waiting and polling each individual port separately. Rather than polling all ports, this simply populates a queue that automatically loads with events to be processed (seems like the read syscall simply waits for the queue to populate with an event corresponding to what its reading before unblocking). We would need to find an optimal time to read (and whether we can preempt the current thread via a signaled interrupt when there is something on the kernel queue) This will need some work to put together, but it seems like it's worth looking into.

[arengarajan99]

Here is an example of a simple server in MacOS that utilizes KQueues as an example: https://gist.github.com/josephg/6c078a241b0e9e538ac04ef28be6e787

[arengarajan99]

I need to get more familiar with how writing would work since we rely on synchronous writes.

[edwardalee]

To be clear, the current solution does not busy wait. It sets up a thread that blocks on socket activity.

[petervdonovan]

For each reaction, when it gets triggered, it can be checked whether all upstream network ports are known. If they are not known, the reaction can simply be set aside in a set of pending reactions.

This seems like basically the same idea as chain ID. If both are implemented, the two might use much of the same code.

[lhstrh]

For each reaction, when it gets triggered, it can be checked whether all upstream network ports are known. If they are not known, the reaction can simply be set aside in a set of pending reactions.

This seems like basically the same idea as chain ID. If both are implemented, the two might use much of the same code.

That's a brilliant observation, @petervdonovan! I like this idea.