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.

Презентация:



Advertisements
Похожие презентации
AVL-Trees COMP171 Fall AVL Trees / Slide 2 Balanced binary tree * The disadvantage of a binary search tree is that its height can be as large as.
Advertisements

11 BASIC DRESS-UP FEATURES. LESSON II : DRESS UP FEATURES 12.
HPC Pipelining Parallelism is achieved by starting to execute one instruction before the previous one is finished. The simplest kind overlaps the execution.
Multiples Michael Marchenko. Definition In mathematics, a multiple is the product of any quantity and an integer. in other words, for the quantities a.
SPLAY TREE The basic idea of the splay tree is that every time a node is accessed, it is pushed to the root by a series of tree rotations. This series.
© 2005 Cisco Systems, Inc. All rights reserved. BGP v Route Selection Using Policy Controls Using Multihomed BGP Networks.
© 2005 Cisco Systems, Inc. All rights reserved. BGP v Customer-to-Provider Connectivity with BGP Connecting a Multihomed Customer to Multiple Service.
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects.
Linear Block Codes Mahdi Barhoush Mohammad Hanaysheh.
The presentation is prepared by Senashov Egor & Sechko Yurij pupil of the 8 th form V " school2.
How can we measure distances in open space. Distances in open space.
Diffraction and Interference. Interference and Diffraction Distinguish Waves from Particles O The key to understanding why light behaves like waves is.
Here are multiplication tables written in a code. The tables are not in the correct order. Find the digit, represented by each letter.
Types of Government. Types of government define who rules and who participates There are three types of governments: 1.Autocracy: Rule by one 2.Oligarchy:
Family Relationships (Семейные Отношения). Family How could you describe the word family? First of all family means a close unit of parents and their.
Knot theory. In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a.
© 2009 Avaya Inc. All rights reserved.1 Chapter Two, Voic Pro Components Module Two – Actions, Variables & Conditions.
Inner Classes. 2 Simple Uses of Inner Classes Inner classes are classes defined within other classes The class that includes the inner class is called.
© 2006 Cisco Systems, Inc. All rights reserved. BSCI v Implementing BGP Explaining BGP Concepts and Terminology.
© 2006 Cisco Systems, Inc. All rights reserved. MPLS v MPLS VPN Implementation Configuring VRF Tables.
Транксрипт:

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,

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

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

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.

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.

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.

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.

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

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

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

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

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

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

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.

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

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

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

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.

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

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.

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

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

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

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

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

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.

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