Modeling the Exogenous Coordination of Mobile Channel based Systems with Petri Nets Juan Gu


FOCLASA 2005 Preliminary Version

Modeling the Exogenous Coordination of Mobile Channel based Systems with Petri Nets
Juan Guillen-Scholten a,1 Farhad Arbab a,1 Frank de Boer a,1 Marcello Bonsangue b,2,3
a b

CWI, Amsterdam, The Netherlands

LIACS, Leiden University, The Netherlands

Abstract In this paper, we discuss how to model systems that communicate through and are coordinated by mobile channels. Mainly, we focus on modeling the exogenous coordination behavior imposed by these channels. We use Petri Nets as our modeling language, for they provide a graphically and mathematically founded modeling formalism. We give Petri Nets for a set of mobile channel types. This allows us to construct models of applications, by taking the Petri Net of each component and each mobile channel, and composing them together. For this purpose, we de?ne a special Petri Net composition function. We also discuss analysis and simulation of these models and their exogenous coordination behavior.

1

Introduction

In the MoCha Framework [6] components and processes are coordinated by mobile channels. A mobile channel is a coordination primitive that allows anonymous point-to-point communication, enables dynamic recon?guration of channel connections in a system, and provides exogenous coordination. Mobile channels are interesting for all kinds of entities that need to be coordinated, but they are specially interesting for Component Based Software. As we show in [6], they provide a highly expressive data-?ow architecture for the construction of complex coordination schemes, independent of the computation parts of components. The implementation of the MoCha Framework, the MoCha middleware, is suitable for any centralized or decentralized distributed network where we
1 2

Email: {juan, farhad, frb}@cwi.nl Email: marcello@liacs.nl 3 The research of Dr. Bonsangue has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences. This is a preliminary version. The ?nal version will be published in Electronic Notes in Theoretical Computer Science URL: www.elsevier.nl/locate/entcs

exogenously coordinate the components by means of mobile channels. For example, in [7] we show the bene?ts of using MoCha for P2P networks. The purpose of this paper is to give the means for modeling systems that communicate through and are coordinated by these mobile channels. Our main goal is to model, analyze, and simulate the exogenous coordination of these systems. Therefore, we need a modeling language with the following features: (1) The language is widely used in both the academic world and industry. (2) It contains well-de?ned semantics with clear theoretical foundation. (3) It provides analysis of models, like all modeling languages do. (4) It provides model simulation. (5) The language is easy to understand as well as the models that it produces. (6) And last, but not least, there is enough tool-support for this language. A modeling language that ful?lls above requirements is Petri Nets. Petri Nets, named after their creator Petri [12], provide a graphically and mathematically founded modeling formalism for the concurrent behavior of systems. They o?er precise semantics and a theoretical foundation [15]. By providing mobile channels speci?ed in the Petri Nets model formalism, we can model systems that use our channels with this formalism. This means that, besides being able to model systems, we automatically get the following advantages: extensive theoretical support, ease of usage, model analysis, simulation of the models, immediate application in di?erent areas, and extensive tool support. Furthermore, while it is not the main objective of this paper, since Petri Nets models have clear and precise semantics, they also automatically give semantics to our mobile channels. The interested reader can compare the mobile channel semantics given in [8] which concentrate on process interaction, with the semantics given in this paper which concentrate on concurrency. In section 2, we give a brief overview of the MoCha Framework. In section 3, we give a short introduction to Petri Nets. In section 4, we show how to model systems that use our mobile channels. Here we give the Petri Net models for a set of mobile channel types, discuss the minimal behavior that components need to implement in Petri Nets to use these channels, and give a composition function for constructing systems. In section 5, we give an example of such a composed system, and discuss analysis and simulation. In section 6, we discuss the complexity of our approach and the need for tools. We conclude with section 7.

2

MoCha

A channel in MoCha (see ?gure 1) consists of a pair of two distinct ends: usually (source, sink) for most common channel-types, but also (source, source) and (sink, sink) for special types. These channel-ends are available to the components of an application. Components can write by inserting values into the source-end, and take by removing values from the sink-end of a channel; 2

the data-?ow is locally one way: from a component into a channel or from a channel into a component.
Component Writes

Channel
Takes Source Sink

Component

A

B

Fig. 1. General View of a Channel.

Channels are point-to-point, they provide a directed virtual path between the (remote) components involved in the connection. Therefore, using channels to express the communication carried out within an application is architecturally very expressive, because it is easy to see which components (potentially) exchange data with each other. This makes it easier to apply tools for the analysis of dependencies and data-?ow analysis in an application. Channels provide anonymous communication. This enables components to exchange messages with other components without having to know where in the network those other components reside, who produces or consumes the exchanged messages, and when a particular message was produced or will be consumed. Since the components do not know each other, it is easy to update or exchange any one of them without the knowledge of the components at the other side of the channels it is connected to. This provides a simple mechanism for composition of components that are decoupled in space and time. The ends of a channel are mobile. We introduce here two de?nitions of mobility: physical and logical. The ?rst is de?ned as physically moving a channel-end from one location to another location in a distributed system, where location is a logical address space wherein components execute. The second, logical mobility, is typically de?ned in the π-calculus as the ability of passing channel(-end) identities through channels themselves to other components in the application; i.e., spreading the knowledge of channel(-ends) references by means of channels. This is possible in MoCha. However, in this paper we de?ne logical mobility as the changing of channel connections among components in a system by means of connect and disconnect operations. Both physical and logical mobility are supported by MoCha. Mobility allows dynamic recon?guration of channel connections among the components in an application, a property that is very useful and even crucial in systems where components are mobile. A component is called mobile when, in a distributed system, it can move from one location (where its code is executing) to another. Because the communication via channels is also anonymous, when a channel-end moves, the components at the other side of the channel are not aware nor a?ected by this movement. Channels provide transparent exogenous coordination. Channels allow several di?erent types of connections among components without them knowing which channel types they deal with. Only the creator of the connection knows the type of the channel. This makes it possible to coordinate components from 3

the outside (exogenous), and thus, change an application’s behavior without having to change the code of its components.

3

A Short Introduction into Petri Nets

Petri Net is actually a generic name for a whole class of net-based models which can be divided into three main layers [17]. The ?rst layer is the most fundamental and is especially well suited for a thorough investigation of foundational issues of concurrent systems. The basic model here is that of Elementary Net Systems [16], or EN systems. The second layer is an ”intermediate” model where one folds some repetitive features of EN systems in order to get more compact representations. The basic model here is Place/Transition Systems [2], or P/T systems. Finally, the third layer is that of high-level nets, where one uses essentially algebraic and logical tools to yield ”compact nets” that are suited for real-life applications. Predicate/Transition Nets [5] and Colored Petri Nets [10] are the best known high-level models. Any Petri Net of the three layers above is suitable to model a system. Moreover, any Petri Net of any layer can be transformed/translated into a Petri Net of another layer [4]. Examples of translation are given in the work of Engelfriet [3] and Jensen [11]. We speci?ed all the channel types of the MoCha Framework using the Place/Transition Petri Nets. In contrast with the highlevel Petri Nets, these kind of Petri Nets are at the right level of abstraction with clear non-changeable semantic rules and constructs. However, in this paper, for simplicity, we use the Elementary Net Systems Petri Nets. This last kind of Petri Nets are easier to use, for their theory is a little bit more simpler. Furthermore, the topology of the synchronous channel types of both models are structural equivalent. For the asynchronous types that we introduce in this paper, it doesn’t pay o? to use the Place/Transition Petri Nets for all channel types. 3.1 Elementary Net Systems We give a short introduction of Elementary Net Systems (EN system in short). We restrict ourselves to the de?nitions that we need in this paper. For an extensive introduction that also covers several properties of EN systems, equivalences, and EN analysis we refer to the tutorial given in [17]. A net is the most basic de?nition of all Petri Nets: De?nition 3.1 A net is a triple N = (P, T, F ) where (1)P and T are ?nite sets with P ∩ T = ?, (2)F ? (P × T ) ∪ (T × P ), (3) for every t ∈ T there exist p, q ∈ P such that (p, t), (t, q) ∈ F , and (4) for every t ∈ T and p, q ∈ P , if (p, t), (t, q) ∈ F , then p = q. The elements of P are called places, the elements of T are called transitions, 4

elements of X = P ∪ T are called elements (of N ), and F is called the ?ow relation (of N ). Each place p ∈ P can be viewed as representing a possible local state of a system. At each moment in time a set of local states (places) participate in the global state of the system. We call such a set of places a con?guration. Graphically, we denote the places that are part of a con?guration with a token; a small black ?lled circle. De?nition 3.2 A con?guration C of a net N = (P, T, F ) is a subset of P . Thus, a con?guration C of a net is a subset of P where each place contains a token. We now de?ne a elementary net system as given in [17]: De?nition 3.3 De?nition: An EN system is a quadruple M = (P, T, F, Cin ) where: (1)(P, T, F ) is a net and (2)Cin ? P is the initial con?guration Every transition in an EN system can perform an action called ?re. This action takes a token from all the input places and places a token to each output place of the transition. This action represents a sequential step of a system. However, for this to happen all the input places of the transition must have a token and its output places must be empty, since a place can have at most only one token at the same time. De?nition 3.4 Let M = (P, T, F, Cin ) be an EN system and let t ∈ T . (1) ? t are the input places of t, and t? the output places of t. (2) Let C ? P be a con?guration. Then t has concession in C (or t can be ?red in C) if ? t ? C and t? ∩ C = ?, written as t con C. (3) Let C,D ? P . Then t ?res from C to D if t con C and D = (C ?? t) ∪ t? , written as C[t > D; t is also called a sequential step from C to D.

4

Modeling Mobile Channel based Systems

In order to model systems that use mobile channels, we need to model the channels in Petri Nets, from now on PN, ?rst. We, then, take the PN of the components and compose them together with the PN of our mobile channels. Next, we give the interface of these PN mobile channels. Afterward, we give the interface and minimal behavior that components need to implement in order to use our channels. We, then, specify a PN composition function σ. Besides composing, this function implicitly models the connect and disconnect channel operation (by using the inverse function as well). Finally, we give the EN systems for a representative set of mobile channel types. 5

4.1 Mobile Channel Interface The EN and P/T-net mobile channel systems that we present in this section have all the same interface from the point of view of the components of a system. We give this interface in ?gure 2. Each channel-net has an internal part that is determined by it’s type, and an interface that is common to all channel types consisting of four interface places, two for each channel-end. We graphically denote these places by marking an extra symbol, I, on the outside of the circle. The interface places are part of a protocol to ensure that all write and take operations are blocking; i.e. an active entity performing such an operation blocks until the operation succeeds and terminates.
Channel
p

Source

I

Source

Sink

I I

p

Fig. 2. PN Mobile Channel Interface

The places pSource and pW A constitute the interface of the source channelend. A component that wants to perform a write operation on this end, puts a token into place pSource . This token represents the fact that a data element is available but has not yet been accepted by the channel. In other words, the write operation is pending between the component and the source channel-end. When the token is removed from this place by the channel, it means that the channel is processing the write operation. Upon completion of the operation, the channel puts a token in the interface place pW A ; a write acknowledgment. The places pSink and pRT T constitute the interface of the sink channel-end. A component that wants to perform a take operation on this end, puts a token in place pRT T (Ready To Take). This token reveals the desire and willingness of the component to take a data element from the channel. However, the channel knows that there is a component waiting (and wanting) to take an element only when the token in pRT T successfully ”enters” the channel due to a ?re action. The channel terminates the take operation by putting a token into the pSink interface place. The component, then, can take the token from this place. We don’t explicitly model a source- and a sink-end in the mobile channel nets. A channel-end is implicitly modeled by its two interface places and the internal transitions where these places are either input or output of. Observe, that the semantics of the write and take operations are analogous with the ones de?ned in [8]. 4.2 Component Interaction The components of a system interact with the mobile channels thought the interface that we de?ned above. From the point of view of the channels, 6

I

p

Sink

p

RTT

WA

p t1
I

Input

p
I

RTT

p

1

p

2

t1

t2

p

1

p

2

I

I

p

Output

p

t2

WA

(a) A Writer

(b) A Taker

Fig. 3. A Writer and a Taker EN System

a component consists of one or more active entities (threads or processes) that perform write and take operations. In ?gure 3 we give the EN systems of two single entity components. They represent the minimal behavior that components need to implement regarding the write and take operations toward channels; i.e. they implement their side of the blocking protocol as described in section 4.1. Figure 3(a) shows the PN of a simple writer. This net has two interface places that are meant for composition with channels:{pOutput , pW A }. The initial con?guration of the net is {p2 }. The writer starts the write operation by executing {p2 }[t2 > {pOutput , p1 }. At this point it is blocked for it must wait until it receives a write acknowledgment; i.e. a token is placed in pW A . If the writer is interacting with a source channel-end, at the time that it receives the acknowledgment the token in place pOutput is already gone. Therefore, we end up with the con?guration {p1 , pW A }. The writer ends the operation by performing the sequential step {p1 , pW A }[t1 > Cin . At this point, it may start writing again. Figure 3(b) shows the PN of a simple taker. This net has also two interface places that are meant for composition with channels: {pInput , pRT T }. The initial con?guration of this net is {p2 }. The taker starts the take operation by executing {p2 }[t2 > {p1 , pRT T }. At some point in time the channel it is interacting with takes the token of pRT T , and later on, it puts a token back in place pInput . The resulting con?guration is {p1 , pInput }. The taker ends the operation by performing {p1 , pInput }[t1 > Cin . At this point, it may start taking again. 4.3 PN Composition of Components and Channels We have introduced the interface of channels and the interface of components toward channels. We now need to compose components and channels together. There are several construction strategies possible. Our major requirement is that such strategy is compositional. One should be able to distinguish the 7

individual components and channels in the composed system, and it must be easy to decompose and rearrange the system; i.e. updating and replacing components and channels without having to change the rest of the system. Therefore, for example, we cannot do composition and optimize the resulting PN for it may not be possible to decompose after many composition steps anymore. Our strategy is, then, to do composition on the interface places. This way, we don’t have to change the internals of components and channels. It is easy to recognize the individual parts. And, decomposition is also clear and easy to do. For this purpose we de?ne a composition function that mergers, or concatenates, interface places: De?nition 4.1 We de?ne the composition function σ : (X1 , P1 , X2 , P2 ) ?→ Y where, (1) X1 , X2 and Y are EN systems (2) P1 and P2 are ordered ?nite set of places, with P1 ? PX1 , P2 ? PX2 and |P1 | = |P2 |. Typical elements of these sets are p1 ∈ P1 and p2 ∈ P2 . We construct the new Petri Net EN System Y as follow, (3) We rename the places, transitions and ?ow relations of nets X1 and X2 that have the same name. (4) PY = (PX1 \ P1 ) ∪ (PX2 \ P2 ) ∪ Pnew , where ?(pairs(p1?i , p2?i )) ?pnew?i ∈ Pnew , with i as an index from 1 to |P1 | = |P2 |, and |P1 | = |P2 | = |Pnew |, (5) TY = TX1 ∪ TX2 , (6) FY = (FX1 ∪ FX2 ∪ FI ) \ FRem , where ?(i ∈ 1 to |Pk |) if (pk?i , t) ∈ FXk then (pk?i , t) ∈ FRem ∧ (pnew?i , t) ∈ FI , ?(i ∈ 1 to |Pk |) if (t, pk?i ) ∈ FXk then (t, pk?i ) ∈ FRem ∧ (t, pnew?i ) ∈ FI , with k = {1, 2}, pk?i ∈ Pk and pnew?i ∈ Pnew , both with index i. (7) Cin?Y = (Cin?X1 \ P1 ) ∪ (Cin?X2 \ P2 ) ∪ Cin?new , where (?i ∈ 1 to |Pnew |)if pk?i ∈ Pk ∧ pk?i ∈ Cin?Xk then pnew?i ∈ Cin?new , with k = {1, 2}. The function σ takes EN Systems as parameters, X1 and X2 . The function also takes two set of places, P1 and P2 , that correspond to the interface places of respectively X1 and X2 that we want to compose. The result of the function is a new EN System Y , that is constructed as follow: (3) We rename all the places, transitions, and relation ?ows of nets X1 and X2 that cause name con?icts due to the composition. (4) Each place of X1 and X2 is present in Y , except for the interface places of P1 and P2 . Each pair {p1 , p2 } of these places, that are related to each other for having the same index number, are substitute for a new place, pnew , that is inserted in Y . (5) The composition is done on interface places so the transitions of Y are just the union of the ones in X1 and X2 . (6) Every ?ow relation present in either X1 or X2 is also present in Y . The ?ow relations that involve the interface places in P1 and P2 , represented in FRem , are changed to be involved in the new added places 8

p

Channel

Source

Sink

p

RTT

WA

p

2

Source Output

Sink Input

t2

t3

t1

p

p

4

p

p

1

Fig. 4. Composing a Writer and a Taker with Mobile Channels

of point 3, represented in FI . (7) The Cin of Y is the union of the ones of X1 and X2 . However, the places of P1 and P2 may also be present at the initial con?gurations of these two last EN systems. Since these places do not exist anymore in Y , we add their corresponding new places from Pnew into the initial con?guration. We can now compose components and channels using our function σ. For example, we obtain the PN-system Comp of ?gure 4, by applying the σ function to the writer-, taker component and a channel (which we de?ned previously): Comp = σ(T aker, {pInput , pRT T }, T mp, {pSink , pRT T }), T mp = σ(W riter, {pOutput , pW A }, Channel, {pSource , pW A }. In this ?gure we take the general channel de?nition. Later on, we give several PN-systems for di?erent mobile channel types. The composition function σ implicitly models the operation connect. Our components don’t issue a connect request, and we don’t keep any administration concerning connect. However, if a component is composed with a channel by σ we regard this component connected to the appropriate channelend. Analogous to connect, we implicitly model disconnect with the function σ ?1 ; the inverse of σ. 4.4 A Set of EN and P/T-net Mobile Channels Systems We now take a representative set of mobile channel types and give an EN system for each of them. 4.4.1 The Synchronous Channel Type With a synchronous channel the I/O operations of both ends are synchronized; the I/O operations atomically succeed. Figure 5(a) shows the EN system of this channel. The internals of this channel type is just a transition tW rite that synchronizes the four interface places as de?ned in section 4.1. The places pSource and pRT T are input places of transition tW rite . Therefore, only when both the writing and the taking components have each inserted a token in these places, the I/O operations atomically succeeds (at the same time); each component inserts a token to its corresponding place as described in section 4.2. We give the sequential ?ring step: {pSource , pRT T }[tW rite > {pSink , pW A }. At the end a token is inserted in the places pSink and pW A . This indicates the 9

p

3

t4

p

WA I

p
I

Source

t WT1 p
WA I

t WT2

p
I

Source

p

1

p

2

p

3

t1 t Write t2

I

I

I

I

p

Sink

p

RTT

p

RTT

p

Sink

(a) Synchronous Channel

(b) Lossy Synchronous Channel

Fig. 5. The Synchronous and Lossy Synchronous Channel EN Systems

end of the I/O operations, from the point of view of the channel. 4.4.2 The Lossy Synchronous Channel Type With the lossy synchronous channel, if there is no I/O operation performed on the sink channel-end while writing a value to the source-end, the write operation always succeeds but the value gets lost. In all other cases, the channel behaves like a normal synchronous type. Figure 5(b) gives the EN system for this channel type. There are two paths for a successful write operation. One, is determined by the tW T 1 transition and exhibits the behavior of a synchronous channel. The other, is determined by the tW T 2 transition and exhibits the lossy behavior. The choice between the ?rst or the second path depends whether there is a component waiting to take a value or not, this is symbolized by the presence of a token in place pRT T . However, the channel is not aware of this intention yet. Only when ?ring transition t1 does the channel know that a component is ready to accept a value: {pRT T }[t1 > {p1 , p2 }. If there is a token in place pSource , there is a component trying to write, transition tW T 1 ?res when there is a token in places p1 and p2 ; there is a component waiting to take. At the same time, transition tW T 2 is blocked because of the token in place p2 . Therefore, the written value synchronously ?ows from pSource to pSink : {pSource , p1 , p2 }[tW T 1 > {pSink , pW A }. However, if there are no tokens in places p1 and p2 , there is no component to take, transition tW T 2 ?res and the value gets lost while the write operation succeeds. Observe that, the transition tW T 1 cannot ?re due to the lack of a token in place p1 . There is no need to model a garbage collector to delete the token value since the ?ring of transition t2 already takes care of this. We give the sequential steps of the lossy path: {pSource }[tW T 2 > {p2 , p3 }[t2 > {pW A }. 10

4.4.3 The FIFO and FIFO n Channel Type
p
WA I

p
I

p

Source

WA I

p
I

p

Source

WA I

p
I

Source

t Write

t Write

t Write

p

buf

p

buf1

p

buf(1)

t Take

t1

Dashed pattern repeats itself until there are n buf places

t buf(2?n)

I

I

p p
Sink

buf2

p

p

buf(2?n)

RTT

t Take

t Take

I

I

I

I

p

RTT

p

Sink

p

RTT

p

Sink

(a) FIFO?1

(b) FIFO?2

(c) FIFO?n

Fig. 6. The FIFO 1, 2 and n Channel EN Systems

With an asynchronous FIFO channel type the I/O operations that are performed on both channel-ends are done in an asynchronous way. Values written into the source channel-end are internally stored in a bu?er until taken from the sink-end. Figure 6(a) shows the EN system of a FIFO-1 channel. As one could expect, the internal bu?er of capacity one is modeled by place pbuf . We write a value into the channel by performing the sequential step {pSource }[twrite > {pbuf , pW A }, and we take a value by performing {pbuf , pRT T }[tT ake > {pSink }. In ?gure 6(b) we give a FIFO-2 EN system channel. Naturally, it contains two bu?er places. Figure 6(c) gives the general scheme of a FIFO EN system channel with bu?er capacity n. Observe, that if n is unlimited, the unbounded FIFO channel type, we get an EN system with in?nite places. To avoid this, we work with a P/T-net system where we have a single bu?er place with unlimited capacity. However, for space saving reasons, we omitted this kind of PN in this paper. 4.4.4 The Asynchronous Drain Channel Type The asynchronous drain channel type has two source channel-ends. Furthermore, the I/O operations performed on the ends of this channel succeed one at a time exclusively. So the write operations on its two ends never succeed simultaneously. This is re?ected in the net we give in ?gure 7(a). Place p3 makes sure that either transition tW rite1 or transition tW rite2 ?res, but not both at the same time. Let’s assume that there are two simultaneous writes available; the net con?guration is {psource1 , psource2 }. Then, we can perform the write operation 11

p

WA1 I

p
I

Source1

p
I

p

Source2

WA2 I

p

1

p

2

p

3

t Write1

t Write2

t1

t Take1

t Take2

t2

p

1

p

3

p

2

I

I

I

I

p t1 t2

RTT?1

p

Sink?1

p

Sink?2

p

RTT?2

(a) Asynchronous Drain

(b) Asynchronous Spout

Fig. 7. The Asynchronous Drain- and Spout EN Channel Systems

on the left source-end ?rst: {psource1 , psource2 }[tW rite1 > {psource2 , p1 , p3 }, at this con?guration transition tW rite2 is blocked, {psource2 , p1 , p3 }[t1 > {psource2 , pW A1 }. Or, we can perform the write operation on the source-end at the right ?rst: {psource1 , psource2 }[tW rite1 > {psource1 , p2 , p3 }, at this con?guration transition tW rite1 is blocked, {psource1 , p2 , p3 }[t1 > {psource1 , pW A2 }. However, we can never perform both write operations at the same time, since we cannot ?re transitions tW rite1 and tW rite2 concurrently. 4.4.5 The Asynchronous Spout Channel Type The asynchronous spout channel type has two sink channel-ends. Furthermore, the I/O operations performed on the ends of this channel succeed one at a time exclusively. So the take operations on its two ends never succeed simultaneously. This is re?ected in the net we give in ?gure 7(b). Place p2 makes sure that either transition tT ake1 or transition tT ake2 ?res, but not both at the same time. Let’s assume that there are two simultaneous takes available; the net con?guration is {pRT T 1 , pRT T 2 }. Then, we can perform the take operation on the left sink-end ?rst: {pRT T 1 , pRT T 2 }[t1 > {pRT T 2 , p1 , p2 }, at this con?guration the token in place p2 blocks the ?ring of transition t2 , {pRT T 2 , p1 , p2 }[tT ake1 > {pRT T 2 , pSink1 }. Or, we can perform the take operation on the sink-end at the right ?rst: {pRT T 1 , pRT T 2 }[t2 > {pRT T 1 , p2 , p3 }, at this con?guration the token in place p2 blocks the ?ring of transition t1 , {pRT T 1 , p2 , p3 }[tT ake2 > {pRT T 1 , pSink2 }. However, we can never perform both take operations at the same time, since we cannot ?re transitions tT ake1 and tT ake2 concurrently.

5

Analysis and Simulation

We now know how to model systems that use our mobile channels by means of Petri Nets. In this section we discuss the analysis and simulation of these models. Figure 8 models a system that consists of a write-, and a take com12

ponent as de?ned in section 4.2. These two components interact through a lossy synchronous channel, as de?ned in section 4.4. We get the system by composing the Petri Nets of each separate entity by means of the function σ: σ(T aker, {pInput , pRT T }, T mp, {pSink , pRT T }), T mp = σ(W riter, {pOutput , pW A },LossySynchronous, {pSource , pW A }.
t WT2 p
3

p

w2

t w1

t w2

w1

Source

p

2

t2

p

p

Sink

t WT1

t t1

p

p

t2

WA

p

p

1

t1

Fig. 8. An Example of Composition

We can simulate the system by playing the ”token game”. This game consists of ?ring transitions, when possible, to get the system from one state into the other. If we cover all possible ?ring sequences, we get all the possible states of the system, and thus all the possible exogenous coordination of this system. In ?gure 9 we give the sequential con?guration graph of ?gure 8. For a precise de?nition of (sequential) con?gurations graphs, see [17]. Besides simulation, we can also analyze the exogenous coordination behavior of the models for desired, or undesired, properties and features. Petri Nets o?er extensive analysis of its models. The most common analysis features include causality, concurrency, con?icts, confusions, deadlocks, and equivalence. The ?rst, studies the causality between the events of a system. The second, analyzes which system events are concurrent at the same moment in time. The third, analyzes which events are con?icting at the same moment in time. Sophistic interaction between concurrency and con?icts can lead to, the fourth, confusions; events that are concurrent can become con?ict and vice-versa. The ?rst four features make it possible to reason about, the ?fth, deadlocks in a system. And ?nally, Petri Net analysis include equivalence. Usually, similarity of systems is build upon the notion of morphism. For example, we can analyze the exogenous behavior of our example model to ?nd concurrent steps. For this purpose, we can look at its sequential con?guration graph, given in ?gure 9. Basically, every diamond shape in the ?gure represents a concurrent step. The ?rst possible concurrent step is {pw2 , pt2 }[{tt2 , tw2 } > {pw1 , pt1 , psource , prtt }; we can arrive from con?guration {pw2 , pt2 } to con?guration {pw1 , pt1 , psource , prtt }, by ?rst ?ring transition tw2 and then transition tt2 , or vice-versa. For the precise de?nition of concurrency and other analysis we refer to [17,2]. 13

p

RTT

p

t t2

t1

{Pw2,Pt2} = (1) Tt2 (2) = {Pw2,Pt1,Prtt} T1 (4) = {Pw2,Pt1,P1,P2} Tw2 Tw2 Tw2 {Pw1,Psource,Pt2} = (3) Tt2 Twt2 {Pw1,Pt2,P2,P3} = (5) Tt2 T2 {Pw1,Pt2,Pwa} Tw1 T2 Tt2 (1) {Pw1,Pt1,Prtt,Pwa} T2 T1 {Pw1,Pt1,P1,P2,Pwa} Tw1 (4) Tw1 (2)

{Pw1,Pt1,Psource,Prtt} T1 Twt2

{Pw1,Pt1,Psource,P1,P2} Twt1 (6) = {Pw1,Pt1,Psink,Pwa} Tw1 {Pw2,Pt1,Psink} Tw2 {Pw1,Psource,Pt1,Psink} Tt1 (3) Twt2 {Pw1,P2,P3,Pt1,Psink} Tt1 (5) T2 (6) Tt1 (1) Tt1 {Pw1,Pt2,Pwa} Tw1

{Pw1,Pt1,Prtt,P2,P3}

Fig. 9. The Sequential Con?guration Graph of Figure 8

6

Complexity and the Need for Tools

The system we modeled in ?gure 8 is quite small and simple. Analyzing and simulating this system “by hand” is possible, but already not a pleasant task. For example, look at the size of ?gure 9. A real application consists of many components and many mobile channels. Therefore, modeling such an application quickly results in a big Petri Net model that is not humantractable anymore. One of the reasons is that the construction strategy we chose is compositional (see section 4.3). Therefore, we cannot optimize the PN systems we obtain, because then we could not recognize its constituent parts anymore. However, the main reason for this explosion is that EN and P/T systems do not o?er high-level constructs such as constrains. This obliges us to explicitly implement everything we need. For example, we explicitly implemented a protocol for modeling blocking operations (see section 4). If our goal is to produce human-readable models, then, the approach we take in this paper using EN and P/T systems is not really suitable. A better choice, for example, is a higher-level Petri Net like Colored Petri Nets [10], or, to use the MoCha-pi calculus given in [8]. However, the Petri Net models that our approach produces are very suitable for veri?cation and simulation using tools. This is due to the fact that, EN and P/T systems have clear non-changeable semantic rules and constructs, 14

and, that our Petri Net models explicitly encode low-level technical details that are otherwise not speci?ed. Fortunately, there are many tools available for EN and P/T systems. For an extensive list of these tools we refer to the state-of-the-art work in [13]. We are experimenting with the Platform Independent Petri Net Editor (PIPE) tool [1]. We chose this tool because, it is free of charge, platformindependent, o?ers simulation and analysis modules, and gives XML support.

7

Conclusions

In this paper, we showed how to model distributed systems that communicate through and are coordinated by mobile channels. We focused on modeling the exogenous coordination of these systems. Examples of such systems are Component Based and P2P networks, as explained in [6,7]. The modeling language we chose to use is Petri Nets. We discussed the modeling of components, mobile channels and their composition into distributed systems. We discussed the analysis and simulation of these Petri Net models. In particular, the analysis of causality, concurrency, con?icts, confusions, deadlocks, and equivalence of the exogenous coordination of these models. We, also, discussed the negative and positive points of the approach we take for mapping MoCha into Petri Nets. On the negative side, the models that we produce quickly become intractable for humans. On the positive side, the low-level semantics of these models make them very suitable for simulation and analysis using one of the many tools that are available for the kind of Petri Nets we use. Petri Nets have been used in many di?erent application areas. As a result there is a high degree of expertise in the modeling ?eld. Interesting for this paper is the work on Web Services composition presented in [9]. MoCha channels are suitable for Web Services, and we are intend to use the channel Petri Nets of this paper for this purpose as well. In [14], Petri Nets are used to model distributed algorithms. Although, we did not introduce an explicit notion of location, our channel Petri Nets de?ne a distributed implementation of the MoCha Framework channel types.

References
[1] J.D. Bloom, Platform Independent Petri-Net Editor (PIPE), electronic manual, 2005, available on-line at http://petri-net.sourceforge.net [2] J. Desel, and W. Reisig, Place/Transition Petri Nets, Lecture Notes in Computer Science, Vol. 1491: Lectures on Petri Nets I: Basic Models, pages 122-173. Springer-Verlag, 1998. [3] J. Engelfriet, Branching processes of Petri nets, Acta Informatica Volume 28, Issue 6, pages 575 - 591, Springer-Verlag, 1991.

15

[4] J. Engelfriet, Private Correspondence, LIACS, 2004. [5] H. J. Genrich, Predicate/transition nets, Advances in Petri nets 1986, part I on Petri nets: central models and their properties, pages: 207 - 247, SpringerVerlag, 1987. [6] J.V. Guillen-Scholten, F. Arbab, F.S. de Boer and M.M. Bonsangue, A Channelbased Coordination Model for Components, A. Brogi and J. Jacquet, editors, Proceedings of the 1st International Workshop on Foundations of Coordination Languages and Software Architectures, ENTCS 68.3, Elsevier Science, 2002. [7] J.V. Guillen-Scholten, F. Arbab, Coordinated Anonymous Peer-to-Peer Connections with MoCha, Proc. of the 4th International Workshop on Scienti?c Engineering of Distributed Java Applications (FIDJI 2004), Luxembourg, 2425 November 2004, Lecture Notes in Computer Science, Vol. 3409, pp. 68-77, Springer-Verlag, January 2005. [8] J.V. Guillen-Scholten, F. Arbab, F.S. de Boer, and M.M. Bonsangue, MoChapi, an Exogenous Coordination Calculus based on Mobile Channels Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, New Mexico, USA, March 13-17, 2005. [9] R. Hamadi, B. Benatallah, A Petri net-based model for web service composition, Proceedings of the Fourteenth Australasian database conference on Database technologies 2003, Volume 17, pages: 191 - 200, Australia, 2003. [10] K. Jensen, A Brief Introduction to Coloured Petri Nets, Tools and Algorithms for the Construction and Analysis of Systems. Proceeding of the TACAS’97 Workshop, Enschede, The Netherlands 1997, Lecture Notes in Computer Science Vol. 1217, Springer-Verlag 1997. [11] K. Jensen, Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Volume 1, Basic Concepts. Monographs in Theoretical Computer Science, Springer-Verlag, 2nd corrected printing 1997. ISBN: 3-540-60943-1. [12] C.A. Petri, Nets, Time and Space. Theoretical Computer Science, 153:348, 1996. [13] Petri Nets World, Petri Nets Tool Database, Available on-line http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/, 2005. at

[14] W. Reisig, Elements of Distributed Algorithms: Modeling and Analysis with Petri nets, Springer-Verlag, 1998. [15] W. Reisig. G. Rozenberg (Eds.),Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Lecture Notes in Computer Science, vol. 1491, SpringerVerlag, 1998. [16] G. Rozenberg, Behaviour of Elementary Net Systems, Lecture Notes In Computer Science, Vol. 254, pages 60-94, Springer-Verlag, 1986 [17] G. Rozenberg and J. Engelfriet, Elementary Net Systems, Lecture Notes in Computer Science, v. 1491, Springer-Verlag, 12-121, 1998.

16


相关文档

更多相关文档

MODELING OF SYSTEMS WITH DELAYS USING HYBRID PETRI NETS
Modeling and Analysis of Workflows using Petri Nets
Modeling Mobile Agent Systems with High-Level Petri Nets
Modeling and analysis using hybrid Petri nets
MODELING, SIMULATION AND ANALYSIS OF PETRI NETS IN MATLAB
Using colored Petri nets for conversation modeling
Modeling and verification of fuzzy knowledge base with fuzzy colored Petri nets
Modeling Computer Systems Evolutions Non-Stationary Processes and Stochastic Petri Nets —
Towards Modeling and Simulating a Multi-party Negotiation Protocol with Colored Petri Nets
Hybrid Petri nets modeling for farm work flow
电脑版