Re: Unordered construct

On Oct 10, 2004, at 7:08 PM, Evren Sirin wrote:

> 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.

Hmpfh. It's not at all clear. I agree that having both unordered and 
split-join where they are essentially synonymous only with unordered 
winning the name beauty contest isn't helpful. And it's nice to break 
them along the perhaps concurrent/absolutely non-concurrent (for some 
bits) line, and to allow interleaving (which you have to for atomics, 
if you're going to forbid concurrency). But there seems to be a *lot* 
of middle ground and it's unclear why the particular unordered is 
selected.

> 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)

Except this makes composite processes feel ``more real", and less like 
the way they've been conceived all along...as golog like macroy control 
constructs or HTN methods.

> 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.

As we discussed, this is, in fact, not true of SHOP. SHOP does not 
allow concurrent execution of operators, but does permit interleaving 
operators from different methods.

The rejoiner is that Split+Join allows this! Just don't parallelize the 
atomics. To this I say, Ugh.

By this logic, we should kill unordered. In fact, that's my proposal, 
kill unordered. If you can't handle concurrency, go ahead,  don't 
handle it. Split+Join doesn't *require* concurrency, it just allows it.

(I kinda like it. Prune, folks, prune!)

> 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.

Evren and I discussed some ways to contrain Split+Join (or an unordered 
that allowed interleving). He thinks it's easy, so I'll leave it to him 
to explicate. I just died on the lack of daml:item.

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

As you command.

Cheers,
Bijan Parsia.

Received on Monday, 11 October 2004 05:25:47 UTC