A network system is given as a set of Petri net-like structures called agents. Each agent has a singled out place interpreted as a communication port with ingoing edges labelled with send(p1; :::; pn) and receive(q1; :::; qm) commands, where pi; qj are names of ports of its interlocutors. Every such edge exits a transition emiting a request for send or receive message. A transmission channel between the agent and its intelocutors is established when its port holds a send or receive command, while ports of its interlocutors hold respective (matching) communication commands. This gives rise to communication between the agent and its interlocutors, after which the channel is disrupted: hence oating channels. Some behavioural properties of such network system are examined, their decision complexity, deadlock and fairness in their number.
A system of communicating agents here is a collection of Petri net-like
structures [Rei 1985], such that in every net there is a singled out place serving for
communication and called a port. Each arrow entering the agent's port is
labelled with a send or receive communication statement with parameters being
names of ports the agent sends a message to, or receives from. Firing a
transition the arrow outgoes, results in putting the arrow's label in the port. If it is a
send (receive) statement and all ports - its parameters - hold matching receive
(send) statements, then a communication channel between senders and receivers
is set up
Let A = fAp1 ; Ap2 ; :::; Apd g be a set of agents, each agent Api (i = 1; 2; :::; d) equipped with a single communication port pi, their set P = fp1; p2; :::; pdg. A is treated as a distributed system whose agents are capable of intercommunicating through their ports. Suppose that the agents are autonomous, i.e. do not share any of their constituents. Let !(pk1 ; pk2 ; :::) and ?(pl1 ; pl2 ; :::) be a shorter notation of send(pk1 ; pk2 ; :::) and receive(pl1 ; pl2 ; :::) operations respectively, i.e. sending a message by an agent to ports pk1 ; pk2 ; ::: and receiving a message from ports pl1 ; pl2 ; :::. Here k1; k2::: and l1; l2::: are subsequences of the sequence 1; 2; :::; d. These communication operations may assume a varying number of parameters and are executed in the synchronous, i.e. hand-shaking mode. Let C denote a set of all possible communication operations of all the agents, along with the empty (no communication) operation . Since apart from communication, other computational activity of the agents is inessential, such fragments of their activity are not taken into consideration. That is why we assume that agent Ap with port p is represented as a single place net with a speci c ring rule (semantics): Ap = (fpg; Tp; Fp) for p 2 P where: Tp is a set of transitions, i.e. actions inserting send or receive operations in the port p, Fp : Tp fpg ! Cp is a set of arrows from transitions to place p, each arrow labelled with a send or receive operation the agent Ap can issue, i.e. Cp C f g: Suppose no agent can send/receive message to/from itself. That is: Fp(t; p) is either !(pk1 ; pk2 ; :::) or ?(pl1 ; pl2 ; :::) with pki 6= p 6= plj (i = 1; 2; :::; j = 1; 2; :::).
The local communication state (for short: a local state) of the agent Ap is a function Mp : fpg ! Cp [ f g: The set of all states of the agent Ap is Sp = (Cp [ f g)fpg Semantics of transition t 2 Tp is a relation [[t]] Sp Sp de ned by (Mp; Mp0 ) 2 [[t]] i Mp(p) = ^ Mp0 (p) = Fp(t; p) (Mp0 is the next state following Mp obtained in e ect of ring transition t) Semantics of agent Ap : [[Ap]] =
S [[t]] t2Tp Fig.1 depicts agent Ap capable of communicating with agents Ap1 ; Ap2 ; Ap3 , Ap4 , Ap5 and passing from the state Mp = f(p; )g to the state Mp0 = f(p; !(p1; p4)g as a result of ring transition t3. This means that Ap issued a request for sending a message to Ap1 and Ap4 .
The global communication state (for short: a global state) of the system A is a function M : P ! C, their set S = CP , thus the local state Mp is a restriction of M to f g
p . The state (global and local) will be treated as a set of pairs of the form (p; !(pk1 ; pk2 ; :::)) and (p; ?(pl1 ; pl2 ; :::)) for p; pk1 ; pk2 ; pl1 ; pl2 ::: 2 P . For n; m 1; let a1; :::; an and b1; :::; bm, pairwise distinct, be ports of agents Aa1 ; :::; Aan and Ab1 ; :::; Abm . Let ai:!(b1; :::; bm) denote the pair (ai; !(b1; :::; bm)) meaning "agent Aai sends a message to agents Ab1 ; :::; Abm " and bj :?(a1; :::; an) the pair (bj ; ?(a1; :::; an)) meaning "agent Abj receives a message from agents Aa1 ; :::; Aan ". A transmission (matching send and receive operations) is a pair t = ( t ;t ) of sets of the form: t = fa1:!(b1; :::; bm); :::; an:!(b1; :::; bm)g (pre-set of transmission t ) t = fb1:?(a1; :::; an); :::; bm:?(a1; :::; an)g (post-set of transmission t ) Let t = t [t and t # P be a projection of t onto the set P , i.e. t # P = fa1; :::; an; b1; :::; bmg, that is, the set of ports the transmission t is involved in. Note that t is of the same type as the global state M : both are sets of pairs of the form (x; !(:::)) or (x; ?(:::)): Expressions ai:!(b1; :::; bm) and bj :?(a1; :::; an) denote matching labelled communication operations.
Note that a transmission depends on a state: it may come into existence in a certain global state and disapear in another. Such emerging and disappearing during system's activity transmissions are typed in bold letters, to distinguish them from the static transitions of the agents. Let TR denote the set of all possible transmissions in the system. If a transmission t 2TR exists in a state M (i.e. t M ) then its semantics is a relation [[t ]] S S de ned by (M; M 0) 2 [[t ]] i M 0 = M t [f(x; )j x 2 t # P g. This means that M 0 is M in which all pairs (x; !(:::)) and (x; ?(:::)) belonging to t are replaced with pairs (x; ), i.e. M 0 is the result of " ring" transmission t at the state M . This models the transfer of a message from senders to receivers and disruption of the communication channel.
In Fig.2 a collection of 6 ports of agents Ap; Ap1 ; Ap2 ; Ap3 ; Ap4 ; Ap5 are depicted. The global state of this system is
M =
p p1 p2 p3 p4 p5 !(p1; p4) ?(p) ?(p) Transmission t = (f(p:!(p1; p4))g; f(p1:?(p); (p4:?(p))g) transforms M into M 0 =
p p1 p2 p3 p4 p5 in e ect of sending simultaneously a message from agent Ap to Ap1 and Ap4 A transmission t 2TR exists in a global state M of the system A i t M . Given a global state M0 and a transmission t , the realizability of t starting computation from M0 is expressed as: does there exist a state M reachable from M0 such that t M ? Thus, the existence problem for t reduces to some versions of state reachability and inclusion problems. Their solution in the form of yes/no decision and, possibly, their complexity, depends obviously on the formal description of agents. For example, let us assume that agents are described as 1-safe nite Petri nets (places are valued in the set f0,1g) obtained by replacing labels of arrows entering ports by weights 1. Then, the existence of t reduces to the problem "For a given marking M0 and place p, is there a reachable from M0 marking with a token in p?", which is known to be the PSPACE-hard (PSPACE - the set of all decision problems solvable by a Turing machine with a polynomial amount of space), see e.g. [ESP 1998]. Indeed, after the replacement of arrow labels, the whole system becomes one disconnected 1-safe Petri net. Denote by m0 the marking of it, such that each place (port) x 2 t # P holds a token (i.e. m0(x) = 1) i M0(x) 6= . In such system net each x 2 t # P has no outgoing arrow, thus, if a token enters this place at a certain marking reachable from m0, then it will stay there inde nitely. Now, decide if there is a marking m reachable from m0 and satisfying m(x) = 1 for all x 2 t # P . If yes (and only if), then in the original system (before replacement of the labels of arrows entering ports) there exists the transmission t , because t M , where M is m restricted to ports x 2 t # P holding communication operations !(:::) and ?(:::) instead of tokens.
Note that the assumption on agents' internal (i.e. without communication)
activity as speci ed by Petri nets, corresponds to the concept of self-modifying
nets
Let T = S Tp and F = S Fp i.e. the set of all transitions and arrows in p2P p2P the system A respectively. The triple A = (P; T; F ), denoted also by A, is a net representation of the system. Its semantics is the union of semantics of the transitions t 2 T and message transmissions t 2TR: [[A]] = S [[ ]]. If 2T [TR (M; M 0) 2 [[A]] then M 0 is the next to M state evoked by a transition t 2 T or a transmission t 2TR. For 2 V = T [ TR denote M ! M 0 i (M; M 0) 2 [[ ]]. A run starting at M0 is a chain M0 !1 M1 !2 M2 !3 :::, nite or in nite, but if nite M0 !1 M1 !2 M2 !3 ::: !n Mn then none M satis es (Mn; M ) 2 [[A]]. A nite or in nite word v = 1 2 3::: 2 V ! = V [ V 1 oVccurtrhinegn atMthisv!ruMn 0is adepnaotthesstaMrting!1atMM1 0. !I2f Mni2te !3v =::: 1!n2 M3::0:: nTh2e set of all nite and in nite runs starting at M is RU N (M ) and RU N1(M ) respectively and RU N (M ) = RU N (M ) [ RU N1(M ). The set of respective paths is P AT H(M ) = P AT H (M ) [ P AT H1(M ), thus P AT H(M ) V !.
Assuming, as above, that agents are described by 1-safe Petri nets obtained by replacing labels of arrows entering ports by weights 1, one can simulate behaviour of the system by a 1-safe net as follows. Let a state M be given. For each transmission t 2TR create a transition t 2= T de ned as t = ( t; t ) with t = t # P , t = ;, and make arrows from ports p 2 t # P to t. The extended net is a triple A = (P; T ; F ), where T = T [ set of newly created transitions, and F = F [ set of newly created arrows weighted with 1. A marking of A is obtained from marking of A by replacing operations !(:::), ?(:::) with tokens wherever such operations are in some ports and removing from remaining ports. Fig.3 depicts a simulation of transmission t from Fig.2 by the newly created transition t and result of its ring. Remember: while t appears and disapears in the course of the system activity, the transition t 2 T is the ordinary transition of the Petri net A simulating system A, thus a unchangeable member of the A's static structure.
Some problems concerning behaviour of the system A may be reduced to problems concerning behaviour of the Petri net A: To mention a few (suppose runs start from a given marking): a. Existence of run with a given message transmission occurrence b. Existence of reachable dead marking (no transition can re at it) c. Existence of nite run (equivalent to b) d. Existence of in nite run e. Existence of run with in nite number of a given message transmission occurrence f. Existence of run with never accomplished a given request for communication All these problems are PSPACE-hard for 1-safe Petri nets ([ESP 1998]) and A is such net. Therefore, by virtue of the obviously polynomial simulation procedure described above, the problems for systems speci ed like A in this paper, are PSPACE-hard provided that internal activity of agents is speci ed by 1-safe Petri nets.
Out of several concepts and kinds of deadlock and fairness found in diverse models of distributed computing, let us consider those arising from communication and described in terms of the model pursued here. 4.1
System A is deadlock-free at a state M if for each agent requesting for communication there is a nite path starting at M , such that the agent will be permitted to accomplish the request on this path. A deadlock is a negation of this property. For an agent Ap 2 A = (P; T; F ), with port p and for a state M 2 S de ne: def Dp(M ) () :[9M 0:9v:(M v! M 0 ^ 9t :(t 2 v ^ p:M (p) 2 t ))] where t 2 v means "transmission t 2TR occurs on the path v" and p:M (p) 2 t means "t accomplishes request for communication issued by agent Ap and pending at the state M ".
In words: never agent Ap requesting for communication at the state M will be permitted to accomplish the request by a certain transmission occurring on whichever nite path starting at M .
The system is subject to a deadlock at the state M i : 9p:M (p) 6= ^ Dp(M ).
Dp(M ) if and only if P AT H(M ) \ V t V t = ; for each t satisfying p:M (p) 2
Dp(M ) () :9M 0:9v:(M :9v:9M 0:(M 8v::9M 0:(M 8v::((9M 0:M 8v:(:(9M 0:M 8v:((9M 0:M 8v:(v 2 fuj 9M 0:M P AT H(M )) v! M 0 ^ 9t :(t 2 v ^ p:M (p) 2 v! M 0 ^ 9t :(t 2 v ^ p:M (p) 2 v! M 0 ^ 9t :(t 2 v ^ p:M (p) 2 |
no M0 in {thzis formula v! M 0) ^ 9t :(t 2 v ^ p:M (p) 2 v! M 0) _ :9t :(t 2 v ^ p:M (p) 2 v! M 0) ) :9t :(t 2 v ^ p:M (p) 2 u ! M 0g ) :9t :(t 2 v ^ p:M (p) 2 fvj :9t :(t 2 v ^ p:M (p) 2 P AT H(M ) P AT H(M )
P AT H(M ) V V t V for each t satisfying p:M (p) 2 t where V t V is the set of all nite words over V where t occurs. Thus: if p:M (p) 2 t then P AT H(M ) (V V t V ) = ;.
Since X (Y Z) = (X Y ) [ (X \ Z) for any sets X; Y; Z then P AT H(M ) (V V t V ) = (P AT H(M ) V ) [ (P AT H(M ) \ V t V ) = ; (Because P AT H(M ) V = ;). Finally: Dp(M ) i 8t .(p:M (p) 2 t ) P AT H(M ) \ V t V = ;) 2
A deadlock at a state M occurs i : 9p:[M (p) 6= ^ (8t .(p:M (p) 2 t ) P AT H(M ) \ V t V = ;))] 2 Thus decidability of such deadlocks reduces to deciding whether transmission t does not occur on any path starting from M (provided that there are a nite number of agents, thus also transmissions), which depends on algebraic structure of the set P AT H(M ). 4.2
System A is weakly fair at a state M if each agent requesting for communication at M will be permitted to accomplish the request on every in nite path starting from M . This is expressed by the formula:
8v:(v 2 P AT H1(M ) ) 9t :(t 2 v ^ p:M (p) 2 fvj v 2 P AT H1(M )g fvj 9t :(t 2 v ^ p:M (p) 2 t )g () P AT H1(M ) V t V 1 for each t satisfying p:M (p) 2 t . Thus 8t .(p:M (p) 2 t ) P AT H1(M ) V t V 1 = ;)
System A is strongly fair at a state M if each agent requesting for communication at M will be permitted to accomplish the request on every nite path starting at M if all these paths are "su ciently long", i.e. of the length at least k, for a certain k. So, all these paths may be jointly ("uniformly") bounded in lentgh. This is expressed by the formula: 8p:[M (p) 6= ) 9k:Fp(M; k)] where
def Fp(M; k) () 8v:((v 2 P AT H (M ) ^ jvj k) ) 9t :(t 2 v ^ p:M (p) 2 t )
To demonstrate the equivalence between the two kinds of fairness in the model considered here, let us recall a version of the:
Let be a set and a tree of the properties: { the number of sons of every node in is nite; { for any k 0 there is a nite branch b in with jbj k and b
with jBj
The weak and strong fairness are equivalent.
By the Theorem 4.2.1 and 4.3.1 it su ces to demonstrate that jP AT H (M ) V t V j < 1 () P AT H1(M ) V t V 1 = ; for each transmission t such that p:M (p) 2 t for every port p with M (p) 6= . Implication ")" is evident, it remains to show "(". Suppose jP AT H (M ) V t V j = 1. Note that the set of paths starting at M is pre xclosed: each pre x of v 2 P AT H(M ) belongs to P AT H(M ). To each v assign a unique element node(v) in this way that v1 6= v2 ) node(v1) 6= node(v2) and let N ODE(M ) = fnode(v)j v 2 P AT H (M )g. This set with internodal relation de ned by "node(u) is father of node(v) i v = u for a certain 2 V " is a tree with node(") as the root (" is the empty path) and nitely many sons of each father. So, every path v 2 P AT H (M ) is a branch in . By assumption jP AT H (M ) V t V j = 1 there are in nitely many nite paths, thus branches in on which no t exists. Therefore there must be an arbitrarily long branch in the tree. Setting = P AT H (M ) and applying the Konig's Lemma, we come to contradition. 2 Summing up the results obtained above, the set-theoretic characteristics of the deadlock and fairness at a state M are in the following table:
Deadlock P AT H(M ) \ V t V = ; Weak fairness P AT H1(M ) V t V 1 = ;
Strong fairness jP AT H (M ) V t V j < 1 for every transmission t . 5
If the agents do not send and receive messages to/from themselves then the total number of (global) states of n-agent system is (2n 1)n. Indeed, each agent may issue 2n 1 send !(:::) requests and the same number of receive ?(:::) requests, that is 22n 2 requests for communication. Since the agent may assume as its local state, the number of local states it may assume is 2n 1. The set of global states is the Cartesian product of sets of the local states of all agents. Therefore the number of global states is (2n 1) ::: (2n 1) = (2n 1)n. For instance, | }
n t{imzes for agents p1; p2; p3: the set of local states of p1 = f ; !(p2); ?(p2); !(p3); ?(p3); !(p2; p3); ?(p2; p3)g the set of local states of p2 = f ; !(p1); ?(p1); !(p3); ?(p3); !(p1; p3); ?(p1; p3)g the set of local states of p3 = f ; !(p1); ?(p1); !(p2); ?(p2); !(p1; p2); ?(p1; p2)g Thus, the system of three agents has 73 = 343 global states.