Discrete State-Space Stochastic Networks with Product Form -- Discovery or Invention?
Probability models have long been used in computer science and engineering to study the performance of systems, software, networks and algorithms, and to analyse theirreliability. Their closed form analytical solutions are used in industry to compute performance metrics such as response times, throughput and resource bottlenecks.However, the search for mathematical solutions of significant classes of models, such as queuing networks that are the key mathematical models for Internet nodes and traffic, is an active but difficult area of research. This talk will focus on some intriguing probability models called “G-networks” that have analytical or quasi-analytical solutions in "product form" – i.e., that are provably "separable" in steady-state, despite the fact that the models are tightly coupled, leading to computational algorithms which are polynomial in the number of state variables, whereas purely numerical solutions would have to enumerate all possible combinations of states. Examples will also be given from systems of interacting resources, as well as web auctions. Links to neural networks, theoretical chemistry and gene regulatory networks will also be outlined.