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 forCSP if these criteria are adopted. We also show that under these criteria, none of the commonly used notions of fairness are fully aceptable for a model with an n-way synchronization mechanism. The notion of fairness most often mentioned for Ada is shown to be fully acceptable. For a model with nonblockingsend operations, some variants of common fairness definitions are appraised, and two are shown to satisfy the suggested criteria.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
[ABC] Apt KR, Bougé L, Clermont P (1987/88) Two normal form theorems for CSP programs. Inf Proc Lett 26: 165–171
[AFK] Apt KR, Francez N, Katz S (1987) Appraising fairness in languages for distributed programming. Proc of 14th ACM-POPL Symp, Munich, West Germany (January 1987)
[AO] Apt KR, Olderog ER (1983) Proof rules and transformations dealing with fairness. Sci Comp Prog 3:65–100
[AF] Attie P, Francez N (1988) Fairness and hyperfairness in multiparty interactions. MCC-STP Tech Rep (July 1987)
[BK-S 1] Back RJ, Kurki-Suonio K (1983) Decentralization of process nets with centralized control. Proc of 2nd ACM-PODC Symp, Montreal (August 1983)
[BK-S 2] Back RJ, Kurki-Suonio K (1985) Serializability in distributed systems with handshaking. CMU Tech Rep, pp 85–109
[BF] Bougé L, Francez N (1988) A compositional approach to superimposition. Proc of 15th ACM-POPL Symp. San Diego, California (January 1988)
[D] Dijkstra EW (1975) Guarded commands, nondeterminacy and formal derivation of programs. Commun ACM 18:453–467
[DM] Degano P, Montanari U (1988) Concurrent histories, a basis for observing distributed systems (to appear in J Comp Syst Sci)
[Fo] Forman I (1986) On the design of large distributed systems. Proc of Int Conf on Comp Lang, Miami Beach, Florida (October 1986)
[Fr] Francez N (1986) Fairness. In: Gries D (ed) Texts and monographs in computer science series. Springer, New York
[FdR] Francez N, de Roever WP (1980) Fairness in communicating processes (unpublished memo) Computer Science Department, Utrecht University (July 1980)
[FK] Francez N, Katz S (1988) Fairness and the axioms of control predicates. To appear in Int J Parallel Programming
[GdR] Gerth RT, de Roever WP (1984) A proof system for concurrent Ada programs. Science of Computer Programming, vol 4, no 2, pp 159–204
[GFK 1] Grumberg O, Francez N, Katz S (1986) A complete rule for equifair termination. J Comp Syst Sci 33:313–332
[GFK 2] Grumberg O, Francez N, Katz S (1984) Fair termination of communicating processes. Proc of 3rd ACM-PODC Symp, Vancouver (August 1984)
[GFMdR] Grumberg O, Francez N, Makowsky J, de Roever WP (1985) A proof rule for fair termination of guarded commands. Inf Control 66:83–102
[H] Hoare CAR (1978) Communicating sequential processes Commun ACM 21:666–677
[HLP] Hennessey W, Wei-Li, Plotkin GD (1983) Semantics for Ada tasks. In: Björner D (ed) Proceedings of TC.2 Working Conference on the Formal Description of Programming Concepts, Garmisch Partenkirchen. North Holland
[K] Katz S (1987) A superimposition control construct for distributed systems. MCC-STP Tech Rep STP-268-87
[KP] Katz S, Peled D (1987) Interleaving set temporal logic. Proc of 6th ACM-PODC Symp, Vancouver, Canada (August 1987)
[KdR] Kuiper R, de Roever WP (1983) Fairness assumptions for CSP in a temporal logic framework. In: Björner D (ed) Proceedings of TC.2 Working Conference on the Formal Description of Programming Concepts, Garmisch Partenkirchen, North Holland
[L 1] Lamport L (1978) Time, clocks, and the ordering of events. Commun ACM 21: 558–566
[L 2] Lamport L (1983) What good is temporal logic? Proc of 9th IFIP Cong, Paris, France (September 1983)
[LPS] Lehmann D, Pnueli A, Stavi J (1981) Impartiality, justice, and fairness: the ethics of concurrent termination. In: Kariv O, Even S (eds)] Proc of 8th ICALP, Acco, Israel (July 1981) LNCS 115. Springer Berlin Heidelberg New York, pp 264–277
[OA] Olderog ER, Apt KR. (1988) Fairness in parallel programs, the transformational approach (to appear in ACM Toplas)
[OL] Owicki SS, Lamport L (1982) Proving liveness properties of concurrent programs. ACM Trans Prog Lang Syst 4(3):455–495
[P] Plotkin GD (1983) An operational semantics for CSP. In: Björner D (ed) Proceedings of TC.2 Working Conference on the Formal Description of Programming Concepts, Garmisch Partenkirchen. North Holland
[PdR] Pnueli A, de Roever WP (1982) Rendezvous with Ada: a proof-theoretic view. Proceedings of the AdaTec Conference, Crystal City
[R] Reisig W (1984) Partial order semantics versus interleaving semantics and its impact on fairness. Proc 11th ICALP, Antwerp, 1984
[RS] Reif J, Spirakis P (1983) Probabilistic bidding gives optimal distributed resource allocation. Aiken Computation Lab Tech Rep, Harvard University (July 1983)
Author information
Authors and Affiliations
Additional information
Krzysztof R. Apt was born in 1949 in Poland. Received his Ph.D. in 1974 from Polish Academy of Sciences in Warsaw in mathematical logic. From 1974 until 1981 worked at various scientific institutions in the Netherlands and from 1981 until 1987 at C.N.R.S. in Paris, France. Spent 1985 as a visiting scientist at IBM Research Centre in Yorktown Heights, U.S.A. Currently holding an Endowed Professorship at the Department of Computer Sciences at the University of Texas at Austin; also a senior research scientist at the Centre for Mathematics and Computer Science in Amsterdam, the Netherlands. His research interests include program correctness and semantics, methodology of distributed computing, use of logic as a programming language and non-standard forms of reasoning. He has served on editorial boards of a number of journals and program committees of numerous conferences in computer science. Lectured in a dozen countries on four continents. Also, he has run two marathons and crossed Sumatra on a bicycle.
Shmuel Katz received his B.A. in Mathematics and English Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rehovot, Israel. From 1976 to 1981 he was a researcher at the IBM Israel Scientific Center. Presently, he is a Senior Lecturer in the Computer Science Department at the Technion in Haifa, Israel. In 1977–78, he visited for a year at the University of California, Berkeley, and in 1984–85 was at the University of Texas at Austin. He has also been a consultant for the MCC Software Technology Program. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structures, and programming languages.
Nissim Francez received his B.A. in Mathematics and Philosophy from the Hebrew University in Jerusalem, and his M.Sc. and Ph.D. in computer science (1976) from the Weizmann Institute of Science, Rehovot, Israel. In 1976–77 he spent a postdoctoral year at Queen's university, Belfast, where he was introduced by C.A.R. Hoare to CSP. In 1977–78 he was an assistant professor at USC, Los Angeles. From 1978 he is with the Computer Science Department at the Technion. In 1982–83 he was on a sabbatical leave at IBM T.J. Watson Research Center. He has been a consultant for MCC's software technology program, working on multiparty activities in distributed systems. He had summer appointments in Harvard University, IBM T.J. Watson Research Center, Utrecht University, CWI (Amsterdam) and at MCC. He also served in several program committees. His research interests include program verification and the semantics of programming languages, mainly for concurrent and distributed programming. Is also interested in logic programming and recursive query evaluation and in compiler constration. He is the author of the first book onFairness. Unfortunately, he is incapable of Marathon running...
Rights and permissions
About this article
Cite this article
Apt, K.R., Francez, N. & Katz, S. Appraising fairness in languages for distributed programming. Distrib Comput 2, 226–241 (1988). https://doi.org/10.1007/BF01872848
Issue Date:
DOI: https://doi.org/10.1007/BF01872848