W3C home > Mailing lists > Public > public-sws-ig@w3.org > October 2004

Re: Unordered construct

From: Evren Sirin <evren@cs.umd.edu>
Date: Mon, 11 Oct 2004 23:57:35 -0400
Message-ID: <416B562F.30903@cs.umd.edu>
To: Bijan Parsia <bparsia@isr.umd.edu>
CC: "'public-sws-ig'" <public-sws-ig@w3.org>

Bijan Parsia wrote:

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


Yes, but it seems that sometimes you want to *forbid* concurrency (or 
even interleaving) but do not want to impose any ordering. Naveen's 
Unordered example was such a case and that is what started the 
discussion about revising the definition of Unordered.

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


Yes, we discussed several different ways to define these control 
constructs. The idea was to use temporal constraints to specify how 
subcomponents occur with respect to each other, e.g. say that these 
subcomponents can or cannot occur in overlapping intervals. This seemed 
easy since Process class was defined to be subclass of Interval class 
from time ontology (which I now realize is not the case in 1.1 anymore). 
But then it turned out that specifying these restrictions is not that 
easy, especially when you consider that each subcomponent may have other 
subcomponents. I don't anymore think it is easy :) There is of course 
the obvious solution: Defining new constructs for different kind of 
interpretations so we would have Spit+Join, Interleaving Unordered and 
non-interleaving Unordered. (Don't delete, add more :)

Evren

>
>> Please send your comments to the mailing list if you have objections 
>> to this change.
>
>
> As you command.
>
> Cheers,
> Bijan Parsia.
>
>
>
>
Received on Tuesday, 12 October 2004 03:58:13 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 16 March 2008 00:10:58 GMT