Instance Deadlock: A Mystery Behind Frozen Programs

Abstract

In the talk we will discuss the event-driven reactive programs and systems, which does not deadlock for one instance, but because of shared resources, can deadlock for several instances. We will focus on event-driven programs, where instances have a correct finish, and resources can be used by single instances, but can neither be destroyed nor created by instances. Typical examples include workflow processes, where each case creates an instance of the process and instances share resources used to execute single activities. Formally, we model such event-driven programs and systems by workflow nets, enriched by so called static places, known from the literature as resource constrained workflow nets (rcwf-nets). We investigate, whether an rcwf-net, which is sound for a single instance is sound for multiple instances (dynamically sound) or whether it contains an instance deadlock for a number of instances. We show that the detection of instance deadlock and the dynamic soundness of rcwf-nets is decidable by transforming the problem to bounded place/transition Petri nets.

14:00-15:00 Wednesday, 23 June 2010