Chandy–Lamport algorithm: Difference between revisions

Revision as of 13:34, 7 April 2006

Latest revision as of 20:43, 5 February 2025

(62 intermediate revisions by 47 users not shown)

Line 1:

{{one source |date=May 2024}}

The '''snapshotChandy–Lamport algorithm''' is ana [[snapshot algorithm]] that is used in [[distributed systems]] for recording a consistent global state of an [[asynchronous communication|asynchronous]] system. It iswas alsodeveloped knownby asand "Chandy-Lamportnamed Algorithmafter for[[Leslie theLamport]] determinationand of[[K. consistentMani global statesChandy]]." <ref>

Leslie Lamport, K. Mani Chandy: [https://research.microsoft.com/users/lamport/pubs/pubs.html#chandy ''Distributed Snapshots: Determining Global States of a Distributed System'']. In: ''ACM Transactions on Computer Systems 3''. Nr. 1, February 1985. ([http://lamport.azurewebsites.net/pubs/chandy.pdf PDF; 1&nbsp;MB])</ref>

==History==

According to one of the authors' [http://research.microsoft.com/users/lamport/pubs/pubs.html#chandy Leslie Lamport's website], "The distributedthe snapshot algorithm described herewas came aboutdescribed when Ihe visited Chandy, who was then at the [[University of Texas in (Austin)]]. HeChandy posed the problem to me over dinner, but wethey had both had too much wine to think about it right then. The next morning, while Lamport was in the shower, Ihe came up with the solution. When Ihe arrived at Chandy's office, he was waiting for mehim with the same solution." Lamport considers the algorithm to be a straightforward application of the basic ideas in his article ''Time, Clocks and the Ordering of Events in a Distributed System''. <ref>{{Cite web |title=The Writings of Leslie Lamport |url=https://lamport.azurewebsites.net/pubs/pubs.html?from=https://research.microsoft.com/users/lamport/pubs/pubs.html&type=path#time-clocks |access-date=2024-08-24 |website=lamport.azurewebsites.net}}</ref>

According to one of the authors' [http://research.microsoft.com/users/lamport/pubs/pubs.html#chandy website], "The distributed snapshot algorithm described here came about when I visited Chandy, who was then at the University of Texas in Austin. He posed the problem to me over dinner, but we had both had too much wine to think about it right then. The next morning, in the shower, I came up with the solution. When I arrived at Chandy's office, he was waiting for me with the same solution." Leslie Lamport.

It was defined in a paper called [http://research.microsoft.com/users/lamport/pubs/chandy.pdf "Distributed Snapshots: Determining Global States of a Distributed System"]

==Definition==

The assumptions of the algorithm are as follows:

* There are no failures and all messages arrive intact and only once

* The communication channels are unidirectional and [[FIFO (computing and electronics)|FIFO]] ordered

* There is a communication path between any two processes in the system

* Any process may initiate the snapshot algorithm

Line 16 ⟶ 15:

* Each process in the system records its local state and the state of its incoming channels

The algorithm works using marker messages. Each process that wants to initiate a snapshot records its local state and sends a marker on each of its outgoing channels. All the other processes, upon receiving a marker, record their local state, the state of the channel from which the marker just came as empty, and send marker messages on all of their outgoing channels. If a process receives a messagemarker after having recorded its local state, it records the state of the incoming channel from which the marker came as carrying all the messages received since it first recorded its local state.

Some of the assumptions of the algorithm can be facilitated using a more reliable communication protocol such as [[Internet protocol suite|TCP/IP]]. The algorithm can be adapted so that there could be multiple snapshots occurring simultaneously.

==WorkingAlgorithm==

The snapshotChandy–Lamport algorithm works like sothis:

# The observorobserver process (the process taking a snapshot):

The snapshot algorithm works like so:

# The observor process (the process taking a snapshot):

## Saves its own local state

## Sends a snapshot request message bearing a snapshot token to all other processes

# A process receiving the snapshot token *''for the first time*'' on *''any*'' message:

## Sends the observorobserver process its own saved state

## Attaches the snapshot token to all subsequent messages (to help propagate the snapshot token)

# ShouldWhen a process that has already received the snapshot token receivereceives a message that does not bear the snapshot token, this process will forward that message to the observorobserver process. This message was obviously sent before the snapshot "cut“cut off"off” (as it does not bear a snapshot token and thus must have come from before the snapshot token was sent out) and needs to be included in the snapshot.

From this, the observorobserver builds up a complete snapshot: a saved state for each process and all messages "in“in the ether"ether” are saved.

==References==

{{Reflist}}

{{DEFAULTSORT:Chandy-Lamport algorithm}}

[http://research.microsoft.com/users/lamport/pubs/pubs.html#chandy Leslie Lamport's Website]

[[Category:Distributed computingalgorithms]]

[[Category:Algorithms]]

[[Category:Distributed computing]]