Re: A bunch of OWL-S difficulties

David Martin wrote:

>
> Daniel Elenius wrote:
>
>> Wouldn't a concurrent execution also include sequential execution as an
>> extreme case? If you execute things concurrently on a  single-cpu
>> computer, you switch back and forth, and it could be the case that one
>> process completes before the other one starts. The concurrency semantics
>> are simply non-commital on this point. At least in the OS case. And I
>> don't see why the case with distributed processes should be any
>> different. For example, if a composite process has a Split+Join with
>> processes A and B, would the user be doing a mistake if he did not
>> create a new thread and started both concurrently? I don't think so, I
>> think he should be allowed to execute A, wait for the return values,
>> then execute B, if he prefers. Separating the two cases seems to go into
>> implementation issues rather than process semantics.
>
>
> Yes, indeed I am sympathetic with your view, at least from the point 
> of view of what is the most widespread understanding of these 
> constructs, and from the point of view that it's easier to define and 
> implement non-concurrency than concurrency.  We discussed this in the 
> OWL-S telecon this morning, and I think everyone present was sympathetic.
>
> We discussed the following possible steps:
>
> (1) Clarifying Split and Split+Join, to indicate that they allow 
> concurrency, but do not necessarily insist upon it.
>
> (2) Redefining Unordered, to indicate that it actually insists upon 
> *non-concurrent* execution, but where any ordering is acceptable.  
> (Note that this would be a very significant change from the current 
> definition in the OWL-S technical overview.  But one or two users have 
> already adopted this proposed definition anyway.)


I made a short summary from various papers published about the use of 
the Unordered construct and its semantics. This is not meant to be a 
complete analysis but should give us an idea if and how the redefinition 
of Unordered would effect the existing work in this area.

I'll start with our work on using OWL-S in planning (see [1] and [2]) 
since that is the one I know best :) In both papers you will find the 
following sentence: "We also assume only a non-concurrent interpretation 
of Unordered" In SHOP2, there is no notion of concurrency so atomic 
processes are always assumed to be non-concurrent. However, the 
situation is different when you consider the composite processes in an 
Unordered construct. For example, suppose there is a composite process C 
which is defined as C = (:unordered A B) where A and B are both 
composite processes. In this case, the sub-processes of A and B can be 
interleaved arbitrarily. If A = (:sequence A1 A2) and B = (:sequence B1 
B2) then (A1 B1 A2 B2) would be one of the valid execution plans. There 
is no ordering relation between A and B yet it is not required to wait 
for one process to finish before the other one starts. If no 
interleaving between composite processes is required, there are other 
constructs in SHOP2 that lets you achieve this.

In [3], a Distributed OPErational (DOPE) semantics for various OWL-S 
composite constructs is given. Semantics are based on Petri nets and as 
far as I can tell, unordered construct is not used at all in this work. 
[4] also uses Petri nets for Web Service composition (but not in the 
context of OWL-S). In section 3.1 of this paper, there are definitions 
for two different operators 'parallel' and 'unordered' where former 
allows concurrency and the latter does not.

[5] provides OWL-S semantics based on the situation calculus and 
explains how to adapt Golog to use with OWL-S constructs. There is no 
specific discussion about the use of Unordered construct but Golog does 
not provide a non-concurrent unordered construct anyway. Therefore, 
Unordered would be modeled in ConGolog (concurrent version of Golog) as 
a concurrent construct.

[6] gives a concurrent execution semantics for DAML-S. In the related 
work section there is this sentence "Similarly, we do not describe the 
Unordered class explicitly because it is equivalent to the Concurrent 
class".

This quick survey shows that people have either assumed Unordered is 
same as Split and ignored it or adapted a non-concurrent semantics. As 
far as I can see, redefining Unordered with non-concurrent execution 
semantics would be ok for any of the approaches mentioned above. In this 
case, the Unordered construct would simply be shorthand for defining a 
Choice for all the possible Sequences.

>
> (3) (not directly related to 1 and 2) Eliminating Iterate, because we 
> do not think it will ever get used as it is defined.


Iterate construct is not mentioned specifically in any of the papers 
mentioned above. All the papers that deal with loop constructs 
concentrate on Repeat-While and Repeat-Until constructs. This is normal 
as the technical overview itself says: "The Iterate construct makes no 
assumption about how many iterations are made or when to initiate, 
terminate, or resume. The initiation, termination or maintenance 
condition could be specified with a whileCondition or an untilCondition 
as below". Golog provides a similar construct for non-deterministic 
iteration which is denoted by *. The semantics given in Golog for p* is 
"Execute p zero or more times". Then non-deterministic iteration is used 
to define While construct in Golog.

And technical overview explains one other reason for having Iterate 
construct "Another possible extension is the ability to define counters 
and use their values as termination conditions. This could be part of an 
extended process control and execution monitoring ontology". For this 
reason, it might be better to keep the definition of Iterate but at 
least relate Repeat constructs to Iterate, e.g. saying Repeat-While is 
subclass of Iterate.

>
> Note that these constructs were based on the work of a founding member 
> of the OWL-S Coalition, who is no longer present to advocate/defend 
> the current definitions.  If the current definitions are causing too 
> much confusion, we are open to changing them, perhaps as suggested 
> above.  On the other hand, we don't want to make a change that ignores 
> any widely accepted definitions, or that messes up anyone's work on 
> semantics or tools for OWL-S, so we have to be somewhat cautious about 
> this.
>
> I would welcome additional input from people have expertise in this area.

>
> Regards, David
>
>
Regards,
Evren

[1] HTN planning for web service composition using SHOP2, Evren Sirin, 
Bijan Parsia, Dan Wu, James Hendler, and Dana Nau. Journal of Web 
Semantics, 2004, In press.

[2] Automating DAML-S web services composition using SHOP2, Dan Wu, 
Bijan Parsia, Evren Sirin, James Hendler, and Dana Nau. In Proceedings 
of 2nd International Semantic Web Conference (ISWC2003), Sanibel Island, 
Florida, October 2003.

[3] Simulation verification and automated composition of web services, 
S. Narayanan, S. McIlraith. In Proceedings of the Eleventh International 
WWW Conference, Honolulu, Hawaii, 2002.

[4] A Petri Net-based Model for Web Service Composition, R. Hamadi, B. 
Benatallah. In Proc. of the Fourteenth Australasian Database Conference 
(ADC'03), Feb. 2003

[5] Adapting Golog for composition of semantic web services, S. 
McIlraith, T. Son. In Proceedings of the Eighth International Conference 
on Knowledge Representation and Reasoning, Toulouse, France, 2002.

[6] Concurrent Execution Semantics for DAML-S with Subtypes, Anupriya 
Ankolekar, Frank Huch, Katia Sycara. The First International Semantic 
Web Conference (ISWC), Sardinia (Italy), June, 2002.

Received on Monday, 27 September 2004 23:37:13 UTC