J M Fourneau

B Plateau

W Stewart

Product form for Stochastic Automata Networks

Keywords: C.4 [Performance of Systems]: Modeling techniques, Performance attributes, G.3 [Probability and Statistics]: Markov processes Continuous Time Markov Chain, Product form steady-state distribution, Stochastic Automata Networks

We consider Stochastic Automata Networks (SAN) in continuous time and we prove a sufficient condition for the steady-state distribution to have product form. We consider SAN without synchronizations where the transitions of one automaton may depend of the states of the other automata. Even with this restriction, this sufficient condition is quite simple and this theorem generalizes former results on SAN but also on modulated Markovian queues, such as the Boucherie's theory on competing Markov chain, or on reversible queues considered by Kelly. The sufficient condition and the proof are purely algebraic.

INTRODUCTION

Since they have been introduced by B. Plateau [START_REF] Plateau | On the stochastic structure of parallelism and synchronization models for distributed algorithms[END_REF] to evaluate the performance of distributed algorithms, Stochastic Automata Networks (SAN for short) have been associated to new research on numerical resolution of finite Markov chains. The key idea is to take into account the tensor decomposition of the transition matrix of a SAN to improve the storage of the model and the complexity of the vector-matrix product [START_REF] Fernandes | Optimizing tensor product computations in san[END_REF]. The first algorithm proposed was a numerical resolution of the steady-state distribution of the Markov chain associated to a SAN [START_REF] Plateau | Peps: A package for solving complex markov models of parallel systems[END_REF] using the power method. Since then, several numerical methods have been investigated.

As a SAN is a modular decomposition into automata which are connected by synchronized transitions and functions, SAN are closely related to Stochastic Process Algebra, (see for instance PEPA [START_REF] Hillston | A compositional approach to Performance Modeling[END_REF]). Therefore, new results on SAN may be easily translated into other models based on composition. The tensor decomposition of the generator has been generalized for Stochastic Petri Nets (see for instance [START_REF] Donatelli | Superposed stochastic automata: A class of stochastic petri nets with parallel solution and distributed state space[END_REF]), Stochastic Process Algebra [START_REF] Hillston | An efficient kronecker representation for pepa models[END_REF] and other modular specification methods as well.

After a decade of numerical analysis, some analytical results for SAN have been proved. First, B. Plateau et al. [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF] have investigated SAN without synchronization. They proved that a product form steady-state distribution exists as soon as some local balance conditions are satisfied. Even without synchronization, the transitions of the automata are still dependent because of functional rates. Plateau's result is closely related to Boucherie's result on Markov chains in competition [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF] and Robertazzi's theorems on Petri nets [START_REF] Lazar | Markovian petri net protocols with product form solution[END_REF]. Similarly, using the same type of argument (i.e. group local balance), Sereno has proved a sufficient condition to obtain a product form solution for a PEPA model [START_REF] Sereno | Towards a product form solution for stochastic process algebras[END_REF] without functional rates.

In [START_REF] Boujdaine | Product form solution for stochastic automata networks with synchronizations[END_REF], the authors have considered SAN without function but with a special case of synchronization denoted as limited synchronization. The usual assumption on synchronization used to define the SAN methodology was the "Rendez-Vous" between an arbitrary number of automata with arbitrary transitions. In a limited synchronization, only two automata are really active. The effects of such a synchronization on other automata in the network are simple loops. The authors had proved a sufficient condition to have a product form steady-state distribution: existence of a solution for a fixed-point system between the instantaneous arrival rate and the steady-state distributions of the automata in isolation. Some typical queueing networks such as Jackson's networks or Gelenbe's networks of positive and negative customers [START_REF] Gelenbe | Product form queueing networks with negative and positive customers[END_REF] are examples of this type of SAN. For both networks, the fixed-point system is equivalent to the well-known flow equation.

In [START_REF] Fourneau | Domino synchronization: product form solution for stochastic automata networks[END_REF], one of us had considered a completely different kind of synchronization: the Domino synchronization. Briefly, a Domino synchronization is an ordered list of tuples (automaton number, list of transitions inside this automaton). The synchronization takes place according to the order in the list. The synchronization may completely succeed or be only partial if some conditions are not satisfied. Again it is proved that the existence of a solution to some fixed point system is a sufficient condition to obtain a product form solution.

Here we consider again SAN without synchronizations and we generalize the results obtained in [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF]. We consider SANs without synchronization. This does not imply that the au-tomata are independent because the transition rate in one automaton may depend on the states of others automata. This model is general enough to represent all multidimensional Markov chains where the rates are dependent of the states of one or several components. This is typically the case of Competing Markov chains considered by Boucherie [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF], some Petri nets modeled by Robertazzi [START_REF] Lazar | Markovian petri net protocols with product form solution[END_REF], and modulated Markov chains. We obtain a very simple algebraic condition using an elementary algebraic proof. This assumption does not require that the local behaviors will always be irreducible for any value of the modulating states. The only requirement is the global irreducibility of the Markov chain and the existence of commons eigenvectors in the kernels of sets of matrices. We also show that this property is somehow related to some important concepts already known in queueing networks theory like reversibility and local balance property.

The rest of the paper is organized as follows: in section II we present a brief introduction to SAN and we show the universality of this description to represent multidimensional modulated Markov chains. Section III is devoted to the proof of the sufficient condition of product form while in section IV we show the links to known results and we present new product theorems based on our necessary condition.

INTRODUCING SAN

A Stochastic Automata Network (SAN) consists of a number of individual stochastic automata that operate more or less independently of each other. Each individual automaton, A, is represented by a number of states and rules that govern the manner in which it moves from one state to the next. The state of an automaton at any time t is just the state it occupies at time t and the state of the SAN at time t is given by the state of each of its constituent automata.

We first consider a set of non-interacting automata. Then we add the synchronizations and functions to represent the dependence between automata. As our approach here is limited to SAN without synchronizations we put more emphasis on functions.

Non-Interacting Stochastic Automata

We present an example rather than the general theory which can be found now in many publications [START_REF] Fernandes | Efficient descriptor-vector multiplications in stochastic automata networks[END_REF][START_REF] Fernandes | Optimizing tensor product computations in san[END_REF][START_REF] Benoit | On the benefits of using functional transitions and kronecker algebra[END_REF][START_REF] Plateau | A methodology for solving markov models of parallel systems[END_REF][START_REF] Plateau | Peps: A package for solving complex markov models of parallel systems[END_REF].

Example 1. Consider the case of a system that may be modelled by two completely independent stochastic automata, each of which may be represented by a continuous-time Markov chain. Let us assume that the first automaton, denoted A (1) , has n1 states and transition rate matrix given by Q (1) ∈ R n 1 ×n 1 . Similarly, let A (2) denote the second automaton; n2, the number of states in its representation and Q (2) ∈ R n 2 ×n 2 , its transition rate matrix. The state of the overall (two-dimensional) system may be represented by the pair (i, j) where i ∈ {1, 2, . . . , n1} and j ∈ {1, 2, . . . , n2}, and the infinitesimal generator of the two-dimensional system is given by Q (1) ⊕ Q (2) where ⊕ is the tensor sum. Remember that with Now given N independent stochastic automata, A (1) , A (2) , . . ., A (N ) , with associated infinitesimal generators, Q (1) , Q (2) , . . . , Q (N ) , and probability distributions π (1) (t), π (2) (t), . . ., π (N ) (t) at time t, the infinitesimal generator of the Ndimensional system, which we shall refer to as the global generator, is given by

A = " a11 a12
Q = ⊕ N k=1 Q (k) = N X k=1 In 1 ⊗• • •⊗In k-1 ⊗Q (k) ⊗In k+1 ⊗• • •⊗In N (1)
where ⊗ is the tensor product. The probability that the system is in state (i1, i2, . . . , iN ) at time t, where i k is the state of the k th automaton at time t with 1 ≤ i k ≤ n k and n k is the number of states in the k th automaton, is given by

Q N k=1 π (k) i k (t) where π (k) i k (t)
is the probability that the k th automaton is in state i k at time t. Furthermore, the probability distribution of the N -dimensional system, π(t), is given by the tensor product of the probability vectors of the individual automaton at time t, i.e.,

π(t) = ⊗ N k=1 π (k) (t). (2)
To solve N -dimensional systems that are formed from independent stochastic automata is therefore very simple. It suffices to solve for the probability distributions of the individual stochastic automata and to form the tensor product of these distributions. This resolves the case of independent stochastic automata, and we now turn our attention to automata that interact with each other

Interacting Stochastic Automata

There are two ways in which stochastic automata interact:

1. The rate at which a transition occurs may be a function of the state of a set of automata. Such transitions are called functional transitions. Transitions that are not functional are said to be constant.

2.

A transition in one automaton may force a transition to occur in one or more other automata. We allow for both the possibility of a master/slave relationship, in which an action in one automaton (the master) actually occasions a transition in one or more other automata (the slaves), and for the case of a rendez-vous in which the presence (or absence) of two or more automata in designated states causes (or prevents) transitions to occur. We refer to such transitions collectively under the name of synchronized transitions. Synchronized transitions are triggered by a synchronizing event; indeed, a single synchronizing event will generally cause multiple synchronized transitions. Transitions that are not synchronized are said to be local.

The elements in the matrix representation of any single stochastic automaton are either constants, i.e., nonnegative real numbers, or functions from the global state space to the nonnegative reals. Transition rates that depend only on the state of the automaton itself, and not on the state of any other automaton, are to all intents and purposes, constant transition rates. A synchronized transition may be either functional or constant. The same is true for local transitions.

Consider as an example, a simple queueing network consisting of two service centers in tandem and an arrival process that is Poisson at rate λ. Each service center consists of an infinite queue and a single server. The service time distribution of the first server is assumed to be exponential at fixed rate µ, while the service time distribution at the second is taken to be exponential with a rate ν that varies with the number and distribution of customers in the network. Since a state of the network is completely described by the pair (n1, n2) where n1 denotes the number of customers at station 1 and n2 the number at station 2, the service rate at station 2 is more properly written as ν(n1, n2).

We may define two stochastic automata A (1) and A (2) corresponding to the two different service centers. The state space of each is given by the set of nonnegative integers {0, 1, 2, . . . , } since any nonnegative number of customers may be in either station. Transitions in A (2) depend on the first automaton in two ways. Firstly the rate at which customers are served in the second station depends on the number of customers in the network and hence, in particular, on the number at the first station. Thus A (2) contains functional transition rates, (ν(n1, n2)). Secondly, when a departure occurs from the first station, a customer enters the second and therefore instantaneously forces a transition to occur within the second automaton. The state of the second automaton is instantaneously changed from n2 to n2 +1. This entails transitions of the second type, namely synchronized transitions. The event, "departure from station 1", is a synchronizing event.

Building Generators using Functional Transitions

We return to the two original automata given in example 1 and consider what happens when one of the transition rates of the second automaton becomes a functional transition rate. Suppose, for example, that the rate of transition from state 2 to state 3 in the second automaton is μ2 when the first automaton is in state 1 and μ2 when the first automaton is in state 2. The global infinitesimal generator is now ( * is the normalization):

0 B B B B B @ * µ1 0 λ1 0 0 0 * μ2 0 λ1 0 µ3 0 * 0 0 λ1 λ2 0 0 * µ1 0 0 λ2 0 0 * μ2 0 0 λ2 µ3 0 * 1 C C C C C A .
If, in addition, the rate at which the first automaton produces transitions from state 1 to state 2 is λ1, λ1 and λ1 depending on whether the second automaton is in state 1, 2 or 3, the two-dimensional infinitesimal generator is given by

0 B B B B B B @ * µ1 0 λ1 0 0 0 * μ2 0 λ1 0 µ3 0 * 0 0 λ1 λ2 0 0 * µ1 0 0 λ2 0 0 * μ2 0 0 λ2 µ3 0 * 1 C C C C C C A .
It is known for a long time that the introduction of functional transition rates has no effect on the structure of the global transition rate matrix other than when functions evaluate to zero in which case a degenerate form of the original structure is obtained. However, even if the structure is preserved, the actual values of the nonzero elements prevents us from writing the solution in the simple form of equation ( 2). Nevertheless it is still possible to profit from this unaltered nonzero structure. This is the concept behind the extended (generalized) tensor algebraic approach, [START_REF] Plateau | A methodology for solving markov models of parallel systems[END_REF]. The descriptor is still written as in equation ( 1), but now the elements of Q (i) j may be functions. This means that it is necessary to track elements that are functions and to substitute (or recompute) the appropriate numerical value each time the functional rate is needed.

notation

The following notations will be used in the paper.

• The number of automata is N .

• i, and j will be state indices • l will be an automaton index • m will be a matrix index.

• Q (l) is the transition rate matrix which describes the local transition of automaton l.

• k is a state of the Markov chain. k l is the state of automata l when the global state is k. k is a N component vector.

• k|l is the N -1 component vector obtained from k after deletion of component l.

• k + (l, i) is the N component vector obtained from k after replacing the value of component l by i.

We assume that the SAN contains functions. So all the matrices are functional and we note Q l [i, j]( k, k ′ ) the entry of matrix Q l for a transition from i to j in automaton l when the global state is k and it changes to k ′ due to the transition.

PRODUCT FORM OF SAN WITHOUT SYNCHRONIZATION

Assume that the steady-state distribution has a product form ( P r(x0, .., xn) = Cπ1(x1)...πn(xn)). We investigate some sufficient condition for such a condition to exist but we do not provide algorithm to compute the normalization constraint C.

In this paper we introduce a simple property which, to the best of our knowledge, has not been considered before, at least in the context of steady-state distribution of CTMC: a positive vector which belongs to the kernels of all the transition rate matrices. Note that in the following we use the word kernel for left kernel or left nullspace. Definition 1. Let α be a probability distribution. We note by S(α) the set of transition rate matrices M such that αM = 0 (i.e. α is in the the kernel of all matrices in S(α)).

Property 1. S(α) has a several interesting properties:

1. 0 (the matrix whose elements are all zero) is in S(α) 2. aM 1 is in S(α). for all matrices M 1 in S(α) and a in R + .

3. aM 1 + bM 2 is in S(α) for all matrices M 1 and M 2 in S(α) and a, b in R + such that a + b = 1.

We will see that Boucherie's theory of competing chains is somehow linked to property 1, that the key idea of our previous work on SAN is property 2 while the algebraic interpretations of local balance and reversibility are connected to property 3.

To introduce the assumptions and the proofs, we first consider the Chapman-Kolmogorov equation for steady-state:

P r( k) 2 4 n X l=1 X i =k l Q (l) [k l , i]( k, k + (l, i)) 3 5 = n X l=1 X i =k l Q (l) [i, k l ]( k + (l, i), k)P r( k + (l, i)). (3)
For the right rand side, we simply consider all the transitions into k resulting from any movement of automaton l which moves to state k l . For the left hand side we write all the transitions leaving state k due to a movement of automaton l which jumps out of state k l . Note that we do not have dummy transitions because the summation on state i which differs from k l .

To improve the previous results already published on this subject it is necessary to change the way we represent functions. Remember that we consider discrete state spaces, thus the functions argument are denumerable. For any function we have in the model, we only have a denumerable set of values reached by this function. Instead of using a function terminology, we evaluate the functions and the matrices and put the matrices in a set and use an index. Let us now introduce this idea more formally. Definition 2. Let l be an automaton index, we consider all the functions in matrix Q (l) and we evaluate them for all state k when the transition from k to k + (l, i) takes place. Such a matrix will be denoted by L (l,m( k)) where m( k) is an index. The set of matrices L (l,m( k)) will be denoted by F (l) .

Let us first present a small model which may have product form solution for some particular functions.

Example 2. We consider a network with two automata A1 and A2. Both have a very simple state space: {0, 1} (see figure 1). The transitions in A1 have a fixed rate l1 for the transition from 0 to 1 and l2 for the transition from 1 to 0. Automaton A2 has two functional transitions: the rate from 0 to 1 has a functional rate f 1 and the reverse transitions has functional rate f 2. Both functions use the state of automaton A1 as an argument.

We assume that the functions are f 1(x1) = mb + m(1b)1x1=0 and f 2(x1) = m1+m21x1=0 where x1 is the current state of automaton A1, 1x is an indicator function and b is a positive values smaller than 1. Thus:

• if automaton A1 is in state 0, the rates are respectively m and m1 + m2 for the transition from 0 to 1 and for the reverse transition. • if automaton A1 is in state 0, the rates are mb and m1.

We depict in figure 2 the Markov chain of this SAN and we now compute the two matrices associated to automaton A2. We now state and prove the main results about product form for a SAN without synchronization. We assume that the Markov chain is irreducible and positive recurrent. Thus a steady state distribution exists. Note that as the assumptions we made on the matrices are very weak, they do not prove irreducibility of the Markov chain. For some particular cases however the assumptions on the local matrices implies the irreducibility of the chain.

M 0 = " -m m m1 + m2 -m1 -m2 « and M 1 = " -m b m b m1 -m1 « ✁ ✁ ✂ ✂ ✄ ✄ ☎ ☎ ✆ ✆ ✝ ✝ ✞ ✞ (0,0) (1,1) l1 l2 l1 l2 m m1+m2 m1 m b (0,1) (1,0)
Theorem 1. Consider a SAN with functions but without synchronizations. Assume that the steady state exists. If for each automaton l there exists a probability distribution π l such that all the matrices in F (l) are in S(π l ), then the SAN has a product form steady state distribution such that: P r(x0, .., xn) = Cπ1(x1) . . . π l x l πn(xn).

Proof: First we write a new version of the global balance equation after substitution of the new index for functions:

P r( k) 2 4 n X l=1 X i =k l L (l,m( k)) [k l , i] 3 5 = n X l=1 X i =k l L (l,m( k)) [i, k l ]P r( k + (l, i)) . (4)
We divide both sides of the equation by P r( k) and we take into account the usual simplification rule:

P r( k + (l, i)) P r( k) = π l (i) π l (k l ) .
Thus we get:

n X l=1 2 4 X i =k l L (l,m( k)) [k l , i] 3 5 = n X l=1 2 4 X i =k l L (l,m( k)) [i, k l ] π l (i) π l (k l ) 3 5
.

But L (l,m( k)) is a transition rate matrix and for every k l we have:

X i =k l L (l,m( k)) [k l , i] = -L (l,m( k)) [k l , k l ].
After substitution we get:

n X l=1 h -L (l,m( k)) [k l , k l ] i = n X l=1 2 4 X i =k l L (l,m( k)) [i, k l ] π l (i) π l (k l ) 3 5 .
(

) 5
Now remember that for all index m( k), matrix L (l,m( k)) satisfies:

πiL (l,m( k)) = 0.
Therefore equation ( 5) is satisfied and we have proved that the SAN has a steady state distribution probability.

Corollary 1. Consider again the SAN of example 2 matrices M 0 and M 1 have the same kernel if b = m1 m1+m2 . If this condition is satisfied, the steady-state distribution of the SAN has product form:

π(x1, x2) = C " l1 l2
« x1 " m m1 + m2 « x2
.

We now present some examples and links to other theorems already published to show that we generalize many concepts and results on Markovian Petri nets, competing Markov chains, modulated set of queues and Stochastic Automata Networks. But before proceeding with this examples, let us make some remarks concerning our main theorem.

• First, it is not necessary for all the matrices to be irreducible. But the matrix resulting of SAN description must be irreducible.

Example 3. Consider again the SAN in Fig. 1. We now change the functions f 0 to be m1x1=0 and f 1 to be m11x1=1. The global Markov chain is irreducible (see Fig. 3) but the matrices associated to automaton A2 are not irreducible. Indeed: However note that we do not claim that this SAN has a product form.

M 0 = " -m m 0 0 « and M 1 = " 0 0 m1 -m1 « . ✁ ✁ ✂ ✂ ✄ ✄ ☎ ☎ ✆ ✆ ✝ ✝ ✞ ✞ (0,0) (1,1)
• It is possible that some matrices in the model have some rows equal to the null vector. To provide an example of such a system with product form we must consider a model based on larger state space.

Example 4. We consider a network with two automata A1 and A2. A2 has a very simple state space: {0, 1} while A1 has four states (see Fig 4). The transitions in A2 have a fixed rate l2 for the transition from 0 to 1 and m2 for the transition from 1 to 0. Automaton A1 contains four functional transitions governed by four functions f 1, f 2, f 3 and f 4. More precisely: Let us now describe the functions:

Q 1 = 0 B B @ -l1 l1 0 0 m1 -m1 -f 1 f 1 0 0 f 2 -f 2 -f 3 f 3 0 0 f 4 -f 4 1 C C A .
8 > > < > > : f 1 = l1 1x2=1 f 2 = m1 1x2=1 f 3 = l1 1x2=0 f 4 = m1 1x2=0
Thus the matrices associated to automaton A1 are:

M 0 = 0 B B @ -l1 l1 0 0 m1 -m1 0 0 0 0 -l1 l1 0 0 m1 m1 1 C C A and M 1 = 0 B B @ -l1 l1 0 0 m1 -m1 -l1 l1 0 0 m1 -m1 0 0 0 0 0 1 C C A .
Let us now find the kernel of both matrices. For M 0 we obtain the set of vectors {u (m1, l1, 0, 0) + v (0, 0, m1, l1), ∀ u, v ∈ R} while the kernel of M 1 is {u (1, l1/m1, l1 2 /m1 2 , 0) + v (0, 0, 0, 1), ∀ u, v ∈ R}.

Clearly the vector (1, l1/m1, l1 2 /m1 2 , l1 3 /m1 3 ) is in both sets and Theorem 1 proves that we have a product form solution.

LINKS TO RELATED WORKS

We first show that previous results on product form SAN satisfy the condition of theorem 1.

Previous Results on SAN

In [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF] some of us have considered Stochastic Automata Networks without synchronizations and they have proved three sufficient conditions to obtain product form. As the second and third one are related to reversibility which will be presented in the next pages we only present here the first case.

Theorem 2 (Case 1 in [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF]). Assume that the Stochastic Automata Network contains functional rates but no synchronization. The local transitions are described by functional matrices L (l,m( k)) . Assume that for every automaton index l L (l,m( k)) is the product of a constant matrix L (l) by a function f l ( k|l) which does not use automaton l as an argument. Assume that matrix L (l) is an ergodic stochastic matrix the steady-state distribution of which is π l . Then the steady-state distribution of the chain has product form.

π( k) = C Y l π l
where C is a normalization constant.

The proof in [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF] of this theorem is based on algebraic manipulations of the global balance equation. Note that in this case, the local matrices must be irreducible. We know show that this theorem is a simple corollary of theorem 1.

Property 2. Assume that matrices L (l,m( k)) are the product of a constant matrix L (l) by a function f l ( k|l) which does not use the state of automaton l as an argument, then all matrices L (l,m( k)) associated to automaton l have the same kernel.

Proof: For all l we have L (l,m( k)) = f l ( k|l)L (l) . And π l L (l) = 0. Thus π l f l ( k|l)L (l) = 0 for all k|l. And after substitution π l L (l,m( k)) = 0. Therefore matrices L (l,m( k)) are all in set S(π l ).

Due to this property, we clearly state that Theorem 1 generalizes this first result in our previous paper. But Theorem 2 (i.e. the first case in [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF] was already a generalization of a long list of results on the product form of chains which model agents competing overs resources. The typical model of such as system is the dining philosophers problem which have been shown to have product form for a long time [START_REF] Zenie | Colored stochastic petri nets[END_REF][START_REF] Wang | Service stage petri net models with product form solution[END_REF][START_REF] Lazar | Markovian petri net protocols with product form solution[END_REF][START_REF] Ycart | The philosopher's process: an ergodic reversible nearest particle system[END_REF] using many modeling techniques and theoretical frameworks. The most relevant results were presented by Boucherie in [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF].

Competing Markov Chain

Boucherie had introduced in [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF] a new framework to generalize Petri nets with product form. This theory was denoted as competing Markov chains. He proved two theorems on product form: the first one with a more restrictive definition of resource and blocking (Th 2.6 in Boucherie's paper), and a second one where the chains in isolation must have some local balance but where the blocking over resource is weaker (Theorem 2.8 in [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF]). We now present Boucherie's first theorem. The second result is mentioned in the section on partial reversibility. We need first to introduce some concepts and notations coming from Boucherie's presentation. He considered a collection of Markov chains and he introduced a product process which has a tensor representation and some restrictions on the reachable state space due to the competition over resources. For the sake of compatibility with SAN we use a tensor representation of the process which is not the original presentation by Boucherie. Let S k be the state space of chain k. The reachable state space of the chains in competition is a subset of the Cartesian product. The transition rate matrix of the product process is the tensor sum of the transition rate matrix of the chains where some transitions have been removed. The competition over resources is modelled as an exclusion of a part of the state space S (say A) and the cancellation of some transitions. A contains the states where the resources are used by several chains. For instance, assume that automaton 1 and automaton 2 compete over resource r, if automaton 1 has resource r, all the transitions of chain 2 are cancelled. Thus the process cannot enter states in A.

For instance, Fig. 5 presents two chains X1 and X2 both with states {0, 1, 2, 3} competing over one resource. The resource is owned by a chain when it is in state 2 or 3. It is released when the chain jumps from state 3 to 1. Thus states in {2, 3} × {2, 3} are forbidden and the reachable state space of the product process is {0, 1, 2, 3} × {0, 1, 2, 3} {2, 3} × {2, 3}. When process X1 is in state 2 or 3 process X2 is stopped. If process X1 is in state 0 or 1, process X2 can move. Of course we also have the symmetrical rules when X2 owns the resource. In Fig. 5, we have depicted first the chains X1 and X2 and the product process when the chains are competing over a resource. The general definition of competing Markov chains uses a set of resources in competition I and for each resource r in I the set of chains which compete over this resource C(r).

Theorem 3. [Th 2.6 [2]] Markov chains in competition have product form (this is only a simplified presentation of Boucherie's theorem to avoid a lot of notations).

Property 3 (SAN and Competing Markov chains).

Consider a SAN modeling a set of competing Markov chains described by Boucherie's first theorem. Let L (l,m( k)) be the matrix of automaton l. Then for all automaton index l, L (l,m( k)) is the product of a constant matrix L (l) by a function f l ( k|l) which does not use the state of automaton l as an argument and which takes values in {0, 1}.

Proof: following Boucherie, the transition rate of a competing Markov chain is given by the following rules:

• if states k and k ′ differ by more than 1 components, the transition rate is 0.

• from state k to state k + (l, i) the transition is the transition rate from k l to i in chain l multiplied by an indicator function.

• This function is equal to zero when there exists a resource r owned by another chain which competes with l.

The first rule states that the transition matrix is a tensor sum of some matrices. The second rule says that these matrices are the original stochastic matrices of the chains multiplied by a function of the states and taking value in {0, 1}. Indeed as the function is the same for all the states of competing Markov chain l (or automaton l in a SAN formulation) we can write that transition matrix L (l,m( k)) is the product of a constant matrix L (l) by a function f l ( k|l).

Finally the third rule defines the functions and we can check that function f l ( k|l) do not use automaton l. As we only use indicator functions, they clearly take values in {0, 1}.

Corollary 2. Therefore Theorem 3 is a simple corollary of Theorem 2 which is itself generalized by Theorem 1.

So we have at least obtained an algebraic formulation of Boucheri Ő's first theorem and a generalization for arbitrary functions but our model allows to consider other results as well.

Reversibility and Partial Reversibility

We first introduce the definition of partial reversibility and show the links with the usual definition of reversibility. Definition 3. An ergodic Markov chain X with stochastic matrix F is partially reversible if and only if there exists a non empty subset X of the states such that for all states i and j in X we have local balance equations between i and j. More precisely let π be the steady state of F , we must have for all i, j in X,

π(i)F (i, j) = π(j)F (j, i).
The link between partial reversibility and reversibility is clear: Property 4. if X is the global set of states of the Markov chain then the matrix is reversible in the usual sense (i.e. as characterized by Kelly [START_REF] Franck | Reversibility and Stochastic Networks[END_REF], theorem 1.3 p. 6).

As shown by Kelly, many amendments can be made to the transition rates of a reversible Markov chain such as the reversibility still holds after the modification. We will see now that we have similar properties for partially reversible chains.

Property 5 (truncation). We now assume that the set S(α) contains an irreducible matrix F which is partially reversible, then all matrices obtained from F after 1. choosing any subset of X (let call it Y ) 2. deleting all the transitions between states of Y are also in S(α).

Note that we delete the transitions but we do not delete the states. Clearly the chain is not irreducible any more.

Proof: Let FY the matrix obtained after deletion of transitions between states of Y . We have FY + MY = F where MY contains the transitions between states of Y in matrix F and the normalization to be a transition rate matrix. We will prove that αFY = 0. Clearly, from the construction we have:

αFY = αF -αMY = -αMY .
Now remember that the chain is partially reversible associated to set X. For any state i and j in X we have α(i)F (i, j) = α(j)F (j, i). As Y is a subset of X, we have:

α(i)F (i, j) = α(i)MY (i, j) = α(j)F (j, i) = α(j)MY (j, i).
Therefore α(i)MY (i, j) -α(j)MY (j, i) = 0. Let Y j be the set Y except state j. We sum other all i in Y j to get:

X i∈Y j α(i)MY (i, j) -α(j) X i∈Y j MY (j, i) = 0.
We remark that

X i∈Y j MY (j, i) = -MY (j, j)
as MY is a transition rate matrix. Finally, for all j in Y we have:

X i∈Y j
α(i)MY (i, j) + α(j)MY (j, j) = 0.

As MY (i, j) is equal to 0 if i or j is not in Y , this last relation implies that αMY = 0. Thus αFY = 0. Property 6. Property 5 is a generalization of Kelly's corollary 1.10 on truncation ( [START_REF] Franck | Reversibility and Stochastic Networks[END_REF], p. 26). Indeed Kelly assumes that the chain is reversible, and that the truncated chain is irreducible, he proved that the truncated process is still reversible and that the probability distribution is the original one up to a normalization factor. When the chain in only partially reversible, the truncation described in property 5 gives the same result on the steady state distribution.

Property 5 also generalizes the second case considered in [START_REF] Plateau | Advances in Computational Probability, Chapter Stochastic Automata Networks[END_REF] where the truncation procedure is not completely specified.

Property 7. Let F be an irreducible transition rate matrix associated to an ergodic Markov chain. Let α be its steady-state distribution. Assume that the chain is partially reversible with set of states X, then for every subset Y of X we have for all i:

X j ∈Y (αjF (j, i) -αiF (i, j)) = 0.
Property 8 (multiplication). We assume that the set S(α) contains an irreducible matrix F which is partially reversible, then all matrices obtained from F after 1. choosing any subset of X (let call it Y )

multiplying all the transitions between states of Y by

an arbitrary positive constant c.

are also in S(α).

The chain is still irreducible after the modification of the rate as c > 0.

Proof: again we write F + (c -1)MY = FY where FY is the matrix obtained after modification of the rates between states of Y and MY is the initial transition rate matrix of the states in Y . We prove that αFY = 0. As the proof is quite similar to the proof of property 5 it is omitted here. then the SAN has a product form solution.

Proof: This is a simple consequence of properties 5 and 8. Note that this is not the most general result based on these properties. We still have product form if both automata are partially reversible and the functions are designed accordingly. Note that we may prove local balance between some nodes due to structural conditions on the automata.

Definition 4 (peninsula). Consider an ergodic CTMC associated to transition rate matrix F , a peninsula is a set of two nodes a, b such that:

• Removing a and b disconnects the chain and creates two connected components A and B.

• a ∈ A and b ∈ B.

• b is the only one successor of a.

• a is the only one successor of b.

A peninsula implies that we have a local balance between a and b (see equation ( 6)). The only transitions between A and B are the transition from a to b and the transition from b to a. The cut theorem for Markov chain states that:

π(a)F (a, c) = π(b)F (b, d). (6)
The assumption on the constant c in property 8 is not necessary. We can have the same property if c is not constant for all the states in Y .

Property 9 (multiplication again). We assume that the set S(α) contains an irreducible matrix F which is partially reversible. We chose any subset Y of X. We build the non diagonal elements of matrix FY as follows:

 FY (i, j) = c(i, j)F (i, j) If i ∈ Y and j ∈ Y FY (i, j) = F (i, j) otherwise
where we only assume that c(i, j) = c(j, i) ≥ 0. And we add the normalization to obtain a transition rate matrix. Then FY is also in S(α).

Proof: we develop αFY for an arbitrary state i.

• If i is not in Y then FY (i, j) = F (i, j). Therefore component i of αFY is zero.
• If i is in Y , we decompose the summation:

X j αjFY (j, i) = X j∈Y j =i αjFY (j, i) + αiFY (i, i) + X j ∈Y αjFY (j, i).
Due to the normalization, we have:

FY (i, i) = - X j∈Y j =i FY (i, j) - X j ∈Y FY (i, j).
Remember that i is in Y . Then if j ∈ Y FY (i, j) = c(i, j)F (i, j). Otherwise FY (i, j) = F (i, j). After substitution we get:

X j αjFY (j, i) = X j∈Y j =i (αjF (j, i)c(j, i) -αiF (i, j)c(i, j)) + X j ∈Y (αjF (j, i) -αiF (i, j)) .
The last term is zero due to property 7. And we assume that c(i, j) = c(j, i). Therefore we can factorize c(i, j):

X j αjFY (j, i) = X j∈Y j =i c(i, j) (αjF (j, i) -αiF (i, j)) .
As i and j are members of Y , all the terms in the summation are 0. Therefore component i of αFY is 0.

Thus we can use several functions in the SAN instead of only one but they must satisfy the constraints of property 9. This is detailed in the next Corollary 3. If the SAN is built with the assumptions of theorem 4 but it uses several functions. If these functions verify one of the following two assumptions 1. the functions carried by automaton l do not use state of automaton l as an argument 2. if the former assumption is not true for a function f l carried by automaton l used for the transition from i to j in automaton l, then the function must also be used from the transition from j to i and we must have:

f l ( k + (l, i)) = f l ( k + (l, j)) (i.e
. the function has the same value for the transition from i to j and the transition from j to i).

then the SAN has product form.

Note that we can combine theorem 2 and 4 and corollary 3 to obtain more general assumptions on SAN with product form.

Boucherie's second theorem is a typical result one can obtain when one combine theorem 2 and 4. The key idea behind the second theorem in [START_REF] Boucherie | A characterization of independence for competing markov chains with applications to stochastic petri nets[END_REF] is to assume group balance for the chain. Then the competition over a resource only takes place in some groups and is again associated to blocking of the transitions in this group when the resource is already owned. For the sake of readability we do not develop this theorem here and just give an example.

Consider the Petri net depicted in Fig. 6. This is an example of the second Boucherie's theorem. Note that this is not a model of a real problem but the result of Robertazzi's method to transform an arbitrary Petri net into a product form one.

The Markov chain associated to this Petri net is in fact depicted in Fig. 2, the SAN model is also given at the beginning of this paper and the proof of product form is already stated. Single Queues in a random environment have been considered for a long time. One typically study the influence of a stochastic process (usually denoted as a phase) on the evolution of a queue or a set of queues. Following Neuts's [START_REF] Neuts | Matrix Geometric Solutions in Stochastic Models, an Algorithmic Approach[END_REF] most of the results are based on the matrix geometric approach.

Only few results have been presented on open networks of n queues modulated by a phase. As the state space is usually infinite in several dimension it is not possible to apply the matrix geometric approach. In [START_REF] Zhu | Markovian queueing networks in a random environment[END_REF] Zhu had studied the steady state distribution of a modulated Markovian open network of infinite queues. He proved a sufficient condition to have a product form steady-state distribution. The steady-state distribution of the number of customers in a queue is geometrically distributed with ratio ρi,j for queue i when the phase is in state j. The proof is based on the reversed process of the network of queues. The necessary condition is simple: the ratio ρi,j must be constant when the phase changes. Remember that the ratios of the geometric in an open queueing network are given by the flow equations.

In [START_REF] Michel | G-réseaux dans un environnement aléatoire[END_REF], Verchère generalized Zhu's result as follows: he considered a multidimensional continuous-time Markov chains: the phase to model the environment and the description of the networks of queues. The transition rates of the network of queues may depend of the state of the phase but the transition rates of the phase do not change when the state of the network evolves. The chain modeling the phases is irreducible and finite. Therefore it has a steady-state distribution. Verchère first proved a general theorem on this model and he also derived corollaries when the network of queues is a G-network with positive and negative customers (see the seminal papers on positive and negative customers by Gelenbe [START_REF] Gelenbe | Product form queueing networks with negative and positive customers[END_REF]). Unlike Zhu's method, the proof in [START_REF] Michel | G-réseaux dans un environnement aléatoire[END_REF] is not based on reversibility.

Property 10 (Verchère's Theorem). Fix the chain of the phase to an arbitrary state (say i). Let M (i) be the transition rate matrix for this state of the phase. It is not necessary for M (i) to be irreducible. Consider the left eigenvector problem with eigenvalue 1: π i M (i) = 0, if π i does not change (up to a normalization) when the phase changes (i.e. π i = π for all phase i), the steady-state distribution of the whole system has product form Cπ N α where C is a normalizing constant and α is the steady-state distribution of the chain modelling the phase.

Our approach clearly generalizes Verchère's result. Indeed a SAN with functions and without synchronization may represent very easily a set of queues modulated by a phase. But the SAN is even more general because we allow that the transition rates of the phase to be dependent of the state of the queues. We do not require any constraint on the functions. They may use any states of any automata to change the rate of any transition. Thus we have a much more general assumption on the model and we still have the same product-form result.

CONCLUDING REMARKS

We have presented a sufficient condition for a SAN without synchronization to have product form steady-state solution. This simple algebraic result generalizes many papers already published on set of queues or set of Markov chains in interaction. It remains to adapt this theory to known results on set of synchronized chains or networks of queues or general SAN. The Domino synchronization [START_REF] Fourneau | Domino synchronization: product form solution for stochastic automata networks[END_REF] have shown that we still may have product form for a complex synchronized set of automata. We also think that our approach can generalize the building blocks theory developed by Robertazzi [START_REF] Thomas | Computer Networks and Systems: queueing networks and performance evaluation[END_REF] through an algebraic interpretation of product form based on local balance.

Figure 1 :

 1 Figure 1: A SAN with functions f 0 and f 1 and constant rates l0 and l1.

Figure 2 :

 2 Figure 2: The Markov chain of the SAN. The kernel of M 0 (resp. M 1) contains all the vectors multiple of (m1 + m2, m) (resp. (m1, m b)).

Figure 3 :

 3 Figure 3: An irreducible Markov chain associated to a SAN whose matrices are reducible

Figure 4 :

 4 Figure 4: A more complex SAN with product form.

Figure 5 :

 5 Figure 5: Two Markov chains in competition

Figure 6 :

 6 Figure 6: Example from Boucherie

ACKNOWLEDGEMENTS

This work is partially supported a cooperation grant CNRS-NSF and by French ANR project (ANR-05-BLAN-009-0, Simulation and Stochastic Monotonicity).