A Shared Memory Algorithm and Proof for the Generalized Alternative Construct in CSP (Communicating Sequential Processes)

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 some satefy and liveness criteria. Extensions to allow termination of processes and to ensure fairness in guard selection are also given.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1987
Accession Number
ADA203009

Entities

People

  • Hwa-chung Feng
  • Richard M. Fujimoto

Organizations

  • University of Utah

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Application Software
  • Channel Models
  • Computer Programming
  • Computer Programs
  • Computers
  • Computing System Architectures
  • Guarantees
  • Lepidoptera
  • Multiprocessors
  • Object Oriented Programming
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Rendezvous
  • Semantics
  • Sequences

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Mathematical Modeling and Probability Theory.