[cs63201] on lai-yang global state recording algorithm

[Mikhail Nesterenko]

AOS students,

I took a look at the original paper describing Lai-Yang algorithm. The
paper is now in the "Additional Materials" section.

In the paper, there is no explicit description as to how to convert
their single snapshot (two colors) algorithm into a multiple snapshot
one. They do mention that it is straightforward. 

Indeed, the simple extension is to use integer counters instead of
colors. That is, all processes start out with the counters set to zero
(color white) and increment it every time a new snapshot is initiated.

Note that the complete sequence of messages (sent and received from
the beginning of the computation) has to be kept only at the process C
that gathers the information for the global snapshot. The other
processes only have to record and submit to C the messages they
send/received since the previous snapshot.

Note that, to save space, C does not have to keep track of a message
that was both sent and received during previous snapshot.

As to the "termination". That is, when it is guaranteed that the sent
message is received and thus the information about can be discarded.
Since the only assumption we place on non-FIFO message delivery is
that each message is eventually delivered, there is no bound as to how
long each message may remain in the channel.

Thanks,
--
Mikhail