Unordered construct

This message is to clarify the issues about Unordered construct and 
explain the decision made at the last OWL-S telecon. It is clear that 
Unordered should imply non-concurrency between atomic processes but 
there are at least two different ways to execute the composite 
processes. Let me explain this using the example from the technical 
overview document: Suppose a, b, c, and d are atomic processes, and X, 
Y, and Z are composite processes:

X = (Sequence a b)
Y = (Sequence c d)
Z = (Unordered X Y)

First interpretation of Unordered (interleaved execution): There is no 
order on the execution of X and Y and their execution can even be 
interleaved as long as individual atomic processes are executed 
non-concurrently. Overview document explains this as: "Z translates to 
the following partial ordering: {(a;b), (c;d)} where ';' means 'executes 
before', and the possible execution sequences (total orders) include 
{(a;b;c;d), (a;c;b;d), (a;c;d;b), (c;d;a;b), (c;a;d;b), (c;a;b;d)}"

Second interpretation of Unordered (no interleaving): Unordered does not 
imply any ordering on X and Y but the execution of one should not start 
before the execution of other ends. Therefore, there are only two 
possible execution sequences {(a;b;c;d), (c;d;a;b)}. This interpretation 
of Unordered is sometimes called as "Arbitrary Sequence".

Description of Unordered construct in OWL-S 1.0 was closer to the first 
interpretation but for OWL-S 1.1 it is now being considered to adopt the 
second interpretation. There are couple of reasons for this change: 1) 
Sometimes it is more intuitive to think of composite processes as a 
single unit and it is required to put constraint on the composite 
process as a whole (as in the example Naveen pointed out) 2) 
Interleaving is already permitted in Split+Join and if interleaving 
between composite processes is allowed then in most cases concurrency 
between atomic processes can also be allowed.

We still believe that both interpretations of Unordered are useful but 
unless there are objections (though I know Bijan has :) the definition 
of Unordered will be changed in accordance to the second interpretation.

Please send your comments to the mailing list if you have objections to 
this change.

Regards,
Evren

Received on Sunday, 10 October 2004 23:09:05 UTC