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 _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 undecidable. In the case of a static communication structure, testing..-reachabiiity in MO is shown to be log-space reducible to and from exceedability in Petri nets, which like Petri net reachability, 'ELI, is a problem not known to- b~e decidable but requiring at least exponential space, infinitely often. In the usual semantics, a process receiving a message on a channel c deletes an earlier message previously added to the message queue of channel c. A model MI is considered, in which a receiving process codes (rather than deletes) AM (rather than the earliest) message from the appropriate message queue. Thus, in M1, the message queues are of non-decreasing length and can be considered to be unordered. Executions in M1 are characterized by extended regular expressions similar to the path expressions of Haberman CHI. For each program statement, there is an extended regular expression with empty language just in case the given program statement in unreachable in Ml. We show that reachability in MI is an MVP-complete problem. Finally, we consider a reasonable model M2 for communicating processes in which analysis algorithms require polynomial time and space. A11 statements are reachable in MZ iff there exists an acyclic: digraph called an event spanningG ra h containing a spanning tree of each process's program flow graph, as well as certain edges (called message links), connecting pairs of TRANSMIT and RECEIVE statements between which a message may be. sent. A .linear time algorithm is presented'for constructing an event spanning graph, if possible, for the case of a static communication structure. The fifth section of this paper describes an iterative technique for data flow analysis of communicating processes with a static communication structure, which generalizes a technique for data flow analysis of sequentially executed programs developed by Iiecht and Ullman CHlJ2J. Thei~r algorithm repeated (until convergence) a pass through the flow graph of a single program, in topo-logical order of its DAG; our proposed algorithm repeats a pass through all the flow graphs of a set of communicating processes, in topological order of their event spanning graph. The final section of this paper presents a data flow analysis algorithm for the case of a dynamic communication structure. This algorithm builds an event spanning graph while simultaneously performing data flow analysis.

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...