Accession Number : ADA187820

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

Descriptive Note : Technical rept.,

Corporate Author : UTAH UNIV SALT LAKE CITY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Fujimoto, Richard M ; Feng, Hwa-Chung

PDF Url : ADA187820

Report Date : 25 Aug 1987

Pagination or Media Count : 37

Abstract : Communicating Sequential Processes (CSP) is a paradigm for communication and synchronization among distributed processes. The alternative constructs is a key feature of CSP that allows nondeterministic selection of one among several possible communicants. 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 alternative construct that exploits the capabilities of a parallel computer with shared memory. The algorithm assumes a generalized version of Hoare's original alternative construct that allows output commands to be included in guards. A correctness proof of the proposed algorithm is presented to show that the algorithm conforms to some safety and liveness criteria. Extensions to allow termination of processes and to ensure fairness in guard selection are also given. Keywords: Communicating sequential processes; Alternative operation; Shared memory multiprocessor; Parallel processing.

Descriptors :   *ALGORITHMS, *DISTRIBUTION, *MEMORY DEVICES, *MULTIPROCESSORS, *PARALLEL PROCESSORS, *TIME SHARING, COMPUTERS, PARALLEL PROCESSING, SEQUENCES

Subject Categories : Computer Systems
      Command, Control and Communications Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE