Browse Prior Art Database

Analysis of Communicating Processes

IP.com Disclosure Number: IPCOM000128615D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 28 page(s) / 62K

Publishing Venue

Software Patent Institute

Related People

John H. Reif: AUTHOR [+3]

Abstract

We consider a set of "distant" concurrent processes, each sequentially executing a distinct program and communicating by the transmission and reception of messages. By "distant" it is meant that there is no interference between processes by shared variables, interrupts, or any other synchronization primitives beyond thel''nessage primitives. (The processes might in fact reside in the same machine.) Various channels are available for communication between processes, and each channel has a unique process which is the destination of messages trans-mitted through this channel. The system of processes has static communication structure if the channel arguments to message primitives are constants, and otherwise has a dynamic communication structure. In the usual semantics for message communication, the process transmitting a message need not wait until reception of the message, and thus a queue of yet-to-be-received messages is associated with each channel. (in a more restrictive semantics proposed by Hoare CHol, the transmitter of a message is required to wait until acknowledge-ment (a "handshake") of reception of messages.) We are interested in data flow anal flow,analysis of communicating-processes: the discovery of facts about distant processes and propagation of facts between processes. A particular analysis problem of interest is reachability: can a given program statement ever be reached in some execution? Reachability is perhaps the simplist of data flow analysis problems. A related problem is the discovery of the dominators of a given program statement n: those program

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Analysis of Communicating Processes

John H. Reif Computer Science Department The University of Rochester Rochester, NY 14527

TR30

May 1978 The preparation of this paper was supported in part by the Alfred P. Sloan Foundation under grant number 74-I2-5, and in part by the National Science Foundation under grant number MSC76-10825. r Analysis of Communicating Processes

1. Introduction

We consider a set of "distant" concurrent processes, each sequentially executing a distinct program and communicating by the transmission and reception of messages. By "distant" it is meant that there is no interference between processes by shared variables, interrupts, or any other synchronization primitives beyond thel''nessage primitives. (The processes might in fact reside in the same machine.) Various channels are available for communication between processes, and each channel has a unique process which is the destination of messages trans- mitted through this channel. The system of processes has static communication structure if the channel arguments to message primitives are constants, and otherwise has a dynamic communication structure. In the usual semantics for message communication, the process transmitting a message need not wait until reception of the message, and thus a queue of yet- to-be-received messages is associated with each channel. (in a more restrictive semantics proposed by Hoare CHol, the transmitter of a message is required to wait until acknowledge- ment (a "handshake") of reception of messages.) We are interested in data flow anal flow,analysis of communicating-processes: the discovery of facts about distant processes and propagation of facts between processes. A particular analysis problem of interest is reachability: can a given program statement ever be reached in some execution? Reachability is perhaps the simplist of data flow analysis problems. A related problem is the discovery of the dominators of a given program statement n: those program _z_

statements whose first execution always precedes the first execution of n. This paper considers various weakened models for systems of communicating processes. These models allow all executions valid in the . usual semantics of communicating processes, but also may allow additional, spurious executions. Of course, a statement unreachable in such a weakened model is also unreachable in the usual, more powerful, semantics. We desire reasonable nodeis, in which analysis algorithms are demonstratably polynomial time, but powerful enough to be useful in practical situations. (See the computational complexity definitions of Appendix I.) In our basic model MO for a system of communicating processes, we. assume the control flow through each process's program is represented. by a program flow graph as is usual in data flow analysis. Unfortunately, we show that testing reachabitity in our basic model is recursively undecida...