A Caltech Library Service

Synchronizing Processes

Hofstee, H. Peter (1994) Synchronizing Processes. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished)

Postscript - Submitted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


In this monograph we develop a mathematical theory for a concurrent language based on angelic and demonic nondeterminism. An underlying model is defined with sets of sets of sequences of synchronization actions. A refinement relation is defined for the model, and equivalence classes under this relation are identified with processes. Processes, together with the refinement relation, form a complete distributive lattice. We define a language with parallel composition, sequential composition, angelic and demonic nondeterminism, and an operator that connects pairs of synchronization actions into synchronization statements and hides these actions from observation. Also, angelic and demonic iteration are defined. All operators are monotonic with respect to the refinement ordering. Many algebraic properties are proven from these definitions. We study duals of processes and prove that they can be related to the most demonic environment in which a process will not deadlock. We give a simple example to illustrate the use of duals. We study classes of programs for which angelic choice can be implemented by probing the environment for its next action. To this end specifications of processes are extended with simple conditions on the environment. We give a more elaborate example to illustrate the use of these conditions and the compositionality of the method. Finally we briefly introduce an operational model that describes implementable processes only. This model mentions probes explicitly. Such a model may form a basis for a language that is less restrictive than ours, but that will also have less attractive algebraic properties.

Item Type:Report or Paper (Technical Report)
Additional Information:© 1995 H. Peter Hofstee. All rights reserved. California Institute of Technology. The research described in this thesis was funded in part by two I.B.M. graduated fellowships, the Advanced Research Projects Agency, and the Air Force under grant AFOSR91-0070. I thank them all for their support.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
Advanced Research Projects Agency (ARPA)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)AFOSR-91-0070
Series Name:Computer Science Technical Reports
Record Number:CaltechCSTR:1994.cs-tr-94-19
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26874
Deposited By: Imported from CaltechCSTR
Deposited On:14 May 2001
Last Modified:03 Oct 2019 03:18

Repository Staff Only: item control page