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 how the distribution of traces affects the performance of systems.

Methodology: The research employs the use of generating series and rational representations to study the asymptotics of the number of traces of a given height or length. The average parallelism is considered for various probability distributions on traces, with a particular focus on the uniform distribution over words of the same length and height.

Results: The study provides finite representations for the generating series, enabling precise information on the asymptotics of the number of traces. It is shown that there exist algebraic numbers λM and γM such that the average parallelism approaches these values as the length or height of the traces increases.

Implications: The results of this study have significant implications for the performance evaluation of concurrent systems. By understanding the average parallelism in trace monoids, researchers can gain insights into the behavior of systems and develop more efficient algorithms for performance analysis. Moreover, the techniques used in this study can be applied to other areas of mathematics and computer science, such as combinatorics and formal language theory.

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