For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Introduction of Economic-Oriented Fairness to Process Algebras
Shigetomo KIMURA Yoshihiko EBIHARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/11/25
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)>>
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.