Towards Automatic Measurement Of Probabilistic Processes

With the rapid development of computer technology and network communication, concurrent and distributed systems that feature concurrency, distribution, real time, heterogeneity and interoperablity have become a major direction. The phenomenon of concurrency challenges computer scientists by its intrinsic complexity. Different from that of sequential-ity, its study is just beginning.Process algebra is a math framework mainly used to proscribe concurrent systems, it studies the phenomenon of concurrency, i.e., multiagent work together to achieve a certain computing phenomenon through exchanging information. As for the study of concurrent computing model, the focus is the equivalence relationship between processes. We can use equivalence relationship to show the approximated actions of two processes.In recent times, randomization has proved to be a very useful tool in the construction of certain algorithms for concurrent systems. Traditionally, the modeling of concurrent systems has abstracted away from quantitative aspects. As a result, there is no information about how frequently or with what chance certain behavior of a system will occur, whereas, at a practical level, there need to be distinctions relating to this, since many aspects of concurrent systems are probabilistic in nature, or at last can be modeled adequately by assuming random behavior.This paper focuses on the probabilistic information of process algebra. The standard notion of trace equivalence can be adapted to probabilistic process algebra by treating the quantities as labels, but this does not provide a robust relation, since quantities are matched only when they are identical.Therefore, the notion of standard trace equivalence has many drawbacks for the reason that it pays more attention to the probabilistic information. The probability occurred in the process should not be considered as labels but the possibility of random event. Then, we propose a notion of approximation between probabilistic process expressions, named metric, to take the place of trace equivalence.The main contributions include the following:1. We define a metric for pCS P processes, and we relate it to trace equivalence such that two processes have distance zero under the metric if and only if they are trace equivalent. Finally, we show that most of construction operators of pCS P are non-expansive.2. In this section, we show that the metric between trace distributions can be reduced to a transshipment problem. Based on it, we present an algorithm to calculate the distance of two pCS P processes and implement this algorithm.3. We give the definition of degree of anonymity for security protocols based on metric. We illustrate our method by using the Dining Cryptographers Problem(DCP). We consider both the cases of nondeterministic and probabilistic users.