Chandy-Lamport algorithm

from Wikipedia, the free encyclopedia

The Chandy-Lamport algorithm is a snapshot algorithm ; H. a method used to determine a global state of an active distributed system . It was developed in 1985 by Leslie Lamport and K. Mani Chandy .

Assumptions

The following assumptions are made for the algorithm:

  • Errors are excluded, messages are only sent once
  • The communication channel is unidirectional and arranged according to the FIFO principle
  • There is a communication path between any pair of processes in the system
  • Any process can trigger the algorithm
  • The algorithm does not affect the normal execution of the process
  • Each process in the system records its local state and the state of its leading channels

procedure

The process that starts the snapshot algorithm takes a snapshot of its local state and sends a marker to each continuing channel. There are two options when receiving a marking message:

  1. When the first marker is received, the process saves its status, sends the marker message in turn to the continuing channels and starts recording all incoming messages.
  2. If a mark has already been received, the process will stop recording.

This procedure records both the actual status of the processes and messages between individual processes.

literature