Snapshot algorithm

A snapshot algorithm is used to create a consistent snapshot of the global state of a distributed system.[1] Due to the lack of globally shared memory and a global clock, this isn't trivially possible.

Example

Several computers work together in a distributed system. Each of them represents a bank account holding a certain amount of money. The participants can transfer money between their accounts by exchanging messages.

Assume the overall balance shall be calculated. Just requesting the balance of each participant can lead to an incorrect result, if one of them just sent a transfer message to another one (and thus has already decreased its own balance), which did not yet receive it.

A snapshot algorithm avoids such inconsistencies.

Algorithms

  • Chandy-Lamport algorithm
  • Lai-Yang algorithm
  • Spezialetti-Kearns algorithm
  • Mattern's algorithm
gollark: It has exclude options.
gollark: `cloc` is a program which exists.
gollark: Due to anomalous golfing.
gollark: 592 quintillion. And I contain about 201MLoC of first party code.
gollark: Oh bee, compilation is taking 944873728293847473737281901028484 years.

References

  1. Vijay K. Garg (23 May 2002). Elements of Distributed Computing. John Wiley & Sons. pp. 121–. ISBN 978-0-471-03600-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.