24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?1 When are two Workflows the same? Polo Regionale di Como of the Politecnico. - презентация

1 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?1 When are two Workflows the same? Polo Regionale di Como of the Politecnico di Milano Workgroup and Workflow Management Systems Babushkin Nikita, Grulenko Victoria - December 19th,

2 Introduction Issues: Large number of languages Lack of standarts Variability Multiple models of Wf in one modeling language 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?2

3 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?3 Silent steps Workflow behaves as a reactive system There are two options: System makes an offer to the environment Environment provides the choice of activity and additional input information System makes decision by itself This steps are known as silent steps

4 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?4 Transition tree To gain the high level of abstraction we describe the behavior of a workflow with a transition tree. This definition is independent of the language used to describe workflows.

5 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?5 Abstract Workflow Abstract workflow abstracts from data supplied by external environment Definition: An abstract workflow (AW) is a tuple (V, E, r) which represents a rooted edge-labeled tree with nodes V V, edges E V×A×V, and root r V.

6 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?6 Concrete Workflow Concrete Workflow represents all data supplied by environment Definition A concrete workflow (CW) is a tuple (V, E, r) which represents a rooted edge-labeled tree with nodes V V, edges E V × (A ×I ) × V, and root r V.

7 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?7 Consistent & deterministic CW CW (V, E, r) is called: Consistent if it holds that if there is an edge (n 1, (a, i), n 2 ) E and an edge (n 3, (a, j), n 4 ) E then there is also an edge (n 1, (a, j), n 5 ) E. Deterministic if for every node n V and pair (a, i) A×I there is at most one edge (n, (a, i), n) E.

8 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?8 Work-set Work-set is the set of activities that could be performed by the environment in this state In each state system offers the environment a choice in the form of work-set The environment then makes a choice a and supplies the information i Definition: Work-set of a node n V is defined such that W(n) = {a|(n, (a, i), n) E}.

9 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?9 Workflow Trace Workflow trace consists of: The work-set A set of activity identifiers The choice made by the environment Represented by an activity identifier The data supplied by the environment Represented by an element of I

10 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?10 Instance Relation Instance relation is a relationship between CWs and AWs Definition: An instance relation between an AW (V 1,E 1, r 1 ) and CW (V 2,E 2, r 2 ) is a relation H V 1 × V 2 such that H(r1, r2), if (n 1, a, n 1 ) E 1 and H(n 1, n 2 ) then there is an edge (n 2, (a, i), n 2 ) E2 such that H(n 1, n 2 ), and if (n 2, (a, i), n 2 ) E 2 and H(n 1, n 2 ) then there is an edge (n 1, a, n 1 ) E 1 and H(n 1, n 2 ). A CW T an instance of an AW T if T is consistent and T and T are related

11 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?11 Observational Equivalence There are two notions of OE: Observation equivalence for CW: Two CWs are called observation equivalent if their workflow trace sets are the same. Observation equivalence for AW: Two AWs are called observation equivalent if the sets of workflow trace sets of their instances are the same. Theorem of bisimilarity: Two AWs are bisimilar iff they are observation equivalent

12 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?12 WFs with Silent Steps Silent step (denoted as τ -step) is entirely controlled by the system and unobservable (directly) for environment. Correspond to internal tasks (e.g. updating a variable, synchronizing tasks, etc) BUT this steps could be observed indirectly Adaptation of definitions: The definition of work-set will exclude τ -steps Definitions of Wf trace and OE vary depending on the interpretation Task τ A in AW definition is introduced τ is associated to the empty input data in CW definition

13 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?13 Classical notions of equivalence There are two notions of equivalence In both cases roots have to be related by R Weak bisimilarity If R(r, s) and r r then there exists a path s s such that R(r, s), where r r denotes a path r r 1 r 2 r if α= τ and a path r r if α= τ. Branching bisimilarity If R(r, s) and r r then either α= τ and R(r, s) or there exists a path s s 1 s such that R(r, s 1 ) and R(r, s).

14 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?14 Classical notions of equivalence In order to mirror a step A of a given process, it is possible to precede and follow A with a number of τ steps in the equivalent process. The difference between the two notions is that branching bisimilarity preserves the branching structure of the process by further imposing that all the τ steps taken before and after A lead to states that offer identical sets of possible future choices.

15 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?15 Semantics with visible silent steps We explore three types of semantics where τ steps may be observed in the traces: Full semantics Change semantics Non-empty semantics

16 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?16 Full semantics This semantics can be formalized simply by taking definition of Wf trace excluding τ from the offered work-sets W i For example, T 7 has two possible traces: ({A,B},A, a, ) and ({A,B},B, b, ) T 8 also has two possible traces: (, τ,, {A},A, a, ) and (, τ,, {B},B, b, )

17 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?17 Change semantics The change semantics considers only τ steps that result in a modified work-set to be visible. For T 10 there is a difference between the full semantics and the change semantics. In the full semantics there are four possible traces while in the change semantics there are two possible traces: ({A,B},A, a, ) and ({A,B},B, b, )

18 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?18 Equivalence relations under change semantics Equivalence relation of traces Let t cs be the smallest equivalence relation such that for any pair of workflow traces t 1 = (X 1,A 1, a 1,..., X n, τ,, X n+1,A n+1, a n+1, X n+2,..., X m ) and t 2 = (X 1,A 1, a 1,..., X n,A n+1, a n+1, X n+2,..., X m ): t 1 t cs t 2 if X n = X n+1 Equivalence relation of CWs and AWs Let T 1 and T 2 be two CWs, T 1 cs T 2 iff in the full semantics for every workflow trace t 1 of T 1 there exists a workflow trace t 2 of T 2 such that t 1 t cs t 2 and vice versa.

19 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?19 Non-empty semantics The non-empty semantics abstracts from τ steps that occur when the work- set is empty. For T 8 and T 12 we obtain different traces then in the full semantics. For T 8 we get ({A},A, a, ) and ({B},B, b, ) and for T 12 we get ({A,B},A, a, ) and ({A,B},B, b, )

20 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?20 Equivalence relations under non-empty semantics Equivalence relation of traces Let t nes be the smallest equivalence relation such that for any pair of workflow traces t 1 = (X 1,A 1, a 1,..., X n, A n, a n,, τ,, X n+2,..., X m ) and t 2 = (X 1,A 1, a 1,...,X n,A n, a n, X n+2,..., X m ): t 1 t nes t 2 Equivalence relation of CWs and AWs Let T 1 and T 2 be two CWs, T 1 nes T 2 iff in the full semantics for every workflow trace t 1 of T 1 there exists a workflow trace t 2 of T 2 such that t 1 t nes t 2 and vice versa.

21 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?21 Semantics with invisible silent steps We also explore three types of semantics where τ steps cannot be observed Eager semantics Far-sighted semantics Near-sighted semantics

22 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?22 Eager semantics In the eager semantics the system gives priority to τ steps, i.e., as long as τ steps are possible no offer is made to the environment. For example, T 7, T 9, T 10, T 12 have two possible traces: ({A,B},A, a, ) and ({A,B},B, b, ) T 8 also has two possible traces: ({A},A, a, ) and ({B},B, b, ) T 11 only has one possible trace: ({B},B, b, )

23 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?23 Far-sighted semantics In the far-sighted semantics the system looks at all states that can be reached through zero or more τ steps and offers all activity identifiers of edges that leave from such states. For example, T 8 has two possible traces: ({A,B},A, a, and {A,B},B, b, )

24 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?24 Near-sighted semantics In the near-sighted semantics the system can make a choice between making an offer or taking a τ step. For example, T 9 has three possible traces: ({A},A, a, ), ({A,B},A, a, ), and ({A,B},B, b, ) T 11 also has three possible traces: ({A,B},A, a, ), ({A,B},B, b, ), and {B},B, b, )

25 Examples 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?25

26 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?26 Summary Results table This table summarizes our findings

27 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?27 Conclusion Which equivalence is most suitable? Classic ones do not consider explicit offers. Notions with visible τ- steps The change semantics. It captures the intuition that the work-set is all that the environment can perceive in-between two inputs. Notions with invisible τ- steps The near-sighted semantics. The eager semantics may create dead branches, the far-sighted semantics lets the choice of the τ steps be influenced by the environment, contradicting the assumption that τ steps are entirely controlled by the system.

28 24-Jul-15Workgroup and Workflow Systems - When are two Workflows the Same?28 Final slide Thanks for reading! Have a nice day! Here is the link for original paper: But a little warning: the paper consists mostly of LIQUID VACUUM!! P.S. In Soviet Russia this presentation reads YOU!!