Global state and snapshot recording algorithms

(20th-December-2019)

• A distributed computing system consists of spatially separated processes that do not share a common memory and communicate asynchronously with each other by message passing over communication channels.

• Each component of a distributed system has a local state. The state of a process is characterized by the state of its local memory and a history of its activity. The state of a channel is characterized by the set of messages sent along the channel less the messages received along the channel. The global state of a distributed system is a collection of the local states of its components.

• Recording the global state of a distributed system is an important paradigm and it finds applications in several aspects of distributed system design.

• For example as following.

• Interpretation in terms of cuts are following figure.

• The Chandy–Lamport algorithm is a snapshot algorithm that is used in distributed systems for recording a consistent global state of an asynchronous system. It was developed by and named after Leslie Lamport and K. Mani Chandy. There are no failures and all messages arrive intact and only once.

• The communication channels are unidirectional and FIFO ordered.

• There is a communication path between any two processes in the system.

• Any process may initiate the snapshot algorithm.

• The snapshot algorithm does not interfere with the normal execution of the processes.

• Each process in the system records its local state and the state of its incoming channels.