Chandy–Lamport algorithm
• This algorithm uses a control message, called a marker.
• After a site has recorded its snapshot, it sends a marker along all of its outgoing
channels before sending out any more messages.
• Since channels are FIFO, marker separates the messages in the channel into those to be
included in the snapshot from those not to be recorded in the snapshot. This addresses
issue I1.
• The role of markers in a FIFO system is to act as delimiters for the messages in the
channels so that the channel state recorded by the process at the receiving end of the
channel satisfies the condition C2.
• Since all messages that follow a marker on channel C
ij
have been sent by process p
i
after p
i
has taken its snapshot, process p
j
must record its snapshot if not recorded earlier
and record the state of the channel that was received along the marker message. This
addresses issue I2.
• The algorithm
• The algorithm is initiated by any process by executing the marker sending rule.
• The algorithm terminates after each process has received a marker on all of its incoming
channels.
• Algorithm 4.1 The Chandy–Lamport algorithm.
Marker sending rule for process p
i
(1) Process p
i
records its state.
(2) For each outgoing channel C on which a marker
has not been sent, p
i
sends a marker along C
CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
19
Jeppiaar Institute of Technology
before p
i
sends further messages along C.
Chia sẻ với bạn bè của bạn: |
