HOME

TheInfoList



OR:

In
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a
product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...
of the metric across the different components. Using
capital Pi notation Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additio ...
a product-form solution has algebraic form :\text(x_1,x_2,x_3,\ldots,x_n) = B \prod_^n \text(x_i) where ''B'' is some constant. Solutions of this form are of interest as they are computationally inexpensive to evaluate for large values of ''n''. Such solutions in queueing networks are important for finding performance metrics in models of multiprogrammed and time-shared computer systems.


Equilibrium distributions

The first product-form solutions were found for equilibrium distributions of Markov chains. Trivially, models composed of two or more
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independ ...
sub-components exhibit a product-form solution by the definition of independence. Initially the term was used in queueing networks where the sub-components would be individual queues. For example, Jackson's theorem gives the joint equilibrium distribution of an open queueing network as the product of the equilibrium distributions of the individual queues. After numerous extensions, chiefly the BCMP network it was thought
local balance In probability theory, a balance equation is an equation that describes the probability flux associated with a Markov chain in and out of states or set of states. Global balance The global balance equations (also known as full balance equations) ...
was a requirement for a product-form solution. Gelenbe's
G-network In queueing theory, a discipline within the mathematical theory of probability, a G-network (generalized queueing network, often called a Gelenbe network) is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing syst ...
model was the first to show that this is not the case. Motivated by the need to model biological neurons which have a point-process like spiking behaviour, he introduced the precursor of G-Networks, calling it the random neural network. By introducing "negative customers" which can destroy or eliminate other customers, he generalised the family of product form networks. Then this was further extended in several steps, first by Gelenbe's "triggers" which are customers which have the power of moving other customers from some queue to another. Another new form of customer that also led to product form was Gelenbe's "batch removal". This was further extended by Erol Gelenbe and Jean-Michel Fourneau with customer types called "resets" which can model the repair of failures: when a queue hits the empty state, representing (for instance) a failure, the queue length can jump back or be "reset" to its steady-state distribution by an arriving reset customer, representing a repair. All these previous types of customers in G-Networks can exist in the same network, including with multiple classes, and they all together still result in the product form solution, taking us far beyond the reversible networks that had been considered before. Product-form solutions are sometimes described as "stations are independent in equilibrium". Product form solutions also exist in networks of bulk queues. J.M. Harrison and R.J. Williams note that "virtually all of the models that have been successfully analyzed in classical queueing network theory are models having a so-called product-form stationary distribution" More recently, product-form solutions have been published for Markov process algebras (e.g. RCAT in
PEPA Performance Evaluation Process Algebra (PEPA) is a stochastic process algebra designed for modelling computer and communication systems introduced by Jane Hillston in the 1990s. The language extends classical process algebras such as Robin Milne ...
) and stochastic
petri nets A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that ...
. Martin Feinberg's deficiency zero theorem gives a sufficient condition for chemical reaction networks to exhibit a product-form stationary distribution. The work by Gelenbe also shows that product form G-Networks can be used to model spiking random neural networks, and furthermore that such networks can be used to approximate bounded and continuous real-valued functions.


Sojourn time distributions

The term ''product form'' has also been used to refer to the sojourn time distribution in a cyclic queueing system, where the time spent by jobs at ''M'' nodes is given as the product of time spent at each node. In 1957 Reich showed the result for two M/M/1 queues in tandem, later extending this to ''n'' M/M/1 queues in tandem and it has been shown to apply to overtake–free paths in
Jackson network In queueing theory, a discipline within the mathematical theory of probability, a Jackson network (sometimes Jacksonian network) is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has ...
s. Walrand and Varaiya suggest that non-overtaking (where customers cannot overtake other customers by taking a different route through the network) may be a necessary condition for the result to hold. Mitrani offers exact solutions to some simple networks with overtaking, showing that none of these exhibit product-form sojourn time distributions. For closed networks, Chow showed a result to hold for two service nodes, which was later generalised to a cycle of queues and to overtake–free paths in Gordon–Newell networks.


Extensions

* Approximate product-form solutions are computed assuming independent marginal distributions, which can give a good approximation to the stationary distribution under some conditions. * Semi-product-form solutions are solutions where a distribution can be written as a product where terms have a limited functional dependency on the global state space, which can be approximated. * Quasi-product-form solutions are either **solutions which are not the product of marginal densities, but the marginal densities describe the distribution in a product-type manner or ** approximate form for transient probability distributions which allows transient moments to be approximated.


References

{{Queueing theory Queueing theory