Browse Prior Art Database

Theorems on Computations of Distributed Systems

IP.com Disclosure Number: IPCOM000127964D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 18 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

K. Maui Chandyl: AUTHOR [+3]

Abstract

This paper presents theorems that are helpful in developing algorithms for the detection of stable properties, recording global snapshots and tracing the execution of distributed systems. The theorems are based on a property of channels.

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

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Theorems on Computations of Distributed Systems

K. Maui Chandyl California Institute of Technology 24 April 1958

Caltech-CS-TFt-88-6

Abstract

This paper presents theorems that are helpful in developing algorithms for the detection of stable properties, recording global snapshots and tracing the execution of distributed systems. The theorems are based on a property of channels.

1 Introduction

A distributed system consists of processes and channels. A process can record its computation, Le., the sequences of actions it performs. A channel is an interface between two processes. Thus, the actions of a channel are actions of the two processes that use the channel. A channel is passive, unlike a process, and it is not possible for a channel to record the sequence of actions performed on it. A system computation, a historical record of what happened in the system, is a sequence of actions of component processes. This paper presents theorems that are helpful in designing algorithms for constructing a system-wide record - the system computation - from local records - the process computations. Such algorithms are useful in detecting stable properties (2( and in debugging distributed systems. The organization of this paper is as follows. The remainder of this section has two parts: Section 1.1 consists of definitions and Section 1.2 has examples that illustrate the definitions. Section 2 container an overview of the results and outlines of the proof. Detailed proofs are found in the Appendix. Applications of the theorems are proposed in Section 3. Section 4 is the conclusion. iOn leave of absence from the University of Texas at Austin.

A system computation is defined as a sequence x such that the projection of x on p is a computation of p, all p, and the projection of z on c is a computation of c, all c. Define a booleaa function H on sequences where H(x) holds if and only if x is a system computation. - Therefore:

(Equation Omitted)

We shall use letters U,V,W for system computations. Let xF be a sequence of actions of p. Define a binary relation (which is read `interleaves') between a sequence y and a set of sequences,

(Equation Omitted)

)

The elements of y (where

California Institute of Technology Page 1 Dec 31, 1988

Page 2 of 18

Theorems on Computations of Distributed Systems

(Equation Omitted)

}) ;are the elements of the xp, all p, and the ordering among elements of each of the xp is preserved in y. The notation x; y represents the sequence obtained by catenating x and y. The concepts discussed so far are from the literature of concurrent systems. Next, we introduce four concepts that are helpful in defining our problem and solution.

1.1.2 New Concepts

Let q and r be the processes that use a channel c, and let xQ and x,. be sequences of actions from q and r respectively. Sequences xQ and x,. are said to match with respect to c if and only if there exists an interleaving of...