Chandy–Lamport algorithm: Difference between revisions

Revision as of 19:30, 19 October 2006

Revision as of 17:30, 30 June 2007

Line 1:

The '''snapshot algorithm''' is an [[algorithm]] used in [[distributed systems]] for recording a consistent global state of an [[asynchronous communication|asynchronous]] system. It is also known as "'''Chandy-Lamport Algorithm for the determination of consistent global states''', after [[Leslie Lamport]] and [[K. Mani Chandy]]."

==History==

According to [http://research.microsoft.com/users/lamport/pubs/pubs.html#chandy Leslie Lamport's website], "The“The distributed snapshot algorithm described here came about when I visited Chandy, who was then at the [[University of Texas at Austin|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."”

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

According to [http://research.microsoft.com/users/lamport/pubs/pubs.html#chandy Leslie Lamport's 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."

It was defined in a paper titled "[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

Line 22 ⟶ 20:

==Working==

The snapshot algorithm works like so:

# The observer 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 observer process its own saved state

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

# Should a process that has already received the snapshot token receive a message that does not bear the snapshot token, this process will forward that message to the observer 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 observer builds up a complete snapshot: a saved state for each process and all messages "in“in the ether"ether” are saved.

==References==