CS 358. Concurrent Object-Oriented Programming
Spring 1996

The names given in the interface determine the visibility of declarations in a module. If a function name, for example, is declared in a module of type Channels, then it is private to the module since it does not appear in the interface.

Modules and the Executable Language

    when  pattern  do
             statement list
    end when

An example is a simple reactive process for a Channel (as defined above):

    ?M : String;
    when  Take_In(?M) do
               Deliver(?M);
    end when;

	Parallel
	  when
	||
	  when
	end;

	await
	  pattern => action;
	  pattern => action;
	end 

-----------------

  * The syntax for When is more something like: 
	when pattern do
	  statement list
	end when
  * Place holders ?m can only be defined in pattern,
  * reference are declared as k: var integer;

-----------

Examples

Example 1

TYPE Producer IS INTERFACE ACTION OUT Emit( n : Integer ); END Producer;
TYPE Consumer IS INTERFACE ACTION IN Source( n : Integer ); END
Consumer;

MODULE New_Producer( min : Integer ) RETURN Producer IS
   FUNCTION Compute( n : Integer ) RETURN Integer IS
      BEGIN RETURN n + 1; END FUNCTION Compute;
INITIAL
   Emit(min);
PARALLEL
   WHEN (?x IN Integer) Emit(?x) WHERE ?x < 20 DO 
      Emit( Compute( ?x ));
   END WHEN;
END MODULE New_Producer;

MODULE New_Consumer() RETURN Consumer IS
   FUNCTION Use( n : Integer ) IS BEGIN NULL; END FUNCTION;
PARALLEL
   WHEN (?y IN Integer) Source(?y) DO Use(?y); END WHEN;
END MODULE New_Consumer;

ARCHITECTURE ProdCon() IS
   Prod : Producer IS New_Producer(4);
   Cons : Consumer IS New_Consumer();
CONNECT
   (?n IN Integer)
   Prod.Emit(?n) TO Cons.Source(?n);
END ARCHITECTURE ProdCon;

Example 2

    k : var Integer;
    parallel 
        when (?M: String); Take_In(?M)  Where k.odd() then
                   Deliver_1(?M); k := k+1; 
        end when;
    ||
        when (?M: String); Take_In(?M)  Where k.even then
                   Deliver_2(?M); k := k+1; 
        end when;
    end parallel;

Some tricky issues. Can the second process start before the first finishes? Rapide decision is yes, for increased concurrency. But then what if we have two processes that are possible when k even and two when k odd? See below. Same occurs with code above is second invocation of one process definition can proceed before first completes.

    k : Integer;
    parallel 
        when (?M: String);  Take_In(?M)  Where k.odd() then
                   Deliver_1(?M); k := k+1; 
        end when;
    ||
        when (?M: String);  Take_In(?M)  Where k.odd() then
                   Deliver_1(?M); k := k+1; 
        end when;
    ||
        when (?M: String);  Take_In(?M)  Where k.even then
                   Deliver_2(?M); k := k+1; 
        end when;
    end parallel;

    j, k : Integer;
    
    when (?M: String); Take_In(?M) Where odd(k.minus(j)) then
               Deliver_1(?M);  ... ; j := j+1; k := k+1; 
    end when;

    when (?M: String); Take_In(?M) Where even(k.minus(j)) then
               Deliver_2(?M); ... ;  j := j+1; k := k+1; 
    end when;

    k : Integer;
    parallel 
        when (?M: String); Take_In(?M)  Where odd(k.minus(j)) then
                   Deliver_1(?M);  ... ; j := j+1; ... ; k := k+1; 
        end when;
    ||
        when (?M: String); Take_In(?M)  Where even(k.minus(j)) then
                   Deliver_2(?M);   ... ; j := j+1; ... ; k := k+1; 
        end when;
    end parallel;

Implementation Issues

Construcing the causality partial order

In the Fidge-Mattern algorithm, each of the n processes maintains an integer vector if length n. Intuitively, the ith component of this vector represents an approximation of the ith processes event counter. The FM algorith proceeds as follows:

• All vectors are initialized to (0,0, ..., 0)
• Process i increments the ith component of its vector before sending an event
• When a process sends an event, it includes the current value of its own vector
• When a process receives a vector, it updates its own vector to the component-wise maximum of the its own vector and the vector it receives

Rapide does not need to compare arbitrary events for causality. Since each module must declare its in and out actions, it is possible to analyze the set of actions that must be transmitted from one process to another. This may be combined with the fact that Rapide only requires the causal order between events arriving at a common receiver to make several optimizations possible. Some optimizations that have been explored are:

• Sparse vectors
• No need to maintain component i of j's vector if no communication path from i to j
• If there is no communication path from i to j, then all events from i or j to k will be independent. Therefore, we can eliminate the need for information to compare i and j vectors.
• If a communication architecture can be divided into two groups so that all communication from the first group to the second passes through a single "gateway" process, then the vectors may be simplified (as described in [MSV91]).

Maintaining "orderly observation"

The problem of arranging arrival of events so that each process sees events in a manner consisten with the global partial order is called "orderly observation."

There are several ways that this problem could be approached. One is to ensure that events arrive at each processor in a temporal order that is consistent with the partial order. Another is to provide some sort of rollback mechanism, in case a later event invalidates an earlier computation. (Potentially very expensive in a distributed environment, I think, since a rollback of one process may trigger rollbacks of others.) A third is for each event to contain enough information to determine whether there are causally earlier events.

The current Rapide implementation (as of the reference consulted) uses a global FIFO queue. Processes must synchronize with the queue when they generate and receive events. This sounds like a serious bottleneck, but the actual consequences of this have not been explored and compared with other approaches.

Possible term project: What changes in the pattern language would make it possible to simplify or eliminate this problem? For example, drop a "negation" operator and only look at "monotonic" patterns. (A pattern is "monotonic" is, whenver it matches a partial order, it matches all larger partial orders.)

Clocks

References

--------

Can we consider remote procedure call as a pair of events, a call event and return event? Maybe if we also have a "suspend" or blocking primitive. But should they really be implemented the same way? (See related discussion in the context of Actors.)

Compare to Linda's tuple space.

Remember: the meaning of a parallel program is a set of partial orders, not a single partial order. Therefore, diagnostics run on a single partial order cannot tell you the program is correct. You have to try all possible partial orders. Is it true that there are fewer partial orders than traces? Since the trace semantics blurs distinctions between partial orders, it might actually be algorithmically better for highly nondeterministic programs.