A Probabilistic Merger for Reo

Reo is a coordination language or component-based systems which is based on the idea of plugging communication channels together using nodes. The channels in Reo are user-defined and can implement virtually any kind of communication or synchronization. What is typically fixed though in Reo is the notion of nodes. Nodes merge incoming data items and replicate them to all outgoing channel ends. The merging is technically more interesting and challenging, which is why in some papers, this behavior is modeled by a ternary component called a Merger, which is often visualized like this:

This component reads data items from a or b and writes them to c. If there is data available at both a and b, the choice for one of them is nondeterministic. If no additional fairness assumptions are made, the model really does not say anything about the policy for choosing between a and b.

The semantics of such a merger component can be formalized using Reo automata. In these automata, transitions are labeled by pairs of guards and dataflow actions, written as "g|f" where g is a guard and f is a dataflow action. The Reo automaton for the merger component is shown below on the left. It consists of only one state and two transitions. The label "ac|ac" is read as: if there are I/O requests on a and c, then there can be dataflow at a and c (analogously for "bc|bc").

The interesting thing about Reo automata is that they can also directly (without encodings) express context-dependent behavior. An example is the automaton for a PriorityMerger shown on the right. The "ac|ac"-transition is the same as in the nondeterministic merger but the transition for choosing b contains an additional constraint in the guard: a (that is the negation of a). This informally means that dataflow from b to c can occur only if there is no data item at a available. Thus, the choice between a and b is no longer nondetermistitic but prioritized to a. So far, nothing new. Ok, let's take a look at the following automaton.

This automaton is not a Reo automaton anymore, because its transitions form discrete probability distributions. This is very similar to probabilistic constraint automata. If you take a look at the two states on the right, they have essentially the behavior of an a-PriorityMerger and a b-PriorityMerger. So, depending on whether the autmaton is in the upper or the lower state, it favor either a or b. The interesting part is that whether it favors a or b is now random. From the initial state, there is one silent step where an initial random decision for either a or b is made (a is chosen with a probability p). Whenever data is available at both a and b, the automaton favors one of them as determined by its current state. Additionally, a coin is tossed to decide whether a or b should be favored the next time. Thus, we have modeled a merger where the choice for a or b is random. What is important here is that we still need context information, i.e. whether there are data items available or not. This is most likely also the reason why this notion of probabilistic mergers was not considered in probabilistic constraint automata (which cannot directly express context information).