Trace Monoids: A Study in Parallelism and Performance Evaluation

Title: Trace Monoids: A Study in Parallelism and Performance Evaluation

Abstract: Trace monoids are a mathematical model used to represent the occurrence of events in concurrent systems. They are particularly useful in studying the performance of such systems, specifically focusing on the concepts of parallelism and execution time. This study aims to investigate the average parallelism in trace monoids, providing insights into the asymptotic behavior of the number of traces of a given height or length.

Main Research Question: How can we measure and understand the average parallelism in trace monoids?

Methodology: The study uses the concept of generating series, which are used to represent the sum of the terms of an infinite geometric series. The authors focus on three specific series: F (height function), L (length function), and H (height function series). They exploit the symmetries of the trace monoid to obtain representations of reduced dimensions and study the asymptotics of the number of traces of a given height or length.

Results: The authors prove that the series F, L, and H are all rational, meaning they can be represented as a quotient of two polynomials with rational coefficients. They provide finite representations for these series and use them to obtain precise information on the asymptotics of the number of traces. They also study the average parallelism in trace monoids, considering three different notions: uniform distribution over traces of the same length, uniform distribution over traces of the same height, and uniform distribution over Cartier-Foata normal forms. They prove that there exist algebraic numbers λM and γM such that the average parallelism approaches these values as the length or height of the traces goes to infinity.

Implications: This study provides a deeper understanding of the average parallelism in trace monoids, which has practical implications for the performance evaluation of concurrent systems. The results can help in predicting the behavior of such systems and in optimizing their performance. The techniques used in the study can also be applied to other areas of mathematics and computer science.

Link to Article: https://arxiv.org/abs/0112012v2 Authors: arXiv ID: 0112012v2