Petri Nets Based Coordination Mechanisms

Alberto B. Raposo, Léo P. Magalhães and Ivan L. M. Ricarte
DCA - FEEC - Unicamp

The coordination of interdependencies among activities in collaborative environments is a very important and difficult task. In this page we present a set of coordination mechanisms for the specification and control of interaction among collaborative activities. To model these mechanisms, we use Petri nets (PNs), which have proven to be an adequate approach to evaluate the behavior of a computer supported collaborative system before its implementation.

Introduction
Temporal Dependencies
Resource Management Dependencies
Conclusion
References

Introduction

This work intends to provide mechanisms to manage interdependencies between tasks in a collaborative environment. In order to achieve this goal, we propose a library of PN-based primitives to model coordination mechanisms for several possible interdependencies. Each coordination mechanism ensures that the associated dependency will not be violated. The idea is that designers be concerned only with the definition of tasks and interdependencies among them, and not with the management of those dependencies, since mechanisms to manage them are provided by the library.

In the proposed schema, an environment is modeled in two distinct levels, workflow and coordination. In the workflow level, each workflow is modeled separately by a PN, in which tasks are represented by transitions, and that may include “traditional” workflow connections (splits and joins) and routings (parallel routing, conditional routing, etc). Also in this level, it is necessary to establish the interdependencies between tasks. The coordination level is built under the workflow level by the expansion of interdependent tasks according to a model defined in [1] and the insertion of corresponding coordination mechanisms between them.

In the passage from the workflow to the coordination level, each task (a transition in the workflow level) which has a dependency with another is hierarchically expanded in a system with five transitions (ta, tb, ti, tf and tc) and four places (P1, P2, P3 and P4), as proposed by van der Aalst et al [1]. As shown in Figure 1, attached to each expanded task there are also five places that represent the interaction with the resource manager and the agent that executes the task. The places request_resource, assigned_resource and release_resource connect the task with the resource manager. The places start_task and finish_task connect the task with the agent that performs it, respectively indicating the beginning and the end of the task’s execution.

Figure 1: An expanded task in the coordination level.

Based on the model of Figure 1, it is possible to conclude that a task can be connected with two sub-nets: a resource manager (which has request_resource and release_resource as input places and assigned_resource as output place), and another representing the logistics of the task (which has start_task as input place and finish_task as output place).

The library recognizes two general classes of interdependencies: temporal and resource management dependencies. The former is related to the logistics sub-net cited above, while the latter is related to the resource manager sub-net.
The main goal of the library is to construct the coordination level from the workflow level, because once the interdependencies are defined, the expansion of tasks according to the model of Figure 1 and the insertion of coordination mechanisms can be automated.

In the following sections we present the set of mechanisms of the library.

Temporal Dependencies

Temporal dependencies establish the execution order of "disconnected" tasks. Coordination mechanisms associated to this kind of dependency have start_task as input place and finish_task as output place (Figure 1).

In order to define the possible temporal dependencies between tasks, we refer to a classic temporal logic paper by J. F. Allen [2]. In this paper, Allen states that there is a set of primitive and mutually exclusive relations that can be applied to time intervals. These relations are illustrated in Figure 2.

	Time ->
X equals Y	XXXXXX YYYYYY
X starts Y	XXX YYYYYY
X finishes Y	XXXX YYYYYY
X before Y	XXXX YYY
X meets Y	XXXXYYYY
X overlaps Y	XXXX YYYYY
X during Y	XXX YYYYYYY

Figure 2: Allen's temporal relations.

Allen defined possible relations between time intervals. We adapted these relations for the definition of temporal dependencies between tasks in collaborative environments, adding a couple of new relations and a few variations of those originally proposed. The following temporal dependencies are defined in the library for two tasks (X and Y):

Equals: [x1, x2] equals [y1, y2] iff x1 = y1 and x2 = y2. Two tasks ocurring in the same time interval.
StartsA: [x1, x2] startsA [y1, y2] iff x1 = y1 and x2 < y2. Both tasks must start together and the first (X) must finish before.
StartsB: [x1, x2] startsB [y1, y2] iff x1 = y1. Both tasks must start together.
FinishesA: [x1, x2] finishesA [y1, y2] iff x2 = y2 and x1 > y1. Both tasks must finish together and X must start after Y.
FinishesB: [x1, x2] finishesB [y1, y2] iff x2 = y2. Both tasks must finish together.
AfterA: [x1,x2] afterA [y1, y2] iff y2 < x1. After each execution of Y, X can occur only once.
AfterB: [x1,x2] afterB [y1, y2] iff y2 < x1. X can happen several times after the execution of Y.
Before: [x1, x2] before [y1, y2] iff x2 < y1. Y does not wait for X. If Y occurs, X cannot be executed anymore.
Meets: [x1, x2] meets (y1, y2] iff x2 = y1. Y must start immediately after X.
OverlapsA: [x1, x2] overlapsA [y1, y2] iff x1 < y1 < x2 < y2. Y must start before the end of X, which must finish before Y.
OverlapsB: [x1, x2] overlapsB [y1, y2] iff x1 < y1 < x2 . Y must start before the end of X.
DuringA: [x1, x2] duringA [y1, y2] iff x1 > y1 and x2 < y2. X can happen only once during the execution of Y.
DuringB: [x1, x2] duringB [y1, y2] iff x1 > y1 and x2 < y2. X can happen several times during the execution of Y.

Click on the name of each dependency above to see the associated coordination mechanisms modeled in Petri nets and high level Petri nets.

Resource Management Dependencies

The coordination mechanisms for resource management are complementary to those presented in the previous section and can be used in parallel to them. This kind of coordination mechanism deals with the distribution of resources among the tasks.

We define three basic coordination mechanisms for resource management:

Sharing: a limited number of resources needs to be shared among several tasks.
Simultaneity: a resource is available only if a certain number of tasks requests it simultaneously.
Volatility: indicates whether, after the use, the resource is available again.

The library also defines composite mechanisms from the basic ones discussed above.

Sharing M + simultaneity N: represents the situation in which up to M groups of N tasks can share a resource.

Sharing M + volatility N: situation in which up to M tasks can share the resource, which can be used N times.

Simultaneity M + volatility N: the resource is assigned to groups of M tasks simultaneously. This can be done N times.

Sharing M + simultaneity N + volatility Q: up to M groups of N tasks can share a resource. This can be done Q times.

Differently from temporal dependencies, resource management dependencies are not binary relations. It is possible, for example, that more than two tasks share a resource. Moreover, each of the above mechanisms requires a parameter indicating the number of resources to be shared, the number of tasks that must request a resource simultaneously, or the number of times a resource can be used (volatility).

Conclusion

Petri Nets, due to their support for modeling, simulation, and analysis, has proven to be a powerful tool for verifying the correctness and validating the effectiveness of collaborative environments before their actual implementation. Furthermore, the hierarchical description of PNs showed an appropriate way to define the coordination structure in different abstraction levels (workflow and coordination levels).

It should be pointed out that there is a clear separation between the defined interdependencies and the PN based coordination mechanisms. Non-PN based applications can follow the ideas presented here separating activities from interdependencies and using appropriate coordination mechanisms.

The library presented in this paper does not claim to be complete. We believe it would be very difficult to establish a framework of all possible interdependencies between tasks. For that reason, we preferred to opt for extensibility instead of completeness. When a new kind of interdependency arises, a corresponding coordination mechanism can be modeled and inserted to the library.

Finally, we reinforce our belief that the coordination of interdependent tasks in collaborative environments is a problem that should be addressed to ensure the effectiveness of the cooperation among organizations. The separation between activities and dependencies, and the utilization of reusable coordination mechanisms are steps towards this goal.

Acknowledgements. The first author is sponsored by FAPESP (Foundation for Research Support of the State of São Paulo), process n. 96/06288-9. This work has also been supported by the SAPIENS project (FAPESP, process n. 97/12807-1). We also would like to thank the School of Electrical and Computer Engineering (FEEC) – UNICAMP for the expressive support granted to this research.

References

[1] van der Aalst, W M P, van Hee, K M and Houben, G J Modelling and analysing workflow using a Petri-net based approach. Proc. 2nd Workshop on Computer-Supported Cooperative Work, Petri nets and related formalisms (1994) 31-50

[2] Allen, J F Towards a General Theory of Action and Time, Artificial Intelligence, 23 (1984) 123-154