Probabilistic Asynchronous π-Calculus: A Model for Distributed Computing

Title: Probabilistic Asynchronous π-Calculus: A Model for Distributed Computing

Abstract: The π-calculus is a powerful model for concurrent programming, but it has challenges in its distributed implementation. The asynchronous π-calculus is more suitable for distribution, but it is weak for solving distributed problems. To increase the expressive power of the asynchronous π-calculus, we propose a probabilistic extension, πpa, based on the probabilistic automata of Segala and Lynch. This model distinguishes between probabilistic and nondeterministic behavior, allowing us to reason about adverse conditions. We show an example of a distributed problem solved with πpa, and we prove that the solution is correct under every possible scheduler. Our algorithm is reminiscent of the algorithm used for the dining philosophers problem, but without the fairness assumption. Finally, we implement πpa in a Java-like language, proving that it is a reasonable paradigm for distributed algorithm specification. The novelty of our proposal is the definition of the parallel operator in a CCS style, allowing natural parallel processing.

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