CaltechAUTHORS
  A Caltech Library Service

Distributed Snapshots: Determining Global States of a Distributed System

Chandy, K. Mani and Lamport, Leslie (1985) Distributed Snapshots: Determining Global States of a Distributed System. ACM Transactions on Computer Systems, 3 (1). pp. 63-75. ISSN 0734-2071. http://resolver.caltech.edu/CaltechAUTHORS:20130923-092736838

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20130923-092736838

Abstract

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/214451.214456DOIArticle
http://dl.acm.org/citation.cfm?id=214456PublisherArticle
Additional Information:Copyright © 1985 ACM, Inc. Received January 1984; revised September 1984; accepted 7 December 1984. This work was supported in part by the Air Force Office of Scientific Research under Grant AFOSR 81-0205 and in part by the National Science Foundation under Grant MCS 81-04459. J. Misra’s contributions in defining the problem of global state detection are gratefully acknowledged. We are grateful to E. W. Dijkstra and C. S. Scholten for their comments-particularly regarding the proof of Theorem 1. The outline of the current version of the proof was suggested by them. Dijkstra’s note [3] on the subject provides colorful insight into the problem of stability detection. Thanks are due to C. A. R. Hoare, F. Schneider, and G. Andrews who helped us with detailed comments. We are grateful to Anita Jones and anonymous referees for suggestions.
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)81-0205
NSFMCS 81-04459
Subject Keywords:Words and Phrases: Global States, Distributed deadlock detection, distributed systems, message communication systems
Classification Code:C.2.4 [Computer-Communication Networks]: Distributed Systems-distributed applications; distributed databases; network operating systems; D.4.1 [Operating Systems]: Process Management-concurrency; deadlocks, multiprocessing/multiprogramming
Record Number:CaltechAUTHORS:20130923-092736838
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20130923-092736838
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:41468
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:23 Sep 2013 16:40
Last Modified:23 Sep 2013 16:40

Repository Staff Only: item control page