Browse Prior Art Database

Synchronizing Distant Cooperating Processes

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

Publishing Venue

Software Patent Institute

Related People

Jerome A. Feldman: AUTHOR [+3]

Abstract

Distributed Computing, the execution of a single computation by a network of computers, is currently a very hot topic. As is usual in computing, applications are proceeding in advance of any systematic study of the subject: The technical and economic reasons for the great increase in distributed computing seem likely to remain in force for some time. In addition to its practical significance, distributed computing is a subject of inherent intellectual interest because every complex system, from a micro-organism to a society, does its computations with a number of fairly independent sub-systems whose communications can be viewed as messages. We have previously worked on a message-based model for system programs [Ball et al '76J and on a high-level programming language (PLITS) for distributed computing [Feldman '76J. This paper attempts to lay out an abstract framework for the analysis and synthesis of message-based distributed computation. The direct motivation for the current effort came from a graduate seminar that was working on the refinement and applications of PLITS. The students had very little trouble writing message-based PLITS programs but had great difficulty rovin them correct, even though they could prove ordinary programs. One difficulty was the absence of an agreed upon formalism for demonstrating the correctness of such programs. An initial attempt at such a formalism is one of the three goals of this paper. A second goal is to extend the recent work on synchronization of modules which share memory to those which communicate only by messages. Our third goal is to develop programming and proof techniques which will help in the production of demonstrably correct solutions to real distributed computing problems.

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

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Synchronizing Distant Cooperating Processes

TR26

by

Jerome A. Feldman

October, 1977 Department of Computer Science The University of Rochester Rochester, New York 14627 The preparation of this paper was supported by the Alfred P. Sloan Foundation under grant number 74-I2-5 and by the National Science Foundation grant number MCS76- 10825. >

1. Introduction

Distributed Computing, the execution of a single computation by a network of computers, is currently a very hot topic. As is usual in computing, applications are proceeding in advance of any systematic study of the subject: The technical and economic reasons for the great increase in distributed computing seem likely to remain in force for some time. In addition to its practical significance, distributed computing is a subject of inherent intellectual interest because every complex system, from a micro-organism to a society, does its computations with a number of fairly independent sub-systems whose communications can be viewed as messages. We have previously worked on a message-based model for system programs [Ball et al '76J and on a high-level programming language (PLITS) for distributed computing [Feldman '76J. This paper attempts to lay out an abstract framework for the analysis and synthesis of message-based distributed computation. The direct motivation for the current effort came from a graduate seminar that was working on the refinement and applications of PLITS. The students had very little trouble writing message-based PLITS programs but had great difficulty rovin them correct, even though they could prove ordinary programs. One difficulty was the absence of an agreed upon formalism for demonstrating the correctness of such programs. An initial attempt at such a formalism is one of the three goals of this paper. A second goal is to extend the recent work on synchronization of modules which share memory to those which communicate only by messages. Our third goal is to develop programming and proof techniques which will help in the production of demonstrably correct solutions to real distributed computing problems.

>The choice of a model is often the crucial step in formalization of a domain. Distributed computing presents particular modeling dif-ficulties because an adequate treatment of it requires consideration of several poorly understood concepts including time-dependency, parallelism and unreliability. There also is much less accumulated intuition than is available for monoprocessing.~ The particular model chosen here assumes-that reliable transmission (including preserving sequence) and the detection of dead modules is treated by an underlying system. This is the same level of model used in our PLITS work and seems to be a clean abstraction of a level to be found in most distributed systems. This paper can also be viewed as part of the continuing effort to carefully define and study the problems of s...