Title: Differencing Workflow Runs
Zhuowei Bao, University of Pennsylvania

Abstract: We study the problem of differencing two workflow runs of
the same specification, which is represented as a control and
data flow network with designated start and termination
nodes. While in general this problem is NP-hard, an analysis
of real workflows shows that their structure can be captured
as a series-parallel graph overlaid with well-nested forking
and looping. For this natural restriction, we present efficient,
polynomial-time algorithms for differencing workflow
runs of the same specification.

Our contributions are three-fold: First, we present a model
of workflows that is sufficiently general to capture workflows
that we have encountered in practice and collected from articles
and sample workflows on the web. Second, for this
model of workflows we present efficient, polynomial-time algorithms
for differencing workflow runs. Third, we provide
experimental results demonstrating the scalability of our approach
using collected, real workflows and increasingly complex
runs, and argue that the edit scripts are useful for users.