Chandy-Lamport algorithm
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:
- 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.
- 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
- Leslie Lamport, K. Mani Chandy: Distributed Snapshots: Determining Global States of a Distributed System . In: ACM Transactions on Computer Systems 3 . No. 1, February 1985 ( PDF; 1 MB ).