Skip to main content
SpringerLink
Log in

A shared memory algorithm and proof for the generalized alternative construct in CSP

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

Communicating Sequential Processes (CSP) is a paradigm for communication and synchronization among distributed processes. The alternative construct is a key feature of CSP that allows nondeterministic selection of one among several possible communicants. A generalized version of Hoare's original alternative construct that allows output commands to be included in guards has been proposed. Previous algorithms for this construct assume a message passing architecture and are not appropriate for multiprocessor systems that feature shared memory. This paper describes a distributed algorithm for the generalized alternative construct that exploits the capabilities of a parallel computer with shared memory. A correctness proof of the proposed algorithm is presented to show that the algorithm conforms to somesatefy andliveness criteria. Extensions to allow termination of processes and to ensure fairness in guard selection are also given.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. A. R. Hoare, Communicating Sequantial Process,Communications of the ACM 21 (8):666–677 (August) 1978).

    Google Scholar 

  2. C. A. R. Hoare,Communicating Sequantial Processes, Computer Science, Prentice Hall (1985).

  3. E. W. Dijkstra, Guarded Commands, Nondeterminism and Formal Derivation of Programs,Communications of the ACM 18,(8):453–457 (August 1975).

    Google Scholar 

  4. A. A. Aaby and K. T. Narayana, A Distributed Implementation Scheme for Communicating Processes,Proceedings of the International Conference on Parallel Processing, pp. 942–949 (August 1986).

  5. R. Bagrodia, A Distributed Algorithm to Implement the Generalized Alternative Command in CSP,The 6th International Conference on Distributed Computing Systems, pp. 422–427 (May 1986).

  6. A. J. Bernstein, Output Guards and Nondeterminism inCommunicating Sequantial Processes, ACM Transactions on Programming Language and Systems 2(2):234–238 (April 1980).

    Google Scholar 

  7. G. N. Buckley and A. Silberschatz, An Efficient Implementation for the Generalized Input-Output Construct of CSP,ACM TOPLAS 5(2):223–235 (April 1983).

    Google Scholar 

  8. M. Collado, R. Morales, and J. J. Moreno, A Modula-2 Implementation of CSP,ACM SIGPLAN Notices 22(6):25–37 (June 1987).

    Google Scholar 

  9. OCCAM Programming Manuael. Inmos. Ltd. (1982).

  10. R. B. Kieburtz and A. Silberschatz, Comments on Communicating Sequential Processes,ACM Transactions on Programming Language and Systems 1(2):218–225 (October 1979).

    Google Scholar 

  11. Z. Sun and X. Li CSM: A Distributed Programming Language,IEEE Transactions on Software Engineering SE13(4):497–500 (April 1987).

    Google Scholar 

  12. D. R. Jefferson, Virtual Time,ACM Transactions on Programming Languages and Systems 7(3):404–425 (July 1985).

    Google Scholar 

  13. J. Misra, Distributed-Discrete Event Simulation,ACM Computing Surveys 18(1):39–65 (March 1986).

    Google Scholar 

  14. D. A. Reed, A. D. Malony, and B. D. McCredie, Parallel Discrete Event Simulation: A Shared Memory Approach,Proceedings of the ACM SIGMETRICS Conference on Measuring and Modeling Computer Systems 15(1):36–38 (May 1987).

    Google Scholar 

  15. B. Thomas, et al.,Butterfly Parallel Processor Overview, BBN Report No. 6148, BBN Laboratories Incorporated (March 1986).

  16. G. F. Pfister, et al., The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture,Proceedings of the International Conference on Parallel Processing, pp. 764–771 (August 1985).

  17. D. D. Gajski, D. H. Lawrie, D. J. Kuck, and A. H. Sameh, Cedar,COMPCON-84, IEEE Computer Society Conference, pp. 306–309 (February 1984).

  18. D. A. Reed and R. M. Fujimoto,Multicomputer Networks: Message-Based Parallel Processing. Computer Science, MIT Press (1987).

  19. R. A. Karp, Proving Failure-Free Properties of Concurrent Systems. Using Temporal Logic,ACM Transactions on Programming Language and Systems 6(2):239–253 (April 1984).

    Google Scholar 

  20. N. Francez,Fairness, Springer-Verlag, New York (1986).

    Google Scholar 

  21. S. Owicki and L. Lamport, Proving Liveness Properties of Concurrent Programs,ACM Transactions on Programming Language and Systems 4(3):455–495 (July 1982).

    Google Scholar 

  22. D. Zobel, Transformations for Communication Fairness in CSP,Information Processing Letters 25:195–198 (May 1987).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Utah, 84112, Salt Lake City, Utah

    Richard M. Fujimoto

Authors
  1. Richard M. Fujimoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hwa-chung Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported by ONR Contract Number N00014-87-K-0184.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fujimoto, R.M., Feng, Hc. A shared memory algorithm and proof for the generalized alternative construct in CSP. Int J Parallel Prog 16, 215–241 (1987). https://doi.org/10.1007/BF01407934

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key Words

Search

Navigation