Issue 7222: Activity Diagrams: Relax Traverse-to-Completion semantics (uml2-superstructure-ftf) Source: (, ) Nature: Uncategorized Issue Severity: Summary: In my interpretation of the current semantics description of UML activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I have identified some rather unpleasant properties of the current traverse-to-completion semantics. The full discussion together with examples can be found in the attached .pdf, the short of it is: *) the current semantics does not prevent deadlocks (as it is supposed to do) *) it rather induces deadlocks even in simple examples (e.g. examples in the UML spec are wrong) *) it makes for a very complex evaluation and introduces unnecessary synchronization in the (basically asynchronous) notation of Activiy Diagrams. I therefore propose to relax the semantics of token flow by dropping the constraint that every Action has to accept all tokens for all its input pins at once. MergeNodes should als be able to buffer tokens until their conditions are satisfied. This is a more natural way of interpreting ADs. Resolution: This is a duplicate of issue 7221 Revised Text: Actions taken: December 2, 2004: closed issue Discussion: End of Annotations:===== Date: Mon, 5 Apr 2004 11:14:56 +0200 From: Jan Hendrik Hausmann X-Mailer: The Bat! (v1.62r) Educational Reply-To: Jan Hendrik Hausmann Organization: University of Paderborn To: issues@omg.org CC: uml2-superstructure-ftf@omg.org Subject: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics X-UNI-PB_FAK-EIM-MailScanner-Information: Please see http://imap.uni-paderborn.de for details X-UNI-PB_FAK-EIM-MailScanner: Found to be clean X-UNI-PB_FAK-EIM-MailScanner-SpamCheck: not spam (whitelisted), SpamAssassin (score=0.803, required 4, MIME_MISSING_BOUNDARY 0.80) X-MailScanner-From: hausmann@upb.de In my interpretation of the current semantics description of UML activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I have identified some rather unpleasant properties of the current traverse-to-completion semantics. The full discussion together with examples can be found in the attached .pdf, the short of it is: *) the current semantics does not prevent deadlocks (as it is supposed to do) *) it rather induces deadlocks even in simple examples (e.g. examples in the UML spec are wrong) *) it makes for a very complex evaluation and introduces unnecessary synchronization in the (basically asynchronous) notation of Activiy Diagrams. I therefore propose to relax the semantics of token flow by dropping the constraint that every Action has to accept all tokens for all its input pins at once. MergeNodes should als be able to buffer tokens until their conditions are satisfied. This is a more natural way of interpreting ADs. cheers Jan Hendrik Hausmann -- oooooooooooooooooooooooooooooooooooooooooooooooo o Jan Hendrik Hausmann | Room E4.301 o o University of Paderborn | 05251 60-3959 o o AG Database and Information Systems| hausmann@upb.de o ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo Why ttc does not work.pdf From: "Thomas Weigert" To: "Jan Hendrik Hausmann" , Cc: Subject: RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Date: Tue, 6 Apr 2004 07:05:10 -0500 X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0) Importance: Normal Dear all, is anybody going to address the concerns raised in the contribution by Mr. Hausmann? I believe that this carefully worked out issue warrants further discussion. All the best, Th. > -----Original Message----- > From: Jan Hendrik Hausmann [mailto:hausmann@upb.de] > Sent: Monday, April 05, 2004 4:15 AM > To: issues@omg.org > Cc: uml2-superstructure-ftf@omg.org > Subject: UML 2 Superstructure/Activity Diagrams: Relax > Traverse-to-Completion semantics > > > > In my interpretation of the current semantics description of UML > activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I > have identified some rather unpleasant properties of the current > traverse-to-completion semantics. The full discussion together with > examples can be found in the attached .pdf, the short of it is: > > *) the current semantics does not prevent deadlocks (as it is > supposed to do) > > *) it rather induces deadlocks even in simple examples (e.g. examples > in the UML spec are wrong) > > *) it makes for a very complex evaluation and introduces unnecessary > synchronization in the (basically asynchronous) notation of Activiy > Diagrams. > > I therefore propose to relax the semantics of token flow by dropping > the constraint that every Action has to accept all tokens for all its > input pins at once. MergeNodes should als be able to buffer tokens > until their conditions are satisfied. This is a more natural way of > interpreting ADs. > To: "Thomas Weigert" Cc: conrad.bock@nist.gov, "Jan Hendrik Hausmann" , uml2-superstructure-ftf@omg.org Subject: RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics X-Mailer: Lotus Notes Release 6.0.2CF1 June 9, 2003 From: Branislav Selic Date: Tue, 6 Apr 2004 10:21:52 -0400 X-MIMETrack: Serialize by Router on D25ML05/25/M/IBM(Release 6.0.2CF1|June 9, 2003) at 04/06/2004 10:21:56, Serialize complete at 04/06/2004 10:21:56 Thomas, The issues are recorded in the official issues database -- albeit it was registered long past the comments deadline (Nov. 7, 2003). However, as has been our practice to date, we will review and respond to all issues received until a future date as yet not fixed. So, this issue will get handled in due course. I must admit that I was surprised to read the comment that it is assumed that the current semantics is "intended to prevent deadlocks". I don't recall anything like that being a requirement or a feature. Perhaps I am misunderstanding the issue. I was also surprised by the comment that activities are "basically" an asynchronous formalism. This is debateable to say the least. Cheers, Bran "Thomas Weigert" 04/06/2004 08:05 AM To "Jan Hendrik Hausmann" , cc Subject RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Dear all, is anybody going to address the concerns raised in the contribution by Mr. Hausmann? I believe that this carefully worked out issue warrants further discussion. All the best, Th. > -----Original Message----- > From: Jan Hendrik Hausmann [mailto:hausmann@upb.de] > Sent: Monday, April 05, 2004 4:15 AM > To: issues@omg.org > Cc: uml2-superstructure-ftf@omg.org > Subject: UML 2 Superstructure/Activity Diagrams: Relax > Traverse-to-Completion semantics > > > > In my interpretation of the current semantics description of UML > activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I > have identified some rather unpleasant properties of the current > traverse-to-completion semantics. The full discussion together with > examples can be found in the attached .pdf, the short of it is: > > *) the current semantics does not prevent deadlocks (as it is > supposed to do) > > *) it rather induces deadlocks even in simple examples (e.g. examples > in the UML spec are wrong) > > *) it makes for a very complex evaluation and introduces unnecessary > synchronization in the (basically asynchronous) notation of Activiy > Diagrams. > > I therefore propose to relax the semantics of token flow by dropping > the constraint that every Action has to accept all tokens for all its > input pins at once. MergeNodes should als be able to buffer tokens > until their conditions are satisfied. This is a more natural way of > interpreting ADs. > From: "Thomas Weigert" To: "Branislav Selic" Cc: , "Jan Hendrik Hausmann" , Subject: RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Date: Tue, 6 Apr 2004 09:29:37 -0500 X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0) Importance: Normal The issue alleges that i. the current semantics is inferior to standard petri-net semantics in dealing with concurrency pathologies and ii. is unintuitive as evidenced by that examples in the specification exhibit such pathologies. Synchronicity makes things worse in this case. The submitter of the issue, I believe, suggests that it would be better to rely on more conventional interpretation of token flow to both get the benefit of research that has already been conducted and avoid counterintuitive interpretations. Given the seriousness of the complaint I believe it warrants investigation. Th. -----Original Message----- From: Branislav Selic [mailto:bselic@ca.ibm.com] Sent: Tuesday, April 06, 2004 9:22 AM To: Thomas Weigert Cc: conrad.bock@nist.gov; Jan Hendrik Hausmann; uml2-superstructure-ftf@omg.org Subject: RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Thomas, The issues are recorded in the official issues database -- albeit it was registered long past the comments deadline (Nov. 7, 2003). However, as has been our practice to date, we will review and respond to all issues received until a future date as yet not fixed. So, this issue will get handled in due course. I must admit that I was surprised to read the comment that it is assumed that the current semantics is "intended to prevent deadlocks". I don't recall anything like that being a requirement or a feature. Perhaps I am misunderstanding the issue. I was also surprised by the comment that activities are "basically" an asynchronous formalism. This is debateable to say the least. Cheers, Bran "Thomas Weigert" 04/06/2004 08:05 AM To "Jan Hendrik Hausmann" , cc Subject RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Dear all, is anybody going to address the concerns raised in the contribution by Mr. Hausmann? I believe that this carefully worked out issue warrants further discussion. All the best, Th. > -----Original Message----- > From: Jan Hendrik Hausmann [mailto:hausmann@upb.de] > Sent: Monday, April 05, 2004 4:15 AM > To: issues@omg.org > Cc: uml2-superstructure-ftf@omg.org > Subject: UML 2 Superstructure/Activity Diagrams: Relax > Traverse-to-Completion semantics > > > > In my interpretation of the current semantics description of UML > activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I > have identified some rather unpleasant properties of the current > traverse-to-completion semantics. The full discussion together with > examples can be found in the attached .pdf, the short of it is: > > *) the current semantics does not prevent deadlocks (as it is > supposed to do) > > *) it rather induces deadlocks even in simple examples (e.g. examples > in the UML spec are wrong) > > *) it makes for a very complex evaluation and introduces unnecessary > synchronization in the (basically asynchronous) notation of Activiy > Diagrams. > > I therefore propose to relax the semantics of token flow by dropping > the constraint that every Action has to accept all tokens for all its > input pins at once. MergeNodes should als be able to buffer tokens > until their conditions are satisfied. This is a more natural way of > interpreting ADs. > Date: Tue, 06 Apr 2004 18:01:05 +0100 From: Guus Ramackers Organization: Oracle User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en, en-us To: Thomas Weigert CC: Branislav Selic , conrad.bock@nist.gov, Jan Hendrik Hausmann , uml2-superstructure-ftf@omg.org Subject: Re: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Thomas, > i. the current semantics is inferior to standard petri-net semantics The proposal seems to move away from petri net semantics in that it is a fundamental aspect that the transition takes all its token when it fires. Also, the statement > *) the current semantics does not prevent deadlocks (as it is supposed to do) Is somewhat confusin. It has never been a goal to develop a specification that would never let the modeler develop a deadlock situation. Deadlocks can occur in SM, Interaction or Activities - only careful modeling (and qualitative analysis) can prevent them. Thanks, guus Thomas Weigert wrote: The issue alleges that i. the current semantics is inferior to standard petri-net semantics in dealing with concurrency pathologies and ii. is unintuitive as evidenced by that examples in the specification exhibit such pathologies. Synchronicity makes things worse in this case. The submitter of the issue, I believe, suggests that it would be better to rely on more conventional interpretation of token flow to both get the benefit of research that has already been conducted and avoid counterintuitive interpretations. Given the seriousness of the complaint I believe it warrants investigation. Th. -----Original Message----- From: Branislav Selic [mailto:bselic@ca.ibm.com] Sent: Tuesday, April 06, 2004 9:22 AM To: Thomas Weigert Cc: conrad.bock@nist.gov; Jan Hendrik Hausmann; uml2-superstructure-ftf@omg.org Subject: RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Thomas, The issues are recorded in the official issues database -- albeit it was registered long past the comments deadline (Nov. 7, 2003). However, as has been our practice to date, we will review and respond to all issues received until a future date as yet not fixed. So, this issue will get handled in due course. I must admit that I was surprised to read the comment that it is assumed that the current semantics is "intended to prevent deadlocks". I don't recall anything like that being a requirement or a feature. Perhaps I am misunderstanding the issue. I was also surprised by the comment that activities are "basically" an asynchronous formalism. This is debateable to say the least. Cheers, Bran "Thomas Weigert" 04/06/2004 08:05 AM To "Jan Hendrik Hausmann" , cc Subject RE: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics Dear all, is anybody going to address the concerns raised in the contribution by Mr. Hausmann? I believe that this carefully worked out issue warrants further discussion. All the best, Th. > -----Original Message----- > From: Jan Hendrik Hausmann [mailto:hausmann@upb.de] > Sent: Monday, April 05, 2004 4:15 AM > To: issues@omg.org > Cc: uml2-superstructure-ftf@omg.org > Subject: UML 2 Superstructure/Activity Diagrams: Relax > Traverse-to-Completion semantics > > > > In my interpretation of the current semantics description of UML > activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I > have identified some rather unpleasant properties of the current > traverse-to-completion semantics. The full discussion together with > examples can be found in the attached .pdf, the short of it is: > > *) the current semantics does not prevent deadlocks (as it is > supposed to do) > > *) it rather induces deadlocks even in simple examples (e.g. examples > in the UML spec are wrong) > > *) it makes for a very complex evaluation and introduces unnecessary > synchronization in the (basically asynchronous) notation of Activiy > Diagrams. > > I therefore propose to relax the semantics of token flow by dropping > the constraint that every Action has to accept all tokens for all its > input pins at once. MergeNodes should als be able to buffer tokens > until their conditions are satisfied. This is a more natural way of > interpreting ADs. > -- _____________________________________________________________ Guus Ramackers Product Manager UML and Web Services Tools Oracle JDeveloper Tools group 520 Oracle Parkway, TVP Reading RG6 1RA, UK work: +44-(0)1189-245101 e-mail: guus.ramackers@oracle.com fax: +44-(0)1189-245148 Date: Wed, 7 Apr 2004 09:00:45 +0200 From: Jan Hendrik Hausmann X-Mailer: The Bat! (v1.62r) Educational Reply-To: Jan Hendrik Hausmann Organization: University of Paderborn To: Guus Ramackers CC: Thomas Weigert , Branislav Selic , , Subject: Re[2]: UML 2 Superstructure/Activity Diagrams: Relax Traverse-to-Completion semantics X-UNI-PB_FAK-EIM-MailScanner-Information: Please see http://imap.uni-paderborn.de for details X-UNI-PB_FAK-EIM-MailScanner: Found to be clean X-UNI-PB_FAK-EIM-MailScanner-SpamCheck: not spam (whitelisted), SpamAssassin (score=0, required 4) X-MailScanner-From: hausmann@upb.de X-MailScanner-To: Guus.Ramackers@oracle.com, bselic@ca.ibm.com, conrad.bock@nist.gov, hausmann@upb.de, thomas.weigert@motorola.com, uml2-superstructure-ftf@omg.org At Dienstag, 6. April 2004 Guus wrote: GR> The proposal seems to move away from petri net semantics in that it is a GR> fundamental aspect that the transition takes all its token when it fires. My particular complaint is that a "transition" is no longer a (possibly branching) path from one node that holds a token to one (or more) nodes that accept that token, but that the current semantics enforce a synchronization over multiple such paths if the receiving object has multiple input pins. Tokens traversing a complex path in one step are quite fine. My proposal is only to allow for an incremental acceptance of needed input data (on both ActionNodes and MergeNodes). GR> It has never been a goal to develop a specification GR> that would never let the modeler develop a deadlock GR> situation. It might not have been an overall goal, but the "accept all input tokens at once" semantics of Actions are described in the spec (Draft Adopted Spec, p.281, 12.3.1 Action / Semantics): "The flow prerequisite is satisfied when all of the input pins are offered tokens and accept them all at once, precluding them from being consumed by any other actions. This ensures that multiple action executions competing for tokens do not accept only some of the tokens they need to begin, causing deadlock as each execution waits for tokens that are already taken by others." A similar statement can be found in Conrad Bock's article series in the Journal of Object Technology (Part 4 in JOT Jan/Feb 04). So at least the detail which I would like to drop is explicitly introduced to prevent deadlocks. GR> Deadlocks can occur in SM, Interaction or Activities - only GR> careful modeling (and qualitative analysis) can prevent them. I agree! This is why I find this particular feature of the current semantics not useful (and possibly harmful as pointed out by the examples). cheers jhh -- oooooooooooooooooooooooooooooooooooooooooooooooo o Jan Hendrik Hausmann | Room E4.301 o o University of Paderborn | 05251 60-3959 o o AG Database and Information Systems| hausmann@upb.de o ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo OMG Issue No: 7221 Title: Activity Diagrams: Relax Traverse-to-Completion semantics Source: University of Paderborn (Mr. Jan Hendrik Hausmann, hausmann@upb.de) Summary: In my interpretation of the current semantics description of UML activity diagrams (Superstructure, Final Adopted Spec, ptc/03-08-02) I have identified some rather unpleasant properties of the current traverse-to-completion semantics. The full discussion together with examples can be found in the attached .pdf, the short of it is: *) the current semantics does not prevent deadlocks (as it is supposed to do) *) it rather induces deadlocks even in simple examples (e.g. examples in the UML spec are wrong) *) it makes for a very complex evaluation and introduces unnecessary synchronization in the (basically asynchronous) notation of Activiy Diagrams. I therefore propose to relax the semantics of token flow by dropping the constraint that every Action has to accept all tokens for all its input pins at once. MergeNodes should als be able to buffer tokens until their conditions are satisfied. This is a more natural way of interpreting ADs. Discussion: This issue is resolved by the changes proposed for issue 6512. The text below is discussion only. > *) the current semantics does not prevent deadlocks (as it is supposed to do) It prevents them to the same extent that Petri nets does. Going beyond this is too much for an FTF to attempt, and perhaps even for UML in general. The filer provided the following example, adapted from Figure 14 of http://www.jot.fm/issues/issue_2004_01/column3: Action input pins require all inputs to be available before accepting them at any input. Since the central buffer nodes are separated from the input pins by another layer of object nodes, a drill can be accepted as input without an extension cord and vice versa. This is similar to a Petri net like this: The above will deadlock in the same way as the adapted carpenter example because the transition rule can't "penetrate" the wall of unshared places between the transitions and the shared places on the left. The action input rule provides the same level of deadlock protection as the transition rule for Petri net. > *) it rather induces deadlocks even in simple examples (e.g. examples in the UML spec are wrong) The examples given by the filer are Figure 212 of the UML 2 FAS and Figure 2 of http://csdl.computer.org/comp/mags/so/2003/05/s5033abs.htm: Neither example above exhibits deadlock in the sense of two actions mutually locking each other's inputs, but under the current fork semantics the above can prevent actions from executing as they should. Forks will not accept a token unless all outgoing edge accept it, and the outgoing edges cannot accept it unless there is an object node somewhere downstream that accepts it. In the top figure above, if the priority is not equal to 1, then there is no object node to accept the token, so the fork cannot accept any at all, even to invoke Fix Problem. In the lower figure, the fork before Get Balance can have the same problem, because the action input rule will not allow Set Balance to accept an input until the addition behavior is done, which prevents Get Balance from starting, which prevents the addition from starting. These problems are resolved by issue 6512. > *) it makes for a very complex evaluation The evaluation of join nodes and actions only need to wait for offers on all their incoming edges. This is not a complex evaluation. In other discussion, the filer cited an implementation that searched backwards from joins and actions an arbitrary distance to find an offerring node, but this is not a required implementation. One that propagates offers forward would not need to perform a search. > and introduces unnecessary synchronization in the (basically asynchronous) notation of Activiy Diagrams. This is addressed by issue 6512. > I therefore propose to relax the semantics of token flow by dropping the constraint that every Action has to accept all tokens for all its input pins at once. This would increase the chance of deadlock. > MergeNodes should als be able to buffer tokens until their conditions are satisfied. This is a more natural way of interpreting ADs. Presumably the filer meant JoinNode rather than MergeNode. The suggestion would prevent joins from competing for tokens properly, because they could accept tokens without being able to pass them along the outgoing edges, even when the token has an alternative path to an object node. Disposition: Resolved What colour is a chameleon on a mirror?