Negotiations have recently been introduced as a model of concurrency with multi-party negotiation atoms as primitive. This paper studies the relation between negotiations and Petri nets. In particular, we show that each negotiation can be translated into a 1-safe labelled Petri net with equivalent behaviour. In the general case, this Petri net is exponentially larger than the negotiation. For deterministic negotiations however, the corresponding Petri has linear size compared to the negotiation, and it enjoys the free-choice property. We show that for this class the negotiation is sound if and only if the corresponding Petri net is sound. Finally, we have a look at the converse direction; given a Petri net; can we find a corresponding negotiation?
Distributed negotiations have been identified as a paradigm for process
interaction since some decades, in particular in the context of multi-agent systems. A
distributed negotiation is based on a set of agents that communicate with each
other to eventually reach a common decision. It can be viewed as a protocol
with atomic negotiations as smallest elements. Multiparty negotiations can
employ more than two agents, both in the entire negotiation and in its atoms. A
natural way to formally model distributed negotiations is to model the behaviour
of the agents separately and then to model the communication between agents
by composition of these agent models. Petri nets and related process languages
have been used with this aim, see e.g. [
In [
Our previous contributions [
The paper is organised as follows. Section 2 repeats the syntax and semantics of negotiations. Section 3 provides the translation to Petri nets with the same behaviour. Section 4 discusses properties of these Petri nets. In Section 5 we show that Petri nets enjoying these properties can be translated back to negotiations, this way characterizing a class of Petri nets representable by negotiations. 2
We recall the main definitions of [
Internal states of agents and their transformers won’t play an important role in this contribution. As will become clear later, states do not influence behaviour in negotiations, i.e., we can consider the control flow and data aspects separately. For the Petri net translation to be defined, local states and their transformers can be modelled by means of token colours and transition modes, respectively, i.e. by means of Coloured Petri nets. These Coloured Petri nets are without guards, because guards restrict transition occurrences by regarding data values.
Definition 1. An atomic negotiation, or just an atom, over a set of agents A is a triple n = (P, R, δ), where P ⊆ A is a nonempty set of parties or participants of n, R is a finite, nonempty set ( results), and δ is a mapping assigning to each result r ∈ R a P -transformer δ(r).
In the sequel, Pn, Rn and δn will denote the components of an atom n. For each result r ∈ Rn, the pair (n, r) is called an outcome. The difference between results and outcomes is that the same result can belong to different atoms whereas the sets of outcomes are pairwise disjoint. If we choose disjoint sets for the respective sets of results then we do not have to distinguish results and outcomes.
If the states of the agents before an atomic negotiation n are given by a tuple q and the result of the negotiation is r, then the agents change their states to q0 for some (q, q0) ∈ δn(r). Only the parties of n can change their internal states. However, it is not required that a Pn-transformer δn(r) actually changes the states of all agents in Pn. Each result r ∈ Rn is possible, independent of the previous internal states of the parties of n.
As a simple example, consider an atomic negotiation nFD with parties F (Father) and D (teenage Daughter). The goal of the negotiation is to determine whether D can go to a party, and the time (a number between 8 and 12) at which she must return home. The possible results are {yes, no, ask_mother}. Both sets QF and QD contain a state angry plus a state t for every time T1 ≤ t ≤ T2 in a given interval [T1, T2]. The transformer δnFD includes δnFD (yes) = { ((tf , td), (t, t)) | tf ≤ t ≤ td ∨ td ≤ t ≤ tf }
δnFD (no) = { ((tf , td), (angry , angry )) } δnFD (ask_mother) = { ((tf , td), (tf , td)) } where tf and td are variables used to denote that F is in state tf 6= angry and D in state td 6= angry before engaging in the negotiation atom nFD. Moreover, if one of the local states before the negotiation atom was angry, then δnFD specifies that both agents will be angry after executing the atom.
If both parties are not angry and the result is yes, then F and D agree on a time t which is not earlier and not later than both suggested times. If it is no, then there is a quarrel and both parties get angry. If it is ask_mother, then the parties keep their previous times. 2.2
If the result of the atomic negotiation above is ask_mother, then nFD is followed by a second atomic negotiation nDM between D and M (Mother). The combined negotiation is the composition of nFD and nDM, where the possible internal states of M are the same as those of F and D, and nDM is a “copy” of nFD, but without the ask_mother result. In order to compose atomic negotiations, we add a transition function X that assigns to every triple (n, a, r) consisting of an atom n, a participant a of n, and a result r of n a set X(n, a, r) of atoms. Intuitively, this M
st nDM D M
af y,n y,n y,n n0 F
st nFD F is the set of atomic negotiations agent a is ready to engage in after the atom n, if the result of n is r.
Definition 2. Given a finite set of agents A and a finite set of atoms N over A, let T (N ) denote the set of triples (n, a, r) such that n ∈ N , a ∈ Pn, and r ∈ Rn. A (distributed) negotiation is a tuple N = (N, n0, nf , X), where n0, nf ∈ N are the initial and final atoms, and X : T (N ) → 2N is the transition function. Further, N satisfies the following properties: (1) every agent of A participates in both n0 and nf ; (2) for every (n, a, r) ∈ T (N ): X(n, a, r) = ∅ iff n = nf .
The graph associated with N has vertices N and edges
{(n, n0) ∈ N × N | ∃ (n, a, r) ∈ T (N ) : n0 ∈ X(n, a, r)}.
The initial and final atoms mark the beginning and the end of the negotiation (and sometimes this is their only role). We may have n0 = nf . In this case, due to (2), N = {n0}, i.e, the negotiation has only one single atom. Notice that nf has, as all other atoms, at least one result end ∈ Rnf . 2.3
Negotiations are graphically represented as shown in Figure 1. For each atom n ∈ N we draw a bar; for each participant a of Pn we draw a circle on the bar, called a port. For each (n, a, r) ∈ T (N ) with n 6= nf , a hyperarc leads from the port of a in n to all the ports of a in the atoms of X(n, a, r), labelled by the result r. Figure 1 shows on the left the graphical representation of a negotiation where Father (F), Daughter (D) and Mother (M) are the involved agents. After the initial atom n0, which has only one possible result st (start), the negotiation atoms sketched above take place. Notice that possibly Father and Daughter come to an agreement without involving Mother. So the agents of a negotiation can be viewed as potential participants, which necessarily participate only in the initial and the final atom. Instead of multiple (hyper)arcs connecting the same input port to the same output ports we draw a single (hyper)arc with multiple labels. In the figure, we write y for yes, n for no, and am for ask mother. Since nf has no outgoing arc, the results of nf do not appear in the graphical representation.
The negotiation on the right (ignore the black dots on the arcs for the moment) is the ping-pong negotiation, well-known in every family. The nDM atom has now an extra result ask_father (af), and Daughter can be sent back and forth between Mother and Father. After each round, D “negotiates with herself” (atom nD) with possible outcomes continue (c) and give up (gu). 2.4
A marking of a negotiation N = (N, n0, nf , X) is a mapping x : A → 2N . Intuitively, x(a) is the set of atoms that agent a is currently ready to engage in next. The initial and final markings, denoted by x0 and xf , are given by x0(a) = {n0} and xf (a) = ∅ for every a ∈ A. Obviously, the set of markings is finite.
A marking x enables an atom n if n ∈ x(a) for every a ∈ Pn, i.e., if every agent that participates in n is currently ready to engage in n. If x enables n, then n can take place and its participants agree on a result r; we say that the outcome (n, r) occurs. The occurrence of (n, r) produces a next marking x0 given by x0(a) = X(n, a, r) for every a ∈ Pn, and x0(a) = x(a) for every a ∈ A \ Pn. We write x −−(n−,−r→)σ x0 to denote this, and call it a small step.
We write x1 −→ to denote that there is a sequence
(n1,r1) (n2,r2) (nk−1,rk−1) (nk,rk) x1 −−−−−→ x2 −−−−−→ · · · −−−−−−−−→ xk −−−−−→ xk+1 · · · σ of small steps such that σ = (n1, r1) . . . (nk, rk) . . .. If x1 −→ , then σ is an occurrence sequence from the marking x1, and x1 enables σ. If σ is finite, then we write x1 −→σ xk+1 and say that xk+1 is reachable from x1. If x1 is the initial marking then we call σ initial occurrence sequence. If moreover xk+1 is the final marking xf , then σ is a large step.
As a consequence of this definition, for each agent a, x(a) is always either {n0} or equals X(n, a, r) for some outcome (n, r). The marking xf can only be reached by the occurrence of (nf , end) (end being a possible result of nf ), and it does not enable any atom.
Reachable markings can be graphically represented by placing tokens (black dots) on the forking points of the hyperarcs (or in the middle of an arc). Thus, both the initial marking and the final marking are represented by no tokens, and all other reachable markings are represented by exactly one token per agent.
Figure 1 shows on the right the marking in which Father is ready to engage in the atomic negotiations nFD and nf , Daughter is only ready to engage in nFD, and Mother is ready to engage in both nDM and nf .
As mentioned before, the enabledness of an atom does not depend on the internal states of the agents involved; it suffices that all agents are ready to engage in this atom, no matter which internal states they have. Moreover, each result of the atom is possible, independent from the internal states. A given result then determines a state transformer and thus possible next states. 2.5
As known from any family, an occurrence sequence of a negotiation can be arbitrarily long (see the ping-pong negotiation above). Therefore, the set of possible occurrence sequences can be infinite. Since we have markings and steps, an obvious way to describe behaviour with finite means is by reachability graphs: Definition 3. The reachability graph of a negotiation N has all markings reachable from x0 as vertices, and an arc leading from x to x0 and annotated by (n, r) whenever x −−(n−,−r→) x0. The initial marking x0 is the distinguished initial vertex.
Generally, atoms with disjoint sets of parties can proceed concurrently, whereas atoms sharing a party cannot. Formally, if two outcomes (n1, r1) and (n2, r2) are enabled by the same reachable marking x and Pn1 ∩Pn2 = ∅ then the outcomes can occur concurrently. The condition Pn1 ∩ Pn2 = ∅ is also necessary for concurrent occurrences of outcomes because, in our model, a single agent cannot be engaged concurrently in two different atoms, and because two state transformers cannot operate concurrently on the local state of an agent. Thus concurrency between outcomes depends only on the involved atoms (and their parties) and not on the results.
Concurrency is formally captured by the concurrent step reachability graph, defined next. A concurrent step enabled at a reachable marking x is a nonempty set of pairwise concurrent outcomes, each of them enabled by x. It is immediate to see that all the outcomes of a concurrent step can be executed subsequently in arbitrary order and that the marking finally reached does not depend on the chosen order. We call this marking reached by the concurrent step. Definition 4. The concurrent step reachability graph of a negotiation N has all markings reachable from x0 as vertices. An arc, annotated by a nonempty set of outcomes, leads from x to x0 whenever the outcomes of this set are pairwise concurrent and the concurrent step leads from x to x0. Again, x0 is the distinguished initial vertex. 3
We assume that the reader is acquainted with (low-level) initially marked Petri nets, the occurrence rule, reachable markings, liveness, and the graphical representation of nets as directed graphs. For each place, there are directed arcs from all input transitions to the place and directed arcs from the place to all output n0 F
st nFD F transitions. Input places and output places of transitions are defined analogously. A labelled Petri net is a Petri net with a labelling function λ, mapping transitions to some set of labels. Graphically, the label λ(t) of a transition t is depicted as an annotation of t. The semantics of negotiations uses many notions from Petri net theory. In this section, we provide a translation and begin with an example.
Figure 2 shows on the right the net for the negotiation shown on the left (which was also shown in Figure 1). Since the number of places of the net equals the number of ports of the negotiation, one might assume that the relation between ports and places is a simple one-to-one mapping. Moreover, the transitions of the net have an obvious relation to the outcomes, i.e., to the results of the negotiation atoms (if the two end-transitions are ignored).
Now we have a look at the two end-transitions of the Petri net. The left transition refers to the last result of the negotiation’s occurrence sequence (n0, st), (nFD, am), (nDM, y), (nf , end), where end is a result of nf . The right transition refers to the last result of the occurrence sequence (n0, st), (nFD, y), (nf , end). Hence, roughly speaking, the left transition refers to the left branch of the (only) proper hyperarc of the graphical representation of the negotiation, and the right transition refers to the right branch. ...
a1 ... n
y ...
ak ...
n ak naccept nreject
For a negotiation with more than one proper hyperarc, each occurrence sequence can involve a particular branching of a hyperarc (moreover, an atom can occur more than once, leading to different branches of the same hyperarc). For k hyperarcs with binary branching, this results in 2k possible patterns. As can be seen in the following example, this can result in exponentially many transitions of the associated Petri net.
Figure 3 shows a class of negotiations with parameter k, involving agents a1, . . . , ak. These negotiations represent a distributed voting process. Each agent votes with possible outcome yes or no (one-party-negotiations). For each yesoutcome there are two possible next atoms, naccept and nreject, whereas for each no-outcome nreject is the only possibility. So the atom naccept is only enabled if all agents vote yes, while the atom nreject is always enabled when all agents have voted.
A Petri net representing this behaviour necessarily has to distinguish the k possible yes-outcomes and no-outcomes, because final acceptance is only possible if all agents have accepted. So we need 2·k corresponding places, k for acceptance and k for rejection. When all agents came to a result, one of 2k possible markings is reached. Only for one of these markings (all agents accepted), final acceptance is possible, and this will be represented by one transition. For each of the 2k − 1 alternative constellations, we need a separate transition to remove the tokens and come to final rejection. So we end up with 2k transitions. We associate with a negotiation N = (N, n0, nf , X) a (labelled) Petri net. The places of this net are, for each atom n except nf , the pairs [a, S] such that a ∈ Pn, r ∈ Rn, and X(n, a, r) = S, plus, for each a ∈ A, the pair [a, {n0}]. Observe that the number of places is linear in the size of N (which might exceed |N | significantly, because, for each n in N , for each a in Pn and for each result r ∈ Rn we have a set of possible successor negotiations in X). In the sequel (and in the figures) we write [a, n] instead of [a, {n}]. The initial marking assigns one token to each place [a, {n0}] and no token to all other places.
The net has a set of transitions T (n, r) for each outcome (n, r). An input place of a transition in T (n, r) reflects that a party of negotiation n is actually ready to engage in n (and possibly in other atoms as well). For a single agent, there might be more than one such place, resulting in several transitions. Each transition in T (n, r) has input places referring to all involved parties, which results in a transition for each combination of respective input places.
Formally, let Pn = {a1, . . . , ak}. T (n, r) contains a transition [n, r, L] for every tuple L = ([a1, S1], . . . , [ak, Sk]) such that n ∈ S1 ∩ . . . ∩ Sk. The set of input places of [n, r, L] is {[a1, S1], . . . , [ak, Sk]}, and its set of output places is {[a1, X(n, a1, r)], . . . , [ak, X(n, ak, r)]}. All transitions of the set T (n, r) are labelled by the outcome (n, r). They all have the same output places. Moreover, they have the same number of input and output places, both of them equal to the number of parties of n.
For the negotiation on the left of Figure 2, we get seven sets of transitions: T (n0, st), T (nFD, y), T (nFD, n), T (nFD, am), T (nDM, y), T (nDM, n), and T (nf , end). All of them are singletons, with the exception of T (nf , end), which contains the two transitions shown at the bottom of the figure. In the figure, we annotate transitions only by results r instead of outcomes (n, r). Notice that here we assume a unique result end of nf .
Proposition 1. For each atom n 6= nf , each transition labelled by (n, r) has exactly one input place [a, X] for each agent a ∈ Pn, and exactly one output place [a, Y ] for each agent a ∈ Pn. Transitions labelled by (nf , end) have no output places.
Corollary 1. For each agent a, the number of tokens on places [a, X] never increases. Since this number is one initially, it is at most one for each reachable marking. tu Corollary 2. The net associated with a negotiation is 1-safe, i.e., no reachable marking assigns more than one token to a place.
Lemma 1. The net associated with a negotiation is deterministic, i.e., no reachable marking enables two distinct transitions with the same label. Proof. A transition labelled by (n, r) has an input place for each participant of n. Two equally labelled transitions cannot have identical sets of input places by construction. Hence, for at least one agent a there is a place [a, X] which is input place of one of the transitions and a distinct place [a, Y ] which is input place of the other transition. Since, by Corollary 1, each reachable marking marks at most one of these two places, each reachable marking enables at most one of the transitions. tu
The (sequential) behaviour of a labelled Petri net is represented by its reachability graph: Definition 5. The reachability graph of a Petri net has all reachable markings m as vertices, an arc annotated by t leading from m to m0 when m enables transition t and the occurrence of t leads to m0, and a distinguished initial marking m0. The label reachability graph of a labelled Petri net is obtained from its reachability graph by replacing each transition by its label.
In terms of reachability graphs, a labelled Petri net is deterministic if and only if its label reachability graph has no vertex with two outgoing edges which carry the same label. An occurrence sequence of a deterministic labelled Petri net is fully determined by the sequence of transition labels, as shown in the following proposition, and so is the sequence of markings reached.
For a labelling function λ and an occurrence sequence σ = t1 t2 t3 . . ., we write λ(σ) for the sequence of labels λ(t1) λ(t2) λ(t3) . . . in the sequel. Proposition 2. Let σ1 and σ2 be two finite, initially enabled occurrence sequences of a deterministic labelled Petri net with labelling function λ. Let m1 be the marking reached by σ1, and let m2 be the marking reached by σ2. If λ(σ1) = λ(σ2) then m1 = m2. tu 3.3
In this subsection, we will employ the usual notion of isomorphism between reachability graphs: Definition 6. Two reachability graphs are isomorphic if there exists a bijective mapping ϕ between their sets of vertices, mapping the initial vertex of the first graph to the initial vertex of the second graph, such that there is an edge from u to v labelled by some t in the first graph if and only if there is an edge from λ(u) to λ(v) labelled by t in the second graph.
Reachability graph isomorphism is a very strong behavioral equivalence notion for sequential behaviour. If moreover the concurrent step reachability graphs of two models are isomorphic, then also the concurrent behaviour of the systems coincide. We will show the existence of both isomorphisms between negotiations and associated Petri nets.
Proposition 3. The reachability graph of a negotiation and the label reachability graph of the associated labelled Petri net are isomorphic.
Proof. (Sketch). We interpret a token on a place [a, {n1, . . . , nk}] on the negotiation side as “agent a is ready to engage in the atoms of the set {n1, . . . , nk}”. It is immediate to see that this holds initially. By construction of the Petri net, a small step (n, r) of the negotiation is mimicked by an occurrence of a transition of the set T (n, r), and hence by a transition labelled by (n, r). By construction, the marking of the negotiation reached by the occurrence of the outcome corresponds to the marking of the net reached by the occurrence of the transition.
For comparing the concurrent behaviour of negotiations and associated labelled Petri nets, we have to define concurrent enabledness of transitions. This is easy in our setting, because the considered nets are 1-safe. Definition 7. Two transitions t and t0 of a 1-safe Petri net are concurrently enabled at a reachable marking m if m enables both t and t0 and if moreover t and t0 have no common input place.
Concurrent behaviour is captured by the concurrent step reachability graph and, for labelled Petri nets, by its label version. In the following definition, a set of transitions is said to be concurrently enabled if any two distinct transitions in this set are concurrently enabled.
Definition 8. The concurrent step reachability graph of a Petri net has all reachable markings m as vertices, a distinguished initial marking m0 and an arc labelled by U leading from m to m0 when m concurrently enables a nonempty set U of transition and the occurrence of all transitions of U (in any order) leads from m to m0.
The label concurrent step reachability graph of a labelled Petri net is obtained from its concurrent step reachability graph by replacing each set of transitions by the multiset of its labels.
Fortunately, in our setting two equally labelled transitions are never enabled concurrently, so that the labels of concurrent steps will never be proper multisets, but just sets.
Lemma 2. If two outcomes (n, r) and (n0, r0) of a negotiation are concurrently enabled at a marking reached by an initial occurrence sequence σ, then there is an initially enabled occurrence sequence μ of the associated labelled Petri net such that λ(μ) = σ and the marking reached by μ concurrently enables two transitions labelled by (n, r) and (n0, r0) respectively.
Conversely, if a marking of the (λ-)labelled Petri net reached by an occurrence sequence μ concurrently enables two transitions t and t0, then the marking of the negotiation reached by λ(μ) concurrently enables the two outcomes λ(t) and λ(t0). Proof. (Sketch). By construction of the Petri net, a transition t has an input place [a, X] only if λ(t) = (n, r) for an agent a ∈ Pn. Assume that two enabled transitions are not concurrent. Then they share an input place [a, X] only if their labels refer to two outcomes (n, r) and (n0, r0) such that a ∈ Pn and a ∈ Pn0 . So Pn ∩ Pn0 6= ∅, and thus the two outcomes are not concurrent.
Conversely, if two outcomes (n, r) and (n0, r0) are enabled but not concurrent, then some agent a belongs to both Pn and Pn0 . In the Petri net, each transition labelled by (n, r) or by (n0, r0) has an input place [a, X]. Since each reachable marking marks only one place [a, X] by Corollary 1, two distinct enabled transitions labelled by (n, r) or by (n0, r0) share this marked input place, whence they are not concurrent.
Corollary 3. The concurrent step reachability graph of a negotiation and the label concurrent step reachability graph of its associated Petri net are isomorphic. reject1 n ...
y a1
.n.0. a1
... accept ... nf ak ak y rejectk 4 4.1
The reader possibly finds unsatisfactory that the negotiation given in Figure 3 can reject even when all parties vote yes. This results in 2k respective transitions of the Petri net. If we want to avoid this possibility in the Petri net, we just remove the single transition that removes tokens from all accept-places and enables overall rejection. For the negotiation, we found the following work-around: we replace the atom nreject by k rejecting atoms rejecti, for 1 ≤ i ≤ k. If agent ai votes yes, then it is ready to engage in accept and in all rejectj such that j 6= i. Any of the rejecjj-atoms have a single result that leads to final rejection. When all agents vote yes then none of the rejecti-atoms are enabled, whence only overall acceptance can take place. Notice that this construction is a bit clumsy (see Figure 4), but still does not require exponentially many elements, as the associated Petri net does.
An S-component of a Petri net is a subnet such that, for each place of the subnet,
all input- and output-transitions belong to the subnet as well, and such that each
transition of the subnet has exactly one input- and exactly one output-place of
the subnet. It is immediate to see that the number of tokens in an S-component
never changes. A net is covered by S-components if each place and each transition
belongs to an S-component. Nets covered by S-components carrying exactly one
token are necessarily 1-safe. For example, every live and 1-safe free-choice net
enjoys this nice property [
Petri nets associated with negotiations are not covered by S-components, only because the end-transitions have no output places. However, if we add an arc from each end-transition to each initially marked place, then the resulting net is covered by S-components: Proposition 4. The Petri net associated with a negotiation, with additional arcs from each end-transition to each initially marked place, is covered by Scomponents.
Proof. (Sketch). For each agent a, the subnet generated by all places [a, X] and all transitions labelled by (n, r), where a ∈ Pn, is an S-component (being generated implies that the arcs of the subnet are all arcs of the original net connecting nodes of the subnet). An arbitrary place of the net belongs to one such subnet, because it corresponds to an agent. Each transition has a label (n, r), and each atom n has a nonempty set of participants. tu 4.2
The following notion of sound negotiations was inspired by van der Aalst’s
soundness of workflow nets [
Definition 9. A negotiation is sound if each outcome occurs in some initial occurrence sequence and if, moreover, each finite occurrence sequence is a large step or can be extended to a large step.
All the negotiations shown in the figures of this paper are sound. For an example of an unsound negotiation, consider again the ping-pong negotiation shown in Figure 1 on the right hand side. Imagine that Daughter could choose to start negotiating with Father or with Mother. This could be expressed by replacing the arc from port D of n0 to port D of nFD by a hyperarc from port D of n0 to ports D of both nFD and nDM. If the first negotiation is between Daughter and Mother, and if it is successful, a marking is reached where both Daughter and Mother can only engage in the final atom nf , whereas father is still only able to participate in nFD. So the distributed negotiation has reached a marking which is neither final nor enables any outcome. We call such a marking a deadlock. Clearly, sound negotiations have no reachable deadlocks.
Since the Petri nets associated with negotiations are not workflow nets, we cannot immediately compare the soundness notions of workflow nets and of negotiations. Instead, we first provide a translation of nets associated with negotiations to workflow nets. It turns out that a sound negotiation does not necessarily lead to a sound workflow net in the general case. However, for the subclass of deterministic negotiations the two concepts coincide, as will be shown next.
We begin with a very simple equivalence transformation of nets:
Two Petri nets N and N 0 are in the relation R if – either N has two distinct places with identical sets of input transitions, identical sets of output transitions and equal initial markings, and N 0 is obtained from N by deletion of one of these places (and adjacent arcs), – or N has a place without output transition, and N 0 is obtained from N by deletion of this place.
The symmetrical, reflexive and transitive closure of R is called place equivalence. Obviously, two place-equivalent nets have identical behaviour, i.e., their reachability graphs are isomorphic and so are their concurrent step reachability graphs. Notice, however, that place-equivalence does not respect 1-safety. If the only place that violates 1-safety has no output-transition, then deletion of this place can make a net 1-safe.
A workflow net is a Petri net with two distinguished places pin and pout such that pin has no input transition, pout has no output transition and, for each place or transition x, there are directed paths from pin to x and from x to pout. The initial marking of a workflow net assigns one token to the place pin and no token to all other places. Workflow nets also have a final marking , assigning only one token to pout. A workflow net is sound if it has no dead transitions (i.e., each transition is in an initially enabled occurrence sequence) and, moreover, each initially enabled occurrence sequence is a prefix of an occurrence sequence leading to the final marking.
Proposition 5. The net associated with a sound negotiation is place-equivalent to a workflow net.
Proof. (Sketch). We derive a single input place pin by deleting all but one of the initially marked places. We add a new place pout with all end-transitions as input transitions. Both transformations apparently lead to place equivalence nets.
Since, by soundness of the negotiation, every atom (and therefore every outcome) can be enabled, a token can be moved from the initial atom to any other atom, and therefore there is a directed path from the initial atom to any other atom (more precisely, there is a path in the graph of the negotiation). By the construction of the Petri net, there are according paths from the place pin to arbitrary places and transitions of the net.
Again by soundness of the negotiation, every occurrence sequence can be extended to a large step, i.e., the final atom can eventually be enabled and the final marking reached. So every “token” can be led to the final atom, and therefore there are paths in the graph of the negotiation from every atom to the final atom. By construction of the Petri net, there are thus paths from any element to an end-transition, and finally to the new place pout.
Unfortunately, soundness of a negotiation does not necessarily imply soundness of a related workflow net. The reason is that soundness requires that every atom can occur but not that every branch of a hyperarc is actually used. If, for example, there would be an additional hyperarc in Figure 1 from the port F in n0 to the ports F in nFD and nf instead of the arc from n0 to nFD, then the resulting negotiation would still be sound (actually, the behaviour does not change at all). In the associated Petri net, however, there would be an additional transition end with new input place [F, {nFD, nf }] (and other input places) which never is enabled. This net is therefore not sound. 4.3
In [
Definition 11. A negotiation is deterministic if, for each atom n, agent a ∈ Pn and result r ∈ Rn, X(n, a, r) contains at most one atom (and no atom only if n = nf ).
The term deterministic is justified because there is no choice for an agent with respect to the next possible atom.
Since both, the exponential blow-up and the problem of useless arcs (branches of hyperarcs) stem from proper hyperarcs, we can expect that deterministic negotiations allow for better results. Actually, the Petri net associated with a deterministic negotiation is in fact much smaller, because all its places have the form [a, X], where a is an agent and X is a singleton set of atoms. So the set of places is linear in agents and in atom.
Before discussing soundness of deterministic negotiations, we make a structural observation: Proposition 6. The net associated with a deterministic negotiation is a freechoice net, i.e., every two places either share no output transitions, or they share all their output transitions.
Proof. (Sketch). Since, in nets associated with deterministic negotiations, each place has the form [a, X], where X is a singleton set {n}, all its output transitions are labelled by (n, r), r being a possible result of n. By construction, every other place [b, {n}] has exactly the same output transitions as [a, {n}] whereas all other places have no common output transition with [a, {n}]. tu Proposition 7. The net associated with a deterministic negotiation is sound if and only if it is place equivalent to a sound workflow net.
Proof. (Sketch). Observe that the translation from the negotiation to the associated Petri net is much easier in this case: for each atom n we add places [a, n] for each a in Pn and transitions (n, r) for each r ∈ Rn. There are no two transitions for any outcome (n, r), and so transition labels are not necessary (formally, we can label each transition by itself). For each such place [a, n] of an atom n and each such transition (n, r) we add an arc from [a, n] to (n, r). Finally we add arcs from transitions (n, r) to places [b, n0] whenever X(n, a, r) = {n0} and b ∈ Pn0 .
It is immediate that to see this net is free-choice and that the behaviour of the negotiation is precisely mimicked by the net. So the negotiation is sound if and only if the net has no dead transitions and moreover can always reach the final (empty) marking.
The result follows since the net can, as above, be translated into a place equivalent workflow net. tu 5
In this section we study the converse direction: Given a labelled Petri net, is there a negotiation such that the net is associated with the negotiation? Obviously, for a positive answer the net has to enjoy all the properties derived before. In particular, it must have disjoint S-components and initially marked input places. However, in the general case it appears to be difficult to characterise nets that have corresponding negotiations.
We will provide an answer for the case of sound deterministic negotiations and sound free-choice workflow nets.
Proposition 8. Every sound free-choice workflow net is place equivalent to a net which is associated with a sound deterministic negotiation.
Proof. (Sketch). A workflow net is sound if and only if the net with an additional
feedback transition moving the token from pout back to pin is live and 1-safe [
Instead we proceed as follows: We choose a minimal set of S-components that cover the net. Since each S-component of a live net has to carry a token, all these S-components contain the place pin. Each S-component will be an agent of the net to be constructed, and each conflict cluster (i.e., each maximal set of places together with their common output transitions) a negotiation atom.
Each place p of the net is contained in at least one S-component of the cover. Let Cp be the set of all S-components of the derived minimal cover containing p. If Cp contains more than one S-component, we duplicate the place p, getting a new place p0 with input and output transitions like p. Now the new net still has a cover by S-components, where one of the S-components containing p now contains p0 instead. Repetition of this procedure eventually leads to a net where each place p belongs to exactly one S-component Cp of the cover. Finally we delete the place pout. Both operations, duplication of places and deletion of pout, lead to place-equivalent nets.
The resulting net is associated with the following negotiation: The set of agents is the set of S-components of the minimal cover. The atoms are the conflict clusters of the net. The results of an atom are the transitions of the corresponding conflict cluster. The X-function can be derived from the arcs of the Petri net leading from transitions to places.
This contribution presented the translation from distributed negotiations to Petri nets such that a negotiation and its associated Petri nets are behaviourally equivalent in a strong sense. In the general case, the Petri net is exponentially larger than the negotiation, wheras for deterministic negotiations its size is only linear. Petri nets do not inherit many properties from arbitrary negotiations, but for deterministic negotiations soundness and non-soundness is respected by the transformation to workflow-like Petri nets, whence in this case the reverse translation is possible as well.
Analysis results for negotiations might be transferable to Petri nets and vice
versa via the translation. In future work, we will study this question in particular
for the respective sound and complete sets of reduction rules for negotiations [
Based on the reduction results, a very recent work [