Chandy–Lamport algorithm: Difference between revisions

Revision as of 03:08, 4 March 2019

Latest revision as of 20:43, 5 February 2025

(20 intermediate revisions by 18 users not shown)

Line 1:

{{one source |date=May 2024}}

The '''Chandy–Lamport algorithm''' is a [[snapshot algorithm]] that is used in [[distributed systems]] for recording a consistent global state of an [[asynchronous communication|asynchronous]] system. It was developed by and named after [[Leslie Lamport]] and [[K. Mani Chandy]].<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, FebruarFebruary 1985. ([http://researchlamport.microsoftazurewebsites.com/users/lamportnet/pubs/chandy.pdf PDF; 1&nbsp;MB])</ref>

==History==

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

==Definition==

Line 19 ⟶ 20:

==Algorithm==

The Chandy-LamportChandy–Lamport algorithm works like this:

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

## Saves its own local state

Line 33 ⟶ 35:

{{Reflist}}

{{DEFAULTSORT:Chandy-Lamport algorithm}}

[[Category:Distributed algorithms]]