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. doi:10.1145/214451.214456. https://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: https://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: |
| |||||||||
| 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: |
| |||||||||
| Subject Keywords: | Words and Phrases: Global States, Distributed deadlock detection, distributed systems, message communication systems | |||||||||
| Issue or Number: | 1 | |||||||||
| 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 | |||||||||
| DOI: | 10.1145/214451.214456 | |||||||||
| Record Number: | CaltechAUTHORS:20130923-092736838 | |||||||||
| Persistent URL: | https://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: | 10 Nov 2021 04:30 |
Repository Staff Only: item control page
