Talk:Chandy–Lamport algorithm

Algorithm description is incomplete and incorrect

Latest comment: 2 months ago2 comments2 people in discussion
Resolved
 – Algorithm rewritten from the 1985 paper to use markers on outgoing channels; termination condition now explicit. Sparks19923 (talk) 19:00, 17 May 2026 (UTC)Reply

Two problems with the current description:

  1. "The observer process ... sends a snapshot request message bearing a snapshot token to all other processes" – The observer process doesn't have direct connections to all other processes. The paper by Chandy and Lamport says that after a process has recorded its state, it sends one marker along each of its outgoing channels. That's what our description should say as well: The observer process sends a snapshot token to all its outgoing channels.
  2. The current description says that when a process receives a snapshot token for the first time, it "attaches the snapshot token to all subsequent messages (to help propagate the snapshot token)". This is not guaranteed to work. If the underlying computation doesn't require the process to send any additional messages, then the process will never send snapshot tokens, and some other processes may never receive snapshot tokens.

I think we should rewrite our algorithm description. Our description deviates in two ways from the paper:

  1. In the paper, the processes don't attach snapshot tokens to messages – they send special marker tokens, independent of other messages in a channel.
  2. In our description, a process that has received a snapshot token forwards subsequent messages that don't have a snapshot token to the observer process. In the paper, a process that has received a marker records messages it receives on another channel until it receives a marker on that channel as well.

Another thing: Neither the paper nor our description explains how the algorithm ends. I think it ends when all processes have received a marker on all their incoming channels, but I'm not quite sure. Yet another thing: We should explicitly specify that the algorithm is based on processes that are connected by channels. At the moment, this information is implicit in the definition. — Chrisahn (talk) 16:01, 5 October 2022 (UTC)Reply

Content and MOS expansion (May 2026)

Latest comment: 2 months ago1 comment1 person in discussion

Full rewrite to address the algorithm correctness issues above and bring coverage to B-class.

Algorithm description (addresses all points raised by Chrisahn, 2022). The previous description incorrectly used an "observer process" that sends tokens directly to all other processes and had processes attach tokens to application messages. The rewrite follows the 1985 paper exactly: the initiating process records its own state and sends a marker (an independent control message, not attached to application messages) on every outgoing channel; each receiving process records its state and propagates markers on its own outgoing channels. The termination condition — all processes have recorded their state and the state of all incoming channels — is now stated explicitly. The model prerequisites (directed FIFO channels, no message loss or reordering, no process failures) are listed in a dedicated Model and assumptions section.

Structure. Article reorganised into Background, History, Model and assumptions, Algorithm, Properties and applications, Variants, See also, References. The previous version had no Background section and placed the algorithm pseudocode before the model it operates on.

History. Added: Lamport's account of the algorithm's origin (dinner with Chandy, shower-next-morning solution); the February 1985 publication venue (ACM Transactions on Computer Systems); the ACM SIGOPS Hall of Fame Award (2013) and Dijkstra Prize (2014); Lamport's Turing Award citation for this work. All sourced to the paper, Lamport's personal notes, and the award pages.

Lead. Expanded to include the principal applications (termination detection, deadlock detection, distributed debugging, checkpointing) cited in the paper and in Lynch and Tel's textbooks.

Citations. Added four sourced references: the original 1985 Chandy–Lamport paper, Lynch's Distributed Algorithms, Tel's Introduction to Distributed Algorithms, and Ghosh's Distributed Systems. Lamport's Turing Award page and his personal notes page are cited for the history section. All inline citations placed at clause level.

National variety and dates. Added {{Use American English}} and {{Use mdy dates}} — US-origin topic.

Upgrading from Start to B-class: the article now covers the topic comprehensively with sourced inline citations, a clear structure, and an accurate algorithm description verified against the 1985 paper. Sparks19923 (talk) 19:00, 17 May 2026 (UTC)Reply

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.