Computation of the normalising constant for product-form models of distributed systems with synchronisation

Performance evaluation of large distributed systems plays a pivotal role in the design of Internet of Things (IoT) applications, or Big Data analysis, where high scalability and low response times are required. However, this performance assessment requires models, methodologies and tools tailored for this type of systems. Product-form queueing networks have been widely adopted for the analysis of sequential computations thanks to the availability of efficient algorithms for the computation of the average performance indices. However, this formalism has strong limitations since it does not allow one to model fork-join constructs or batches of jobs. Product-form stochastic Petri nets partially overcome these limitations but, on the other hand, general algorithms for the computation of the expected performance indices are not known or require strong assumptions on the model structure. In this paper, we define a new algorithm for the analysis of product-form stochastic Petri nets which works under much less restrictive assumptions than those previously proposed. The idea is that, in many cases, the entire state space of the model can be stored in memory thanks to multi-valued decision diagrams and the computation of the net's performance indices can take advantage of the tree structure that characterises this representation. Finally, we present a case study and several examples that will be used to study the performance of the algorithm for realistic scenarios