Introduction of Economic-Oriented Fairness to Process Algebras

Shigetomo KIMURA  Yoshihiko EBIHARA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.11   pp.1768-1773
Publication Date: 1996/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)
fairness,  economic-oriented fairness,  process algebra,  CCS,  

Full Text: PDF(553.1KB)>>
Buy this Article

Fairness is one of the important notion for programming language, such as process algebras like CCS, that includes concurrency (or parallelism) and nondeterminism. This ensures that while repeatedly choosing among a set of alternatives, no alternative will be postponed forever. However, the fairness does not mention at what frequency these alternatives are selected. In this paper, we propose a quantitative fairness, which is called economic-oriented fairness, to each alternatives. This fairness ensures that the expected number of selection for each alternatives are same. We give a condition for probability assignment of selection of each alternative to be satisfied for economic-oriented fairness. First we show a simple probability assignment rule. In this assignment, between any two alternatives, if an alternative is selected n times and the other m times then the probability to select the former alternative is (m + 1)/(n + 1) times the probability for the latter. We prove that this assignment satisfies the condition of economic-oriented fairness. For a model of the economic-oriented fairness, we adopt a probabilistic process algebra. Finally, we elaborate with two process models of the economic-oriented fairness. The first one is a server and client model, where each client communicates only with the server, but not among them. In this model, the expected number of communication by each client are equal. The second model considers communication between two processes. In practice, a process has several subprocesses. Each subprocess communicates via a communication port, In the second model, there is economic-oriented fairness where the expected number of communications via each communication port are equal.