K. R. Apt
ABSTRACT
The relations among various languages and models for distributed computation and various possible definitions of fairness are considered. Natural semantic criteria are presented which an acceptable notion of fairness should satisfy. These are then used to demonstrate differences among the basic models, the added power of the fairness notion, and the sensitivity of the fairness notion to irrelevant semantic interleavings of independent operations. These results are used to show that from the considerable variety of commonly used possibilities, only strong process fairness is appropriate for CSP if these criteria are adopted. We also show that under these criteria, none of the commonly used notions of fairness are fully acceptable for a model with an n-way synchronization mechanism. Finally, the notion of fairness most often mentioned for Ada is shown to be fully acceptable.
- 1.{AO} K.R. Apt, E.-R. Olderog, Proof rules and transformations dealing with fairness, SCP 3, pp. 65- i00, 1983.Google Scholar
- 2.{AC} K.R. Apt, Ph. Clermont, Two normal form theorems for CSP programs. IBM T.J Watson research Center RC I0975, July 1985Google Scholar
- 3.{BK-S1} R.J. Back and K. Kuski-Suonio, Decentralization of process nets with centralized control, Proceedings of 2nd ACM PODC, Montreal, August 1983. Google ScholarDigital Library
- 4.{BK-S2} RJ. Back and K. Kurki-Suonio, $cdalizability in distributed systems with handshaking, CMU TR 85-109, 1985.Google Scholar
- 5.{DM} P. Dcgano and U. Montanari, Concurrent histories, a basis for observing distributed systems, to appear in JCSS. Google ScholarDigital Library
- 6.{Fo} I. Forman, On the design of large distributed systems, ~oceedings of International Conference on Computer Languages, Miami Beach, Florida, October, 1986.Google Scholar
- 7.{Fr} N. Frmlcez, Fairness, Texts and monographs in computer science series (D. Gales, ed.), Springer-Verlag, New York, 1986.Google Scholar
- 8.{FdR} N. Francez and W. P. de Roever, Fairness in communicating processes, unpublished memo, Computer Science Dept., Utrecht University, July 1980.Google Scholar
- 9.{GFK1} O. Grumberg, N. Francez, and S. Katz, A complete proof rule for strong equifairness, in Proceedings of 2nd Workshop on Logics of Programs, CMU, in LNCS 164 (E. Clarke and D. Kozen, eds.), 1983; also to appear in JCSS, 1986. Google ScholarDigital Library
- 10.{GFK2} O. Grumberg, N. Francez, and S. Katz, Fair termination of communicating processes, Proceedings of 3rd ACM PODC, Vancouver, August 1984. Google ScholarDigital Library
- 11.{GFMdR} O. Grumberg, N. Francez, J. Makowsky, and W.P. de Roever, A proof rule for fair termination of guarded commands, Information and Control 66, 1/2: 83-102, July/August, 1985. Google ScholarDigital Library
- 12.{H} C.A.R. Home, Communicating sequential processes, CACM 21, 8, August 1978.Google Scholar
- 13.{HLP} W. Hennessey, Wei-Li, G. Plotldn, Semantics for Ada tasks, proceedings of TC.2 Working conference on the formal description of programming concepts, Garmisch Partenkirchen (D. Biomer, ed.), North Holland, 1983.Google Scholar
- 14.{KdR} R. Kuiper and W.P. de Roever, Fairness assumptions for CSP in a temporal logic framework, proceedings of TC.2 Working conference on the formal description of programming concepts, Garmisch Partenkirchen OD. Biomer, ed.), North Holland, 1983.Google Scholar
- 15.{L1} L. Lamport, Time, clocks, and the ordering of events, CACM 21, 1978, pp. 558-566. Google ScholarDigital Library
- 16.{L2} L. Lamport, What good is temporal logic?, proceedings of IPIP 9th world congress, Paris, France, September 1983.Google Scholar
- 17.{LPS} D. Lehmann, A. Pnueli, and J. Stavi, impartiality, justice, and fairness" the ethics of concurrent termination, Proceedings of 8th ICALP, Aeeo, Israel, July 1981, in LNCS 115 (O. Kariv and S. Even, eds.), Springer-Verlag, 1981. Google ScholarDigital Library
- 18.{OA} E.-R. Olderog, K.R. Apt, Fairness in parallel programs, the transformational approach, TR 86-I 1, Univ. of Kiel, 1986 (submitted for publication).Google Scholar
- 19.{OL} S.S. Owicki, L. Lamport, Proving liveness properties of concurrent programs, ACM-TOPLAS 4, 3, July I982: 455-495. Google ScholarDigital Library
- 20.{P} G.D. Plotlfin, An operational semantics for CSP, proceedings of TC.2 Working conference on the formal description of programming concepts, Garmisch Partenkirchen (D. Biorner, ed.), North Holland, 1983.Google Scholar
- 21.{PdR} A. Pnueli and W,P. de Rocver, Rendezvous with Ads: a proof-theoretic view, RUU-CS-82-12, University of Utrecht, July 1982. Also in: proceedings of the AdaTec conference, Crystal City, 1982.Google Scholar
- 22.{R} W. Reisig, Partial order semantics versus interleaving semantics and its impact on fairness, Proceedings of 1 lth ICALP, Antwerp, 1984. Google ScholarDigital Library
- 23.{RS} J. Reif, P. Spirakis, Probabilistic bidding gives optimal distributed resource allocation, TR, Aiken Computation Lab, July 1983.Google Scholar
Index Terms
- Appraising fairness in distributed languages
Recommendations
Appraising fairness in languages for distributed programming
The relations among various languages and models for distributed computation and various possible definitions of fairness are considered. Natural semantic criteria are presented which an acceptable notion of fairness should satisfy. These are then used ...
Airtime Fairness for IEEE 802.11 Multirate Networks
Under a multi rate network scenario, the IEEE 802.11 DCF MAC fails to provide air-time fairness for all competing stations since the protocol is designed for ensuring max-min throughput fairness and the maximum achievable throughput by any station gets ...
Comments