Browse Prior Art Database

COMMUNICATIONS BETWEEN SEQUENTIAL PROCESSES

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

Publishing Venue

Software Patent Institute

Related People

C.J. Barter: AUTHOR [+3]

Abstract

In this paper we consider programs which are designed and specified as systems of sequential processes, communicating with each other explicitly, by passing messages. Of central importance in such systems is the way in which communication paths or connections are specified: we particularly wish to point to the works of Feldman (77), Hoare (77) and Milne and Milner (77), by way of contrast with each other and with the present work. .We.wish to make two specific proposals concerning the specification of inter-process communication: the first defines the "construction" of a message as the determining attribute of message passing, the second gives a communications significance to the structure of hierarchies of processes. We present these proposals within the framework of a small language, having the following characteristics: (a) Message passing is the sole means of inter-process communication, thereby excluding communication via common data or global variables. (b) For the specification of sequential processes, we adopt the guarded command notation of Dijkstra (75), together with Hoare's (77) extension of that notation to include the possibility of an "input command" as part of a guard. This extension greatly enhances the guarded command notation in a multi-process situation (see later). We also note that Milner (78) establishes "guarding" as a principal .r operation of his algebra of communicating behaviours. (c) We assume asynchronous, buffered communication, and a few convenient operations which allow messages to be treated as record-like data objects (Feldman (77)). The features in (c) are not essential to the present proposal concerning communications, but are included for their expressive power. We could restrict this discussion to synchronous communication, with explicitly represented buffering where needed, but we choose not to. Apart from >2 this, we have made the language as small as is consistent with our aim of providing a framework for experimentation. We define "construction" in a manner similar to Hoare (77), being a concept related to "type", but also including an element associated with the "constructor" of a message. It is our proposal that message construction be the single attribute of a message which determines message reception. More than one message may be pending on a process, perhaps from different senders, but the one chosen for reception is selected by construction alone. In contrast, Hoare (77) defines the name of the sending process to be the determining attribute (and uses "construction" for runtime type checking). Feldman (77) similarly uses the name of the sending process, but may also selectively receive on a "transaction key" associated with a message. Milne and Milner (77) use correspondences between the names of "ports" in the set of communicating processes. From the point of view of~a receiving process, their proposal is similar to ours; from the point of view of a sending process it is not. We shall elaborate this difference in the context of our second proposal, which follows.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COMMUNICATIONS BETWEEN SEQUENTIAL PROCESSES

C.J. Barter

TR34 Novem'-l.er 1978 Computer Science Department University of Rochester Rochester, NY 14627 United States of America Department of Computing Science University of Adelaide G.P.O. Box 498, Australia South Australia 5001 This research was supported in part by the Alfred P. Sloan Foundation under Grant No. 74-12-5 and the National Science Foundation under Grant No. MSC76-10825.

>

1. Introduction

In this paper we consider programs which are designed and specified as systems of sequential processes, communicating with each other explicitly, by passing messages. Of central importance in such systems is the way in which communication paths or connections are specified: we particularly wish to point to the works of Feldman (77), Hoare (77) and Milne and Milner (77), by way of contrast with each other and with the present work. .We.wish to make two specific proposals concerning the specification of inter-process communication: the first defines the "construction" of a message as the determining attribute of message passing, the second gives a communications significance to the structure of hierarchies of processes. We present these proposals within the framework of a small language, having the following characteristics:
(a) Message passing is the sole means of inter-process communication, thereby excluding communication via common data or global variables. (b) For the specification of sequential processes, we adopt the guarded command notation of Dijkstra (75), together with Hoare's (77) extension of that notation to include the possibility of an "input command" as part of a guard. This extension greatly enhances the guarded command notation in a multi-process situation (see later). We also note that Milner (78) establishes "guarding" as a principal

.r operation of his algebra of communicating behaviours. (c) We assume asynchronous, buffered communication, and a few convenient operations which allow messages to be treated as record-like data objects (Feldman (77)). The features in (c) are not essential to the present proposal concerning communications, but are included for their expressive power. We could restrict this discussion to synchronous communication, with explicitly represented buffering where needed, but we choose not to. Apart from

>2

this, we have made the language as small as is consistent with our aim of providing a framework for experimentation.

We define "construction" in a manner similar to Hoare (77), being a concept related to "type", but also including an element associated with the "constructor" of a message. It is our proposal that message construction be the single attribute of a message which determines message reception. More than one message may be pending on a process, perhaps from different senders, but the one chosen for reception is selected by construction alone. In contrast, Hoare
(77) d...