Fairness and hyperfairness in multi-party interactions | Distributed Computing Skip to main content
Springer Nature Link
Log in

Fairness and hyperfairness in multi-party interactions

  • Published:
Distributed Computing Aims and scope Submit manuscript

Summary

In this paper, a new fairness notion is proposed for languages withmulti-party interactions as the sole interprocess synchronization and communication primitive. The main advantage of this fairness notion is the elimination of starvation occurring solely due to race conditions (i.e., ordering of independent actions). Also, this is the first fairness notion for such languages which is fully adequate with respect to the criteria presented in [2]. The paper defines the notion, proves its properties, and presents examples of its usefulness.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Apt KR, Bouge L, Clermont P: Two normal form theorems for CSP programs IPL 26:165–171 (1987)

    Google Scholar 

  2. Apt KR, Francez N, Katz S: Appraising fairness in distributed languages Distrib Comput 2:226–241 (1988). Also: Proc 14th ACM-POPL Symp, Munich, Germany, January 1987

    Google Scholar 

  3. Apt KR, Olderog ER: Proof rules and transformations dealing with fairness Sci Comput Program 3:65–100 (1983)

    Google Scholar 

  4. Bagrodia R: A distributed algorithm to implement N-party rendezvous Tech Rep Department of Computer Science, University of Texas at Austin, June 1987

  5. Back RJR, Kurki-Suonio R: Decentralization of process nets with centralized control Distrib Comput 3:73–87 (1989) Also: Proc 2nd ACM-PODC, Montreal, Canada, August 1983

    Google Scholar 

  6. Back RJR, Kurki-Suonio R: Cooperation in distributed systems using symmetric multiprocess handshaking Tech Rep A34, Abo Akademi 1984

  7. Back RJR, Kurki-Suonio R: Serializability in distributed systems with handshaking Tech Rep 85-109, CMU, 1985

  8. Back RJR, Kurki-Suonio R: Distributed cooperation with action systems. ACM Trans Program Lang Syst 10(4) 513–554 (1988)

    Google Scholar 

  9. Charlesworth A: The multiway rendezvous ACM Trans Program Lang Syst 9(2):350–366 (1987)

    Google Scholar 

  10. Chandy KM, Misra J: Synchronizing asynchronous processes —the committee-coordination problem Tech Rep Department of Computer Science, University of Texas at Austin, 1987

  11. Chandy KM, Misra J: Parallel program design: a foundation Chap 14, Addison Wesley 1988

  12. Dijkstra, EW: A discipline of programming Prentice-Hall 1976

  13. Deleted

  14. Francez N, Hailpern BT, Taubenfeld G: SCRIPT—a communication abstraction mechanism and its verification Sci Comput Program 6(1):35–88 (1986)

    Google Scholar 

  15. Forman, I.R.: On the design of large distributed systems Tech Rep STP-098-86 (Rev 1.0), MCC, Austin, Texas January 1987. A preliminary version presented at the First International Conference on Computer Languages, Miami, Florida, October 1986

    Google Scholar 

  16. Francez N: Fairness Springer, Berlin Heidelberg New York 1986

    Google Scholar 

  17. Francez N: Cooperating proofs for distributed programs with multi-party interactions IPL 32(5):235–242 (1989)

    Google Scholar 

  18. Grumberg O, Francez N, Katz S: Fair termination of communicating processes 3rd ACM-PODC Conference, Vancouver, BC, Canada, August 1984

  19. Hoare CAR: Communicating sequential processes Commun ACM 21(8):666–678 (1978)

    Google Scholar 

  20. Hoare CAR: Communicating Sequential Processes Prentice-Hall 1985

  21. Kuiper R, de Roever WP: Fairness assumptions for CSP in a temporal logic framework In: Biorner D (ed) Proc Tech Rep 2 Working Conference on Formal Description of Programming Concepts, Garmisch Partenkirchen North Holland 1983

  22. Olderog ER, Apt KR: Transformations realizing fairness assumptions for parallel programs ACM Trans Programm Lang Syst 10(3):420–455 (1988)

    Google Scholar 

  23. Plotkin GD: An operational semantics for CSP In: Biorner D (ed) Tech Rep 2 Working Conference on Formal Description of Programming Concepts, Garmisch Partenkirchen, North Holland 1983

  24. Pnueli A: Lect Notes of CS395T, Specification and verification of reactive systems University of Texas at Austin 1986

  25. Ramesh S, Mehndiratta H: A methodology for developing distributed programs IEEE Trans Software Eng SE-13(8):967–976 (1987)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Sciences, The University of Texas at Austin, USA

    Paul C. Attie

  2. Microelectronics and Computer Technology Corporation, Austin, Texas, USA

    Paul C. Attie & Nissim Francez

  3. Computer Science Department, Technion, Haifa, Israel

    Nissim Francez & Orna Grumberg

Authors
  1. Paul C. Attie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nissim Francez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Orna Grumberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Orna Grumberg received her B.Sc. degree, M.Sc. and Ph.D. in the Computer Science Department at the Technion—Israel Institute of Technology. Since 1984 she is a faculty member in the Computer Science Department at the Technion. Her research interests include verification of distributed systems, computer-aided verification, model checking, temporal logics and automata.

Paul Attie received a B.A. degree in engineering science from the University of Oxford, and an M.Sc. degree in computer science from the University of London. Since 1986, Paul has been with the Microelectronics and Computer Technology Corporation, where he is currently a member of technical staff. He is also a candidate for the Ph.D. in computer science degree at the University of Texas at Austin. His research interests include temporal logic, fairness, algebraic process theory, formal semantics, and concurrent program verification.

The photograph and autobiography of Dr. Nissim Francez were published in Volume 2, Issue No. 4, 1988 on page 226

Rights and permissions

Reprints and permissions

About this article

Cite this article

Attie, P.C., Francez, N. & Grumberg, O. Fairness and hyperfairness in multi-party interactions. Distrib Comput 6, 245–254 (1993). https://doi.org/10.1007/BF02242712

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02242712

Key words

Search

Navigation