SlideShare a Scribd company logo
1 of 28
Download to read offline
Modelling provenance using
                                         Structured Occurrence Networks




                          Paolo Missier, Brian Randell, Maciej Koutny
                                     Newcastle University, UK


                                           IPAW’12
                                 Santa Barbara, CA, June 2012




Thursday, June 21, 2012
Petri Nets and Occurrence Nets

                               Historically, Occurrence Nets have been used to define
                               process semantics of Petri Nets [2]
   IPAW 2012 - P.Missier




                           [2] Best, Eike, and Raymond Devillers. “Sequential and concurrent behaviour in Petri net theory.” Theoretical Computer
                                Science 55, no. 1 (1987): 87-136. http://www.sciencedirect.com/science/article/pii/0304397587900909.
    2

Thursday, June 21, 2012
Occurrence Nets




                                ON is about capturing causal relationships
                                between events and conditions


                           ON = (C, E, F ) with nodes C E and a flow relation F ⊆ (C ×E)∪(E × C) satisfying the following:
                           (i) for every condition c there is at most one event e such that (e,c) ∈ F, and at most one event f such that (c,f) ∈ F;
                           (ii) for every event e there is at least one condition c such that (c, e) ∈ F , and at least one condition d such that (e,
                             d) ∈ F ;
                           (iii) ON forms an acyclic graph and F + is a partial order relation (the relation PrecON = (F ◦ F)|C×C is acyclic)
   IPAW 2012 - P.Missier




    3

Thursday, June 21, 2012
Provenance and Occurrence Nets
                           • "Provenance is defined as a record that • An Occurrence Net is an abstract record of
                             describes the people, institutions,       a single execution of some computing
                             entities, and activities involved in      system
                             producing, influencing, or delivering a   • Only information about causality and
                             piece of data or a thing." [PROV]            concurrency between events and visited
                                                                          local states is represented
   IPAW 2012 - P.Missier




    4

Thursday, June 21, 2012
Provenance and Occurrence Nets
                           • "Provenance is defined as a record that • An Occurrence Net is an abstract record of
                             describes the people, institutions,       a single execution of some computing
                             entities, and activities involved in      system
                             producing, influencing, or delivering a   • Only information about causality and
                             piece of data or a thing." [PROV]            concurrency between events and visited
                                                                          local states is represented


                           Data: The evolution of variable A as a ON:
   IPAW 2012 - P.Missier




    4

Thursday, June 21, 2012
Provenance and Occurrence Nets
                           • "Provenance is defined as a record that • An Occurrence Net is an abstract record of
                             describes the people, institutions,       a single execution of some computing
                             entities, and activities involved in      system
                             producing, influencing, or delivering a   • Only information about causality and
                             piece of data or a thing." [PROV]            concurrency between events and visited
                                                                          local states is represented


                           Data: The evolution of variable A as a ON:




                           Agents: The evolution of Bob, the document editor:
                                         read                                         drafted    ready
                                                        performed       verified
                                  ptd    paper                                        internal     to
                                                           exp.         results                   draft
                                          p1                                           memo
   IPAW 2012 - P.Missier




                                                                        read
                                                                        paper
                                                                         p2




    4

Thursday, June 21, 2012
From ON to Structured ON
                             ON is an adequate starting point, but extensions are needed to
                             represent the activity of complex systems

                           • Structured Occurrence Nets provide these extensions as new
                             relationships amongst multiple ONs [2]
   IPAW 2012 - P.Missier




                           [2] Koutny, M., and B Randell. “Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and
                               Analysis Techniques.” Fundamenta Informaticae 97 (2009).
    5

Thursday, June 21, 2012
From ON to Structured ON
                             ON is an adequate starting point, but extensions are needed to
                             represent the activity of complex systems

                           • Structured Occurrence Nets provide these extensions as new
                             relationships amongst multiple ONs [2]
   IPAW 2012 - P.Missier




                           [2] Koutny, M., and B Randell. “Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and
                               Analysis Techniques.” Fundamenta Informaticae 97 (2009).
    5

Thursday, June 21, 2012
Provenance modelling patterns using SON

                               Main goal of this work:
                                       to explore the use of Structured Occurrence Nets
                                                as a formal model of provenance


                           • Data is viewed as an evolving system

                           • Agents are also evolving systems, thus their evolution is also captured

                           • Uniform representation of Agents / Activity / Data interplay

                           • Representation of multi-layered Provenance
                              – eg:the provenance of a workflow run is underpinned by system-level provenance
                              – SONs are suitable for modelling at multiple levels of abstraction
   IPAW 2012 - P.Missier




                             Expected by-product of the investigation:
                              suggest enhancements to the current SON model
    6

Thursday, June 21, 2012
Talk outline
                           • C-SON: ON + communication relation
                             – a provenance pattern to represent workflow patterns

                           • T-SON: C-SON + temporal abstraction
                           • (more abstraction relations omitted in the talk)
                           • Modelling multi-layered provenance
                           • Agents as evolving systems
                             – provenance of agents
   IPAW 2012 - P.Missier




    7

Thursday, June 21, 2012
Communication SONs
                           • Goal: to capture communication between ONs that otherwise proceed
                             concurrently
                           • by introducing a Communication relation amongst activities in two ONs
                              – induces a partial order on the states and conditions of the two nets
                              – must result in an acyclic net



                                                                   e1 cannot have happened after f1

                                                                   e2, f2 must have happened simultaneously
   IPAW 2012 - P.Missier




    8

Thursday, June 21, 2012
Communication SONs
                           • Goal: to capture communication between ONs that otherwise proceed
                             concurrently
                           • by introducing a Communication relation amongst activities in two ONs
                              – induces a partial order on the states and conditions of the two nets
                              – must result in an acyclic net



                                                                   e1 cannot have happened after f1

                                                                   e2, f2 must have happened simultaneously
   IPAW 2012 - P.Missier




    8

Thursday, June 21, 2012
C-SON at work - a first provenance pattern




                           • Each ON models one variable as a system.
                           • The composed activity “A:=A+1; A:=A+B; B:=A+B” is represented as a SON
                           composed of a pair of communicating ONs
   IPAW 2012 - P.Missier




                           • The resulting SON captures a (partial) order of possible reads and writes
                           leading to the final result

    9

Thursday, June 21, 2012
Workflow execution traces using C-SON

                                                                                                                                           X= 10

                                                                               Y:= f(X)
                                                             (a)                                                    (b)
                                                          Program                                                Execution
                                                        specification                                            instance                   f()


                                                                            <X,Z> := g(X,Y)                                                   Y = "200"

                                                                                                                                            g()


                                                                                                                                  X = 20          Z = "20"



                                                       10               r                10         r       10                               w               20

                                                   X


                                   (c)
                           SON representation of
                             Execution trace                                     f                                            g

                                                   Program
                                                   execution
   IPAW 2012 - P.Missier




                                                                                                                                                             w    20
                                                                                     w        200       r               200
                                                                                                                                                                       Z
                                                                                                                              Y



  10

Thursday, June 21, 2012
Temporal SON (T-SON)
                           • Goal: to replace part of an ON with new “atomic” actions
                             – a form of temporal abstraction
                             – these new actions only appear atomic at one level of abstraction
   IPAW 2012 - P.Missier




   11

Thursday, June 21, 2012
T-SON in action: multi-layered provenance
                           • Provenance of computed data naturally comes in layers:
                             – program execution (incl. workflow controller)
                                • system-level primitives, network protocols


                                           10    r                   10


                                                     t                         t                                   10               r       10
                                     t
                                                                                                               X

                             10          fetch                   send               10


                             X
                                                                                                                                        f

                                                                                                                        Program
                                                                                                                        execution
                                                                              get                compute




                                                                          t                  t             t


                                                                                         f
   IPAW 2012 - P.Missier




                                                         Program
                                                         execution




                                  Temporal abstraction used to hide/reveal lower-level details of both
  12                              systems and their interaction (i.e., reading from storage)
Thursday, June 21, 2012
T-SON: multi-layered provenance
                           Additional unfolding:
                           - assume f is a service call
                           - reveal details of communication with an underlying service implementation



                                                         10               r       10

                                                     X




                                                                              f

                                                              Program
                                                              execution




                                                          Service
                                                         execution
   IPAW 2012 - P.Missier




  13

Thursday, June 21, 2012
T-SON: multi-layered provenance



                                      10      r             10


                                                  t                t
                                t

                                                                                                     msg                 msg
                                                                                                   receive               send
                           10       fetch               send           10


                                                                                    Service
                           X
                                                                                   execution




                                                                            msg                              msg
                                                             get                                                    receive
                                                                            prep                             send




                                                        t                                 t
                                                                                                                         t

                                                                                               f
   IPAW 2012 - P.Missier




                                            Program
                                            execution




  14

Thursday, June 21, 2012
Agents as evolving systems
                           Alice and Bob collaborate on document editing




                            An agent performs activities that account for changes in the state of the data
                           • F is data (a file)
                           • Data and agents are modelled as systems
                             • Each system is a SON
                           • Communication abstraction used to synchronize events across different
   IPAW 2012 - P.Missier




                           systems
                             • Bob.draft → F.write, F.read → Alice.”read draft” etc.
                           • For example, Bob in the state b2 is unaware of Alice’s feedback
                           • Bob in state b3 has read Alice’s feedback
  15

Thursday, June 21, 2012
Agents as evolving systems
                           • Tracking the state of agents is important
                              – we know that it is the “version” of Bob that is aware of Alice’s comment that is
                                responsible for the latest edit




                             Below: Bob’s edits to the document do not take account of Alice’s comments

                                            ptd   draft        b2                                          edit   b4



                                     Bob




                                                   w      f1          r      f1      w       f2   r   f2    w     f3
   IPAW 2012 - P.Missier




                                     F




                                                                    read            leave
                                                          a1                a2
                                                                    draft         comments

  16                                Alice


Thursday, June 21, 2012
Summary
                           • SONs extend well-known Occurrence Nets

                           • Simple graphical notation with formal grounding
                             – amenable to various types of analysis

                           • Appealing for capturing system evolution and inter-system
                             communication

                           • Accommodates multiple levels of abstraction

                           • Evolution traces of Data, Agents and Activities provenance queried
                             seamlessly

                           • Some software tool support (in progress), more work needed here

                           • Feedback for customizations of the SON model itself!
   IPAW 2012 - P.Missier




  17

Thursday, June 21, 2012
Selected References
                                •    V. Khomenko, M. Koutny, A. Yakovlev: Logic Synthesis for Asynchronous
                                     Circuits Based on Petri Net Unfoldings and Incremental SAT. Fundamenta
                                     Informaticae 70, 2006.
                                       •    http://www.cs.ncl.ac.uk/publications/inproceedings/papers/749.pdf
                                •    M. Koutny, B. Randell: Structured Occurrence Nets: A Formalism for
                                     Aiding System Failure Prevention and Analysis Techniques. Fundamenta
                                     Informaticae 97, 2009.
                                       •    http://www.cs.ncl.ac.uk/publications/trs/papers/1162.pdf
                                •    B. Li, M. Koutny: Verification and Simulation Tool for Communication Structured
                                     Occurrence Nets. CS-TR, Newcastle University, (to appear).
                                •    P.M. Merlin and B. Randell: State Restoration in Distributed Systems. Proc.
                                     FTCS-8, 1978.
                                       •    http://www.cs.ncl.ac.uk/publications/inproceedings/papers/347.pdf
                                •    I. Poliakov, V. Khomenko, A. Yakovlev: Workcraft - A Framework for
                                     Interpreted Graph Models. LNCS 5606, 2009.
                                •    B. Randell, M. Koutny: Failures: Their Definition, Modelling and Analysis. LNCS
                                     4711, 2007.
                                       •    http://www.cs.ncl.ac.uk/publications/trs/papers/994.pdf
   IPAW 2012 - P.Missier




                                •    B. Randell, M. Koutny: Structured Occurrence Nets: Incomplete,
                                     Contradictory and Uncertain Failure Evidence. CS-TR 1170, Newcastle
                                     University, 2009.
                                       •    http://www.cs.ncl.ac.uk/publications/trs/papers/1170.pdf

  18                       Martinique, Jan. 2012
                                                                                                                       24

Thursday, June 21, 2012
IPAW 2012 - P.Missier   EXTRA material




  19

Thursday, June 21, 2012
SON provenance and PROV

                                                    read
                                 b2                                  b3             edit           b4
                                                  feedback

                           Bob                                                                               (a)



                                 f2               r          f2      r         f2          w            f3

                           F




                                                         used                    wasGeneratedBy
                                             f2                          edit      wa                 f3     (b)
                                                                                      sG
                                                                                        en
                                                                                           era
                                      used                         wasAssociatedWith           ted
                                                                                                   By
                                        read           wasGeneratedBy
                                      feedback                         Bob_b3 wasDerivedFrom Bob_b4
   IPAW 2012 - P.Missier




                                 wasAssociatedWith
                                                        wasDerivedFrom

                                        Bob_b2
  20

Thursday, June 21, 2012
T-SON and finite-duration activities

                           In Occurrence Nets, events (activities) are instantaneous.
                           Using temporal abstraction one can add a time duration to activities


                                                                                        [s,e]
                                               Activity f                           f
                                          with duration [s,e]


                                                        t         t                t            t   t       t



                                                            s                                           e



                                                        c              duration interval of f                   c



                                               t1                 t2                                                tn


                                        Time
   IPAW 2012 - P.Missier




  21

Thursday, June 21, 2012
SON -- behavioural abstraction
                           • Insight: ‘system’ and ‘state’ are not separate concepts
                           • The same graph node may be used to represent either a state or a
                           system, at different levels of abstraction




                           Key idea of Structured Occurrence Nets:
                           • multiple ONs, each portraying a system/state at some level of abstraction
   IPAW 2012 - P.Missier




                           • associations amongst the ONs are then established by means of new
                           relation types

  22

Thursday, June 21, 2012
B-abstraction in use
                           – An application of behavioural abstraction -- state/system duality
                           – Bob’s state b1 expands into a system’s activities (b1)
                            – the expansion provides additional insight into Bob’s “knowledge level” /
                              “preparedness” prior to drafting the document
   IPAW 2012 - P.Missier




  23                                                   Bob’s state as a system
Thursday, June 21, 2012
Finding good abstractions - cuts in ON and SON

                           (a)


                                                       (d)




                           (b)




                                                       (e)
   IPAW 2012 - P.Missier




                           (c)

  24

Thursday, June 21, 2012

More Related Content

Viewers also liked

Invited talk @ DCC09 workshop
Invited talk @ DCC09 workshopInvited talk @ DCC09 workshop
Invited talk @ DCC09 workshopPaolo Missier
 
Session talk @ AGU09
Session talk @ AGU09Session talk @ AGU09
Session talk @ AGU09Paolo Missier
 
PDT: Personal Data from Things, and its provenance
PDT: Personal Data from Things,and its provenancePDT: Personal Data from Things,and its provenance
PDT: Personal Data from Things, and its provenancePaolo Missier
 
ProvAbs: model, policy, and tooling for abstracting PROV graphs
ProvAbs: model, policy, and tooling for abstracting PROV graphsProvAbs: model, policy, and tooling for abstracting PROV graphs
ProvAbs: model, policy, and tooling for abstracting PROV graphsPaolo Missier
 
Big Data Quality Panel : Diachron Workshop @EDBT
Big Data Quality Panel: Diachron Workshop @EDBTBig Data Quality Panel: Diachron Workshop @EDBT
Big Data Quality Panel : Diachron Workshop @EDBTPaolo Missier
 
Your data won’t stay smart forever: exploring the temporal dimension of (big ...
Your data won’t stay smart forever:exploring the temporal dimension of (big ...Your data won’t stay smart forever:exploring the temporal dimension of (big ...
Your data won’t stay smart forever: exploring the temporal dimension of (big ...Paolo Missier
 
The lifecycle of reproducible science data and what provenance has got to do ...
The lifecycle of reproducible science data and what provenance has got to do ...The lifecycle of reproducible science data and what provenance has got to do ...
The lifecycle of reproducible science data and what provenance has got to do ...Paolo Missier
 
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science Central
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science CentralCloud e-Genome: NGS Workflows on the Cloud Using e-Science Central
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science CentralPaolo Missier
 
Paper presentation @DILS'07
Paper presentation @DILS'07Paper presentation @DILS'07
Paper presentation @DILS'07Paolo Missier
 

Viewers also liked (10)

C4Bio paper talk
C4Bio paper talkC4Bio paper talk
C4Bio paper talk
 
Invited talk @ DCC09 workshop
Invited talk @ DCC09 workshopInvited talk @ DCC09 workshop
Invited talk @ DCC09 workshop
 
Session talk @ AGU09
Session talk @ AGU09Session talk @ AGU09
Session talk @ AGU09
 
PDT: Personal Data from Things, and its provenance
PDT: Personal Data from Things,and its provenancePDT: Personal Data from Things,and its provenance
PDT: Personal Data from Things, and its provenance
 
ProvAbs: model, policy, and tooling for abstracting PROV graphs
ProvAbs: model, policy, and tooling for abstracting PROV graphsProvAbs: model, policy, and tooling for abstracting PROV graphs
ProvAbs: model, policy, and tooling for abstracting PROV graphs
 
Big Data Quality Panel : Diachron Workshop @EDBT
Big Data Quality Panel: Diachron Workshop @EDBTBig Data Quality Panel: Diachron Workshop @EDBT
Big Data Quality Panel : Diachron Workshop @EDBT
 
Your data won’t stay smart forever: exploring the temporal dimension of (big ...
Your data won’t stay smart forever:exploring the temporal dimension of (big ...Your data won’t stay smart forever:exploring the temporal dimension of (big ...
Your data won’t stay smart forever: exploring the temporal dimension of (big ...
 
The lifecycle of reproducible science data and what provenance has got to do ...
The lifecycle of reproducible science data and what provenance has got to do ...The lifecycle of reproducible science data and what provenance has got to do ...
The lifecycle of reproducible science data and what provenance has got to do ...
 
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science Central
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science CentralCloud e-Genome: NGS Workflows on the Cloud Using e-Science Central
Cloud e-Genome: NGS Workflows on the Cloud Using e-Science Central
 
Paper presentation @DILS'07
Paper presentation @DILS'07Paper presentation @DILS'07
Paper presentation @DILS'07
 

Similar to Structured Occurrence Network for provenance: talk for ipaw12 paper

Supporting Inter-Organizational Situation Assessment in Crisis Management
Supporting Inter-Organizational Situation Assessment in Crisis ManagementSupporting Inter-Organizational Situation Assessment in Crisis Management
Supporting Inter-Organizational Situation Assessment in Crisis ManagementTorben Wiedenhoefer
 
Rule-based Information Extraction from Disease Outbreak Reports
Rule-based Information Extraction from Disease Outbreak ReportsRule-based Information Extraction from Disease Outbreak Reports
Rule-based Information Extraction from Disease Outbreak ReportsWaqas Tariq
 
Mythbusters: Event Stream Processing v. Complex Event Processing
Mythbusters: Event Stream Processing v. Complex Event ProcessingMythbusters: Event Stream Processing v. Complex Event Processing
Mythbusters: Event Stream Processing v. Complex Event ProcessingTim Bass
 
Object-Centric Processes - from cases to objects and relations… and beyond
Object-Centric Processes - from cases to objects and relations… and beyondObject-Centric Processes - from cases to objects and relations… and beyond
Object-Centric Processes - from cases to objects and relations… and beyondDirk Fahland
 
Financial Networks and Cartography
Financial Networks and CartographyFinancial Networks and Cartography
Financial Networks and CartographyKimmo Soramaki
 
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...Jan Recker @ University of Hamburg
 
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...Inter-Organizational Crisis Management Infrastructures for Electrical Power B...
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...Torben Wiedenhoefer
 
Situation based analysis and control for supporting Event-web applications
Situation based analysis and control for supporting Event-web applicationsSituation based analysis and control for supporting Event-web applications
Situation based analysis and control for supporting Event-web applicationsVivek Singh
 
The Symbiotic Nature of Provenance and Workflow
The Symbiotic Nature of Provenance and WorkflowThe Symbiotic Nature of Provenance and Workflow
The Symbiotic Nature of Provenance and WorkflowEric Stephan
 
A data driven approach for monitoring network events
A data driven approach for monitoring network eventsA data driven approach for monitoring network events
A data driven approach for monitoring network eventsJisc
 
Scio12 sem web_final
Scio12 sem web_finalScio12 sem web_final
Scio12 sem web_finalKristi Holmes
 
A Resource Oriented Framework for Context-Aware Enterprise Applications
A Resource Oriented Framework for Context-Aware Enterprise ApplicationsA Resource Oriented Framework for Context-Aware Enterprise Applications
A Resource Oriented Framework for Context-Aware Enterprise Applicationsruyalarcon
 
Mining Development Repositories to Study the Impact of Collaboration on Softw...
Mining Development Repositories to Study the Impact of Collaboration on Softw...Mining Development Repositories to Study the Impact of Collaboration on Softw...
Mining Development Repositories to Study the Impact of Collaboration on Softw...Nicolas Bettenburg
 
Managing Complexity in a World of Surprise David L. Alderson, PhD
Managing Complexity in a World of Surprise David L. Alderson, PhDManaging Complexity in a World of Surprise David L. Alderson, PhD
Managing Complexity in a World of Surprise David L. Alderson, PhDPacificResearchPlatform
 
Understanding Collaboration in Fluid Organizations, a Proximity Approach
Understanding Collaboration in Fluid Organizations, a Proximity ApproachUnderstanding Collaboration in Fluid Organizations, a Proximity Approach
Understanding Collaboration in Fluid Organizations, a Proximity ApproachDawn Foster
 

Similar to Structured Occurrence Network for provenance: talk for ipaw12 paper (20)

Supporting Inter-Organizational Situation Assessment in Crisis Management
Supporting Inter-Organizational Situation Assessment in Crisis ManagementSupporting Inter-Organizational Situation Assessment in Crisis Management
Supporting Inter-Organizational Situation Assessment in Crisis Management
 
Fois2010 final
Fois2010 finalFois2010 final
Fois2010 final
 
Rule-based Information Extraction from Disease Outbreak Reports
Rule-based Information Extraction from Disease Outbreak ReportsRule-based Information Extraction from Disease Outbreak Reports
Rule-based Information Extraction from Disease Outbreak Reports
 
Mythbusters: Event Stream Processing v. Complex Event Processing
Mythbusters: Event Stream Processing v. Complex Event ProcessingMythbusters: Event Stream Processing v. Complex Event Processing
Mythbusters: Event Stream Processing v. Complex Event Processing
 
Object-Centric Processes - from cases to objects and relations… and beyond
Object-Centric Processes - from cases to objects and relations… and beyondObject-Centric Processes - from cases to objects and relations… and beyond
Object-Centric Processes - from cases to objects and relations… and beyond
 
Innovation ecosystems value co-creation
Innovation ecosystems value co-creationInnovation ecosystems value co-creation
Innovation ecosystems value co-creation
 
Financial Networks and Cartography
Financial Networks and CartographyFinancial Networks and Cartography
Financial Networks and Cartography
 
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...
From Representation to Mediation: A New Agenda for Conceptual Modeling Resear...
 
eventdemo2016
eventdemo2016eventdemo2016
eventdemo2016
 
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...Inter-Organizational Crisis Management Infrastructures for Electrical Power B...
Inter-Organizational Crisis Management Infrastructures for Electrical Power B...
 
Situation based analysis and control for supporting Event-web applications
Situation based analysis and control for supporting Event-web applicationsSituation based analysis and control for supporting Event-web applications
Situation based analysis and control for supporting Event-web applications
 
169 s170
169 s170169 s170
169 s170
 
The Symbiotic Nature of Provenance and Workflow
The Symbiotic Nature of Provenance and WorkflowThe Symbiotic Nature of Provenance and Workflow
The Symbiotic Nature of Provenance and Workflow
 
A data driven approach for monitoring network events
A data driven approach for monitoring network eventsA data driven approach for monitoring network events
A data driven approach for monitoring network events
 
Scio12 sem web_final
Scio12 sem web_finalScio12 sem web_final
Scio12 sem web_final
 
A Resource Oriented Framework for Context-Aware Enterprise Applications
A Resource Oriented Framework for Context-Aware Enterprise ApplicationsA Resource Oriented Framework for Context-Aware Enterprise Applications
A Resource Oriented Framework for Context-Aware Enterprise Applications
 
Mining Development Repositories to Study the Impact of Collaboration on Softw...
Mining Development Repositories to Study the Impact of Collaboration on Softw...Mining Development Repositories to Study the Impact of Collaboration on Softw...
Mining Development Repositories to Study the Impact of Collaboration on Softw...
 
Managing Complexity in a World of Surprise David L. Alderson, PhD
Managing Complexity in a World of Surprise David L. Alderson, PhDManaging Complexity in a World of Surprise David L. Alderson, PhD
Managing Complexity in a World of Surprise David L. Alderson, PhD
 
Understanding Collaboration in Fluid Organizations, a Proximity Approach
Understanding Collaboration in Fluid Organizations, a Proximity ApproachUnderstanding Collaboration in Fluid Organizations, a Proximity Approach
Understanding Collaboration in Fluid Organizations, a Proximity Approach
 
CAiSE 2018 Keynote
CAiSE 2018 KeynoteCAiSE 2018 Keynote
CAiSE 2018 Keynote
 

More from Paolo Missier

Interpretable and robust hospital readmission predictions from Electronic Hea...
Interpretable and robust hospital readmission predictions from Electronic Hea...Interpretable and robust hospital readmission predictions from Electronic Hea...
Interpretable and robust hospital readmission predictions from Electronic Hea...Paolo Missier
 
Data-centric AI and the convergence of data and model engineering: opportunit...
Data-centric AI and the convergence of data and model engineering:opportunit...Data-centric AI and the convergence of data and model engineering:opportunit...
Data-centric AI and the convergence of data and model engineering: opportunit...Paolo Missier
 
Realising the potential of Health Data Science: opportunities and challenges ...
Realising the potential of Health Data Science:opportunities and challenges ...Realising the potential of Health Data Science:opportunities and challenges ...
Realising the potential of Health Data Science: opportunities and challenges ...Paolo Missier
 
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)Paolo Missier
 
A Data-centric perspective on Data-driven healthcare: a short overview
A Data-centric perspective on Data-driven healthcare: a short overviewA Data-centric perspective on Data-driven healthcare: a short overview
A Data-centric perspective on Data-driven healthcare: a short overviewPaolo Missier
 
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Paolo Missier
 
Tracking trajectories of multiple long-term conditions using dynamic patient...
Tracking trajectories of  multiple long-term conditions using dynamic patient...Tracking trajectories of  multiple long-term conditions using dynamic patient...
Tracking trajectories of multiple long-term conditions using dynamic patient...Paolo Missier
 
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...Paolo Missier
 
Digital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcareDigital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcarePaolo Missier
 
Digital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcareDigital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcarePaolo Missier
 
Data Provenance for Data Science
Data Provenance for Data ScienceData Provenance for Data Science
Data Provenance for Data SciencePaolo Missier
 
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Paolo Missier
 
Quo vadis, provenancer?  Cui prodest?  our own trajectory: provenance of data...
Quo vadis, provenancer? Cui prodest? our own trajectory: provenance of data...Quo vadis, provenancer? Cui prodest? our own trajectory: provenance of data...
Quo vadis, provenancer?  Cui prodest?  our own trajectory: provenance of data...Paolo Missier
 
Data Science for (Health) Science: tales from a challenging front line, and h...
Data Science for (Health) Science:tales from a challenging front line, and h...Data Science for (Health) Science:tales from a challenging front line, and h...
Data Science for (Health) Science: tales from a challenging front line, and h...Paolo Missier
 
Analytics of analytics pipelines: from optimising re-execution to general Dat...
Analytics of analytics pipelines:from optimising re-execution to general Dat...Analytics of analytics pipelines:from optimising re-execution to general Dat...
Analytics of analytics pipelines: from optimising re-execution to general Dat...Paolo Missier
 
ReComp: optimising the re-execution of analytics pipelines in response to cha...
ReComp: optimising the re-execution of analytics pipelines in response to cha...ReComp: optimising the re-execution of analytics pipelines in response to cha...
ReComp: optimising the re-execution of analytics pipelines in response to cha...Paolo Missier
 
ReComp, the complete story: an invited talk at Cardiff University
ReComp, the complete story:  an invited talk at Cardiff UniversityReComp, the complete story:  an invited talk at Cardiff University
ReComp, the complete story: an invited talk at Cardiff UniversityPaolo Missier
 
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Paolo Missier
 
Decentralized, Trust-less Marketplace for Brokered IoT Data Trading using Blo...
Decentralized, Trust-less Marketplacefor Brokered IoT Data Tradingusing Blo...Decentralized, Trust-less Marketplacefor Brokered IoT Data Tradingusing Blo...
Decentralized, Trust-less Marketplace for Brokered IoT Data Trading using Blo...Paolo Missier
 
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Paolo Missier
 

More from Paolo Missier (20)

Interpretable and robust hospital readmission predictions from Electronic Hea...
Interpretable and robust hospital readmission predictions from Electronic Hea...Interpretable and robust hospital readmission predictions from Electronic Hea...
Interpretable and robust hospital readmission predictions from Electronic Hea...
 
Data-centric AI and the convergence of data and model engineering: opportunit...
Data-centric AI and the convergence of data and model engineering:opportunit...Data-centric AI and the convergence of data and model engineering:opportunit...
Data-centric AI and the convergence of data and model engineering: opportunit...
 
Realising the potential of Health Data Science: opportunities and challenges ...
Realising the potential of Health Data Science:opportunities and challenges ...Realising the potential of Health Data Science:opportunities and challenges ...
Realising the potential of Health Data Science: opportunities and challenges ...
 
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)
Provenance Week 2023 talk on DP4DS (Data Provenance for Data Science)
 
A Data-centric perspective on Data-driven healthcare: a short overview
A Data-centric perspective on Data-driven healthcare: a short overviewA Data-centric perspective on Data-driven healthcare: a short overview
A Data-centric perspective on Data-driven healthcare: a short overview
 
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
 
Tracking trajectories of multiple long-term conditions using dynamic patient...
Tracking trajectories of  multiple long-term conditions using dynamic patient...Tracking trajectories of  multiple long-term conditions using dynamic patient...
Tracking trajectories of multiple long-term conditions using dynamic patient...
 
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...
Delivering on the promise of data-driven healthcare: trade-offs, challenges, ...
 
Digital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcareDigital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcare
 
Digital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcareDigital biomarkers for preventive personalised healthcare
Digital biomarkers for preventive personalised healthcare
 
Data Provenance for Data Science
Data Provenance for Data ScienceData Provenance for Data Science
Data Provenance for Data Science
 
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...Capturing and querying fine-grained provenance of preprocessing pipelines in ...
Capturing and querying fine-grained provenance of preprocessing pipelines in ...
 
Quo vadis, provenancer?  Cui prodest?  our own trajectory: provenance of data...
Quo vadis, provenancer? Cui prodest? our own trajectory: provenance of data...Quo vadis, provenancer? Cui prodest? our own trajectory: provenance of data...
Quo vadis, provenancer?  Cui prodest?  our own trajectory: provenance of data...
 
Data Science for (Health) Science: tales from a challenging front line, and h...
Data Science for (Health) Science:tales from a challenging front line, and h...Data Science for (Health) Science:tales from a challenging front line, and h...
Data Science for (Health) Science: tales from a challenging front line, and h...
 
Analytics of analytics pipelines: from optimising re-execution to general Dat...
Analytics of analytics pipelines:from optimising re-execution to general Dat...Analytics of analytics pipelines:from optimising re-execution to general Dat...
Analytics of analytics pipelines: from optimising re-execution to general Dat...
 
ReComp: optimising the re-execution of analytics pipelines in response to cha...
ReComp: optimising the re-execution of analytics pipelines in response to cha...ReComp: optimising the re-execution of analytics pipelines in response to cha...
ReComp: optimising the re-execution of analytics pipelines in response to cha...
 
ReComp, the complete story: an invited talk at Cardiff University
ReComp, the complete story:  an invited talk at Cardiff UniversityReComp, the complete story:  an invited talk at Cardiff University
ReComp, the complete story: an invited talk at Cardiff University
 
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
 
Decentralized, Trust-less Marketplace for Brokered IoT Data Trading using Blo...
Decentralized, Trust-less Marketplacefor Brokered IoT Data Tradingusing Blo...Decentralized, Trust-less Marketplacefor Brokered IoT Data Tradingusing Blo...
Decentralized, Trust-less Marketplace for Brokered IoT Data Trading using Blo...
 
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
Efficient Re-computation of Big Data Analytics Processes in the Presence of C...
 

Recently uploaded

How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyes
How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyesHow to Effectively Monitor SD-WAN and SASE Environments with ThousandEyes
How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyesThousandEyes
 
Empowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintEmpowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintMahmoud Rabie
 
OpenShift Commons Paris - Choose Your Own Observability Adventure
OpenShift Commons Paris - Choose Your Own Observability AdventureOpenShift Commons Paris - Choose Your Own Observability Adventure
OpenShift Commons Paris - Choose Your Own Observability AdventureEric D. Schabell
 
UiPath Community: AI for UiPath Automation Developers
UiPath Community: AI for UiPath Automation DevelopersUiPath Community: AI for UiPath Automation Developers
UiPath Community: AI for UiPath Automation DevelopersUiPathCommunity
 
Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.francesco barbera
 
Meet the new FSP 3000 M-Flex800™
Meet the new FSP 3000 M-Flex800™Meet the new FSP 3000 M-Flex800™
Meet the new FSP 3000 M-Flex800™Adtran
 
Introduction to Quantum Computing
Introduction to Quantum ComputingIntroduction to Quantum Computing
Introduction to Quantum ComputingGDSC PJATK
 
COMPUTER 10: Lesson 7 - File Storage and Online Collaboration
COMPUTER 10: Lesson 7 - File Storage and Online CollaborationCOMPUTER 10: Lesson 7 - File Storage and Online Collaboration
COMPUTER 10: Lesson 7 - File Storage and Online Collaborationbruanjhuli
 
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1DianaGray10
 
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...Will Schroeder
 
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UbiTrack UK
 
9 Steps For Building Winning Founding Team
9 Steps For Building Winning Founding Team9 Steps For Building Winning Founding Team
9 Steps For Building Winning Founding TeamAdam Moalla
 
Basic Building Blocks of Internet of Things.
Basic Building Blocks of Internet of Things.Basic Building Blocks of Internet of Things.
Basic Building Blocks of Internet of Things.YounusS2
 
Babel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxBabel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxYounusS2
 
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IES VE
 
Comparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioComparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioChristian Posta
 
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdf
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdfUiPath Solutions Management Preview - Northern CA Chapter - March 22.pdf
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdfDianaGray10
 
Linked Data in Production: Moving Beyond Ontologies
Linked Data in Production: Moving Beyond OntologiesLinked Data in Production: Moving Beyond Ontologies
Linked Data in Production: Moving Beyond OntologiesDavid Newbury
 
AI Fame Rush Review – Virtual Influencer Creation In Just Minutes
AI Fame Rush Review – Virtual Influencer Creation In Just MinutesAI Fame Rush Review – Virtual Influencer Creation In Just Minutes
AI Fame Rush Review – Virtual Influencer Creation In Just MinutesMd Hossain Ali
 
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...Aggregage
 

Recently uploaded (20)

How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyes
How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyesHow to Effectively Monitor SD-WAN and SASE Environments with ThousandEyes
How to Effectively Monitor SD-WAN and SASE Environments with ThousandEyes
 
Empowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintEmpowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership Blueprint
 
OpenShift Commons Paris - Choose Your Own Observability Adventure
OpenShift Commons Paris - Choose Your Own Observability AdventureOpenShift Commons Paris - Choose Your Own Observability Adventure
OpenShift Commons Paris - Choose Your Own Observability Adventure
 
UiPath Community: AI for UiPath Automation Developers
UiPath Community: AI for UiPath Automation DevelopersUiPath Community: AI for UiPath Automation Developers
UiPath Community: AI for UiPath Automation Developers
 
Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.
 
Meet the new FSP 3000 M-Flex800™
Meet the new FSP 3000 M-Flex800™Meet the new FSP 3000 M-Flex800™
Meet the new FSP 3000 M-Flex800™
 
Introduction to Quantum Computing
Introduction to Quantum ComputingIntroduction to Quantum Computing
Introduction to Quantum Computing
 
COMPUTER 10: Lesson 7 - File Storage and Online Collaboration
COMPUTER 10: Lesson 7 - File Storage and Online CollaborationCOMPUTER 10: Lesson 7 - File Storage and Online Collaboration
COMPUTER 10: Lesson 7 - File Storage and Online Collaboration
 
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
 
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...
Apres-Cyber - The Data Dilemma: Bridging Offensive Operations and Machine Lea...
 
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
 
9 Steps For Building Winning Founding Team
9 Steps For Building Winning Founding Team9 Steps For Building Winning Founding Team
9 Steps For Building Winning Founding Team
 
Basic Building Blocks of Internet of Things.
Basic Building Blocks of Internet of Things.Basic Building Blocks of Internet of Things.
Basic Building Blocks of Internet of Things.
 
Babel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxBabel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptx
 
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
 
Comparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioComparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and Istio
 
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdf
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdfUiPath Solutions Management Preview - Northern CA Chapter - March 22.pdf
UiPath Solutions Management Preview - Northern CA Chapter - March 22.pdf
 
Linked Data in Production: Moving Beyond Ontologies
Linked Data in Production: Moving Beyond OntologiesLinked Data in Production: Moving Beyond Ontologies
Linked Data in Production: Moving Beyond Ontologies
 
AI Fame Rush Review – Virtual Influencer Creation In Just Minutes
AI Fame Rush Review – Virtual Influencer Creation In Just MinutesAI Fame Rush Review – Virtual Influencer Creation In Just Minutes
AI Fame Rush Review – Virtual Influencer Creation In Just Minutes
 
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...
The Data Metaverse: Unpacking the Roles, Use Cases, and Tech Trends in Data a...
 

Structured Occurrence Network for provenance: talk for ipaw12 paper

  • 1. Modelling provenance using Structured Occurrence Networks Paolo Missier, Brian Randell, Maciej Koutny Newcastle University, UK IPAW’12 Santa Barbara, CA, June 2012 Thursday, June 21, 2012
  • 2. Petri Nets and Occurrence Nets Historically, Occurrence Nets have been used to define process semantics of Petri Nets [2] IPAW 2012 - P.Missier [2] Best, Eike, and Raymond Devillers. “Sequential and concurrent behaviour in Petri net theory.” Theoretical Computer Science 55, no. 1 (1987): 87-136. http://www.sciencedirect.com/science/article/pii/0304397587900909. 2 Thursday, June 21, 2012
  • 3. Occurrence Nets ON is about capturing causal relationships between events and conditions ON = (C, E, F ) with nodes C E and a flow relation F ⊆ (C ×E)∪(E × C) satisfying the following: (i) for every condition c there is at most one event e such that (e,c) ∈ F, and at most one event f such that (c,f) ∈ F; (ii) for every event e there is at least one condition c such that (c, e) ∈ F , and at least one condition d such that (e, d) ∈ F ; (iii) ON forms an acyclic graph and F + is a partial order relation (the relation PrecON = (F ◦ F)|C×C is acyclic) IPAW 2012 - P.Missier 3 Thursday, June 21, 2012
  • 4. Provenance and Occurrence Nets • "Provenance is defined as a record that • An Occurrence Net is an abstract record of describes the people, institutions, a single execution of some computing entities, and activities involved in system producing, influencing, or delivering a • Only information about causality and piece of data or a thing." [PROV] concurrency between events and visited local states is represented IPAW 2012 - P.Missier 4 Thursday, June 21, 2012
  • 5. Provenance and Occurrence Nets • "Provenance is defined as a record that • An Occurrence Net is an abstract record of describes the people, institutions, a single execution of some computing entities, and activities involved in system producing, influencing, or delivering a • Only information about causality and piece of data or a thing." [PROV] concurrency between events and visited local states is represented Data: The evolution of variable A as a ON: IPAW 2012 - P.Missier 4 Thursday, June 21, 2012
  • 6. Provenance and Occurrence Nets • "Provenance is defined as a record that • An Occurrence Net is an abstract record of describes the people, institutions, a single execution of some computing entities, and activities involved in system producing, influencing, or delivering a • Only information about causality and piece of data or a thing." [PROV] concurrency between events and visited local states is represented Data: The evolution of variable A as a ON: Agents: The evolution of Bob, the document editor: read drafted ready performed verified ptd paper internal to exp. results draft p1 memo IPAW 2012 - P.Missier read paper p2 4 Thursday, June 21, 2012
  • 7. From ON to Structured ON ON is an adequate starting point, but extensions are needed to represent the activity of complex systems • Structured Occurrence Nets provide these extensions as new relationships amongst multiple ONs [2] IPAW 2012 - P.Missier [2] Koutny, M., and B Randell. “Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and Analysis Techniques.” Fundamenta Informaticae 97 (2009). 5 Thursday, June 21, 2012
  • 8. From ON to Structured ON ON is an adequate starting point, but extensions are needed to represent the activity of complex systems • Structured Occurrence Nets provide these extensions as new relationships amongst multiple ONs [2] IPAW 2012 - P.Missier [2] Koutny, M., and B Randell. “Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and Analysis Techniques.” Fundamenta Informaticae 97 (2009). 5 Thursday, June 21, 2012
  • 9. Provenance modelling patterns using SON Main goal of this work: to explore the use of Structured Occurrence Nets as a formal model of provenance • Data is viewed as an evolving system • Agents are also evolving systems, thus their evolution is also captured • Uniform representation of Agents / Activity / Data interplay • Representation of multi-layered Provenance – eg:the provenance of a workflow run is underpinned by system-level provenance – SONs are suitable for modelling at multiple levels of abstraction IPAW 2012 - P.Missier Expected by-product of the investigation: suggest enhancements to the current SON model 6 Thursday, June 21, 2012
  • 10. Talk outline • C-SON: ON + communication relation – a provenance pattern to represent workflow patterns • T-SON: C-SON + temporal abstraction • (more abstraction relations omitted in the talk) • Modelling multi-layered provenance • Agents as evolving systems – provenance of agents IPAW 2012 - P.Missier 7 Thursday, June 21, 2012
  • 11. Communication SONs • Goal: to capture communication between ONs that otherwise proceed concurrently • by introducing a Communication relation amongst activities in two ONs – induces a partial order on the states and conditions of the two nets – must result in an acyclic net e1 cannot have happened after f1 e2, f2 must have happened simultaneously IPAW 2012 - P.Missier 8 Thursday, June 21, 2012
  • 12. Communication SONs • Goal: to capture communication between ONs that otherwise proceed concurrently • by introducing a Communication relation amongst activities in two ONs – induces a partial order on the states and conditions of the two nets – must result in an acyclic net e1 cannot have happened after f1 e2, f2 must have happened simultaneously IPAW 2012 - P.Missier 8 Thursday, June 21, 2012
  • 13. C-SON at work - a first provenance pattern • Each ON models one variable as a system. • The composed activity “A:=A+1; A:=A+B; B:=A+B” is represented as a SON composed of a pair of communicating ONs IPAW 2012 - P.Missier • The resulting SON captures a (partial) order of possible reads and writes leading to the final result 9 Thursday, June 21, 2012
  • 14. Workflow execution traces using C-SON X= 10 Y:= f(X) (a) (b) Program Execution specification instance f() <X,Z> := g(X,Y) Y = "200" g() X = 20 Z = "20" 10 r 10 r 10 w 20 X (c) SON representation of Execution trace f g Program execution IPAW 2012 - P.Missier w 20 w 200 r 200 Z Y 10 Thursday, June 21, 2012
  • 15. Temporal SON (T-SON) • Goal: to replace part of an ON with new “atomic” actions – a form of temporal abstraction – these new actions only appear atomic at one level of abstraction IPAW 2012 - P.Missier 11 Thursday, June 21, 2012
  • 16. T-SON in action: multi-layered provenance • Provenance of computed data naturally comes in layers: – program execution (incl. workflow controller) • system-level primitives, network protocols 10 r 10 t t 10 r 10 t X 10 fetch send 10 X f Program execution get compute t t t f IPAW 2012 - P.Missier Program execution Temporal abstraction used to hide/reveal lower-level details of both 12 systems and their interaction (i.e., reading from storage) Thursday, June 21, 2012
  • 17. T-SON: multi-layered provenance Additional unfolding: - assume f is a service call - reveal details of communication with an underlying service implementation 10 r 10 X f Program execution Service execution IPAW 2012 - P.Missier 13 Thursday, June 21, 2012
  • 18. T-SON: multi-layered provenance 10 r 10 t t t msg msg receive send 10 fetch send 10 Service X execution msg msg get receive prep send t t t f IPAW 2012 - P.Missier Program execution 14 Thursday, June 21, 2012
  • 19. Agents as evolving systems Alice and Bob collaborate on document editing An agent performs activities that account for changes in the state of the data • F is data (a file) • Data and agents are modelled as systems • Each system is a SON • Communication abstraction used to synchronize events across different IPAW 2012 - P.Missier systems • Bob.draft → F.write, F.read → Alice.”read draft” etc. • For example, Bob in the state b2 is unaware of Alice’s feedback • Bob in state b3 has read Alice’s feedback 15 Thursday, June 21, 2012
  • 20. Agents as evolving systems • Tracking the state of agents is important – we know that it is the “version” of Bob that is aware of Alice’s comment that is responsible for the latest edit Below: Bob’s edits to the document do not take account of Alice’s comments ptd draft b2 edit b4 Bob w f1 r f1 w f2 r f2 w f3 IPAW 2012 - P.Missier F read leave a1 a2 draft comments 16 Alice Thursday, June 21, 2012
  • 21. Summary • SONs extend well-known Occurrence Nets • Simple graphical notation with formal grounding – amenable to various types of analysis • Appealing for capturing system evolution and inter-system communication • Accommodates multiple levels of abstraction • Evolution traces of Data, Agents and Activities provenance queried seamlessly • Some software tool support (in progress), more work needed here • Feedback for customizations of the SON model itself! IPAW 2012 - P.Missier 17 Thursday, June 21, 2012
  • 22. Selected References •  V. Khomenko, M. Koutny, A. Yakovlev: Logic Synthesis for Asynchronous Circuits Based on Petri Net Unfoldings and Incremental SAT. Fundamenta Informaticae 70, 2006. •  http://www.cs.ncl.ac.uk/publications/inproceedings/papers/749.pdf •  M. Koutny, B. Randell: Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and Analysis Techniques. Fundamenta Informaticae 97, 2009. •  http://www.cs.ncl.ac.uk/publications/trs/papers/1162.pdf •  B. Li, M. Koutny: Verification and Simulation Tool for Communication Structured Occurrence Nets. CS-TR, Newcastle University, (to appear). •  P.M. Merlin and B. Randell: State Restoration in Distributed Systems. Proc. FTCS-8, 1978. •  http://www.cs.ncl.ac.uk/publications/inproceedings/papers/347.pdf •  I. Poliakov, V. Khomenko, A. Yakovlev: Workcraft - A Framework for Interpreted Graph Models. LNCS 5606, 2009. •  B. Randell, M. Koutny: Failures: Their Definition, Modelling and Analysis. LNCS 4711, 2007. •  http://www.cs.ncl.ac.uk/publications/trs/papers/994.pdf IPAW 2012 - P.Missier •  B. Randell, M. Koutny: Structured Occurrence Nets: Incomplete, Contradictory and Uncertain Failure Evidence. CS-TR 1170, Newcastle University, 2009. •  http://www.cs.ncl.ac.uk/publications/trs/papers/1170.pdf 18 Martinique, Jan. 2012 24 Thursday, June 21, 2012
  • 23. IPAW 2012 - P.Missier EXTRA material 19 Thursday, June 21, 2012
  • 24. SON provenance and PROV read b2 b3 edit b4 feedback Bob (a) f2 r f2 r f2 w f3 F used wasGeneratedBy f2 edit wa f3 (b) sG en era used wasAssociatedWith ted By read wasGeneratedBy feedback Bob_b3 wasDerivedFrom Bob_b4 IPAW 2012 - P.Missier wasAssociatedWith wasDerivedFrom Bob_b2 20 Thursday, June 21, 2012
  • 25. T-SON and finite-duration activities In Occurrence Nets, events (activities) are instantaneous. Using temporal abstraction one can add a time duration to activities [s,e] Activity f f with duration [s,e] t t t t t t s e c duration interval of f c t1 t2 tn Time IPAW 2012 - P.Missier 21 Thursday, June 21, 2012
  • 26. SON -- behavioural abstraction • Insight: ‘system’ and ‘state’ are not separate concepts • The same graph node may be used to represent either a state or a system, at different levels of abstraction Key idea of Structured Occurrence Nets: • multiple ONs, each portraying a system/state at some level of abstraction IPAW 2012 - P.Missier • associations amongst the ONs are then established by means of new relation types 22 Thursday, June 21, 2012
  • 27. B-abstraction in use – An application of behavioural abstraction -- state/system duality – Bob’s state b1 expands into a system’s activities (b1) – the expansion provides additional insight into Bob’s “knowledge level” / “preparedness” prior to drafting the document IPAW 2012 - P.Missier 23 Bob’s state as a system Thursday, June 21, 2012
  • 28. Finding good abstractions - cuts in ON and SON (a) (d) (b) (e) IPAW 2012 - P.Missier (c) 24 Thursday, June 21, 2012