The ability to cope with change is one of the biggest challenges companies are facing today. Methods to increase business agility, such as outsourcing or off-shoring of non-core parts of the business are practiced already and will continue to play an important role in the future. A change in business however always means to also change the underlying IT infrastructure, which therefore needs to be designed in a way to be able to support flexible re-arrangement of its support for business operations. IT systems today are integrated using so called workflow management systems, that execute a business process in the form of örchestrations" of the individual applications used for carrying out business functions.

These processes today are enacted centrally, i.e. the workflow engine acts as a central point of control governing the lifecycle of all activities of a process. This way of enacting processes has certain drawbacks, revealed when executing change such as outsourcing parts of a process. Using state-of-the-art workflow engines, this results in development of process partitions that need to be maintained separately and were not created because the original business goal has changed, but because the used workflow engine does not allow for flexible deployment of a single process model to multiple process engines. This thesis proposes a fundamentally new execution model for decentralized workflow enactment that does not have these drawbacks. It allows for flexible deployment of arbitrary partitions of the original workflow graph, thus supporting change at the level of business processes avoiding the need to change a process solely because the underlying IT infrastructure has changed.

The contributions of this thesis are: an in-depth analysis of differences between tuplespace-based and message-oriented middleware systems, a Petri net based formalization of tuplespace interactions called Executable Workflow Nets (EWFN), a fully-fledged Petri net formalization of WS-BPEL 2.0, a method and algorithm to execute Petri nets using tuplespaces and an architecture and implementation of the "coordination kernel" of a decentralized workflow engine that executes Petri net based workflows.