DISTRIBUTED COMPUTTING (snapshot).pptx

Study purpose

1. DISTRIBUTED COMPUTING Chandy- Lamport Snapshot algorithm for FIFO Channel

2. ❖ In a Distributed system, more processes may be running on different physical servers. These processes communicate with each other via communication channels using text messaging. ❖ These processes neither have a shared memory nor a common physical clock, so determining the global state of a distributed system is very difficult. ❖ But a process could record its own local state at a given time but a message that is in transit (on its way to be delivered) will not be included in the recorded state and hence the actual state of the system/process is incorrect after the transit message is delivered.

3. As shown in the below diagram, if we record only the local states of the process S1 and S2 and omit the communication channels, then Rs.500 will not be tallied in both accounts A and B as that delivering message is in transit between both accounts while taking snapshot FOR EXAMPLE

4. GLOBAL SNAPSHOT: Global Snapshot = Global State = Collection of individual states of each process in the distributed system + individual state of each communication channel in the distributed system SNAPSHOT: ❖ Is a photograph of a process taken or record it quickly.

5. What is the need for taking snapshots or recording the global state of the system? CHECK POINTING: ❖ Snapshot will use as a checkpoint, to restart the application in case of failure. COLLECTING GARBAGE: ❖ Use to remove objects that don't have any references DETECTING DEADLOCKS: ❖ Use to examine the current application state

6. VARIOUS SNAPSHOT ALGORITHMS 1) FIFO Channel ❖ Chandy_lamport algorithm 2) Non-FIFO Channel ❖ Lai-Yang algorithm Matterrn's algorithm 3)Casual ordering channel ❖ Acharya badrinath & Alagar venkatesan algorithm

7. CHANDY LAMPORT ALGORITHM ❖ This algorithm always captures the consistent global state of a distributed system ❖ The main idea behind the proposed algorithm is that if we know that all messages that have been sent by one process and they have been received by another process, then we can record the global state of the system.

8. ❖ Any process in the distributed system can initiate this global state recording algorithm using a special message called MARKER . ❖ This marker traverse the distributed system across all communication channel and cause each process to record its own state. ❖ In the end, the state of entire system (Global state) is recorded. ❖ This algorithm does not interfere with normal execution of processes.

9. How it works ❖ This algorithm can be initiated by any process by executing the "Marker Sending Rule" records its local state and sends a marker on each outgoing channel. ❖ The receiving process executes the "Marker Receiving Rule" once received the marker. If incase, the process has not yet recorded its local state, it sets the state of the incoming channel on which the marker has been received as EMPTY or NULL

10. ❖ The incoming channel on which the marker has been received is set as empty in order to block any other messages coming on this channel while recording is being done. ❖ Then the receiving process executes the " Marker Sending Rule " to record its own local state + record the state of other incoming channels i.e except the channel on which the MARKER is received.

11. Let us assume, Two processes P1 & P2 are running two channels are C12, C21

12. Initial global state (snapshot 1) of the processes and channels

13. ❖Now, P1 tells P2 to change its state variable x2 to 4. ❖This is an another global snapshot of this distributed system - No: 2

14. ❖ Now P2 receives the message sent by p1 through the channel C12. So the channel C12 becomes empty now. ❖ Global snapshot of this distributed system No: 3

15. ❖ P2 changes its state variable x2 to 4. ❖ Global snapshot of the distributed system - No: 4

16. ❖ Now, the Process P1 initiates the recording process. i.e P1 is the initiator. ❖ So, P1 sends a MARKER message to P2 and begins recording its local state and recording all messages on inbound channels. ❖ Meanwhile, P2 also sent a message to P1

17. ❖ P2 receives the MARKER message for the first time, so records its local state. ❖ Meanwhile P1 also receives the message M1, sent by p2 ❖ Now, P2 sends a MARKER message to P1

18. Now the statue is, P1 has already sent a MARKER message to P2, so it records all messages it received on inbound channels to the appropriate channel's state

19. Now, Both processes have recorded their states and also the states of their all incoming channels

20. ❖Each process has received a MARKER on all of its incoming channels. i.e both processes have recorded their local states. ❖Since only two processes running in this distributed system, the algorithm terminates here. ❖The collection of these two local snapshots, determine the global state of the distributed system.

21. ◌ THANK YOU ◌