Chandy–Lamport algorithm: Difference between revisions

Revision as of 05:08, 27 February 2006

Revision as of 04:11, 7 April 2006

Line 1:

The '''snapshot algorithm''' is an [[algorithm]] used in [[distributed systems]] for recording a consistent global state of an [[asynchronous communication|asynchronous]] system.

==History==

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."

==Definition==

The assumptions of the algorithm are as follows:

Line 25 ⟶ 31:

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

==References==

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

[[Category:Algorithms]]