Talk:Chandy–Lamport algorithm

Algorithm description is incomplete and incorrect

Two problems with the current description:

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

In the paper, the processes don't attach snapshot tokens to messages – they send special marker tokens, independent of other messages in a channel.
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]