Study and analysis of Chandy Misra snapshot algorithm
Jing Mao
Department of Computer Science
Kent State University
Abstract— In this paper, we are going to study snapshot algorithm, namely Chandy-Mishra Snapshot algorithm. The paper is based on the practical implementation of the algorithm and comparison is made according to the experiment results. The algorithm is implemented on C++ platform. The message complexity and time complexity are used to measure the performance of the Chandy-Mishra Snapshot algorithm. Section I is the introduction of this research. In section II of this paper, I am going to describe how I set up the experiment. Section III will analyze the results. Section IV will talk about the conclusion of this research in brief.
Keywords— Chandy-Mishra; Snapshot; time complexity; message complexity
I. Introduction
In the introduction, I will talk about the basic concepts of the snapshot algorithm which will enable better understanding of the algorithm and implementation.
A snapshot of a basic computation consists of local snapshots of the state of each process and the messages in transit in each channel. The Chandy-Mishra algorithm uses a control message, called a marker whose role in a FIFO system is to separate messages in the channels. After a site has recorded its snapshot, it sends a marker, along all of its outgoing channels before sending out any more messages. A marker separates the messages in the channel into those to be included in the snapshot from those not to be recorded in the snapshot. A process must record its snapshot no later than when it receives a marker on any of its incoming channels.
The algorithm can be initiated by any process by executing the “Marker Sending Rule” by which it records its local state and sends a marker on each outgoing channel. A process executes the “Marker Receiving Rule” on receiving a marker. If the process has not yet recorded its local state, it records the state of the channel on which the marker is received as empty and executes the “Marker Sending Rule” to record its local state. The algorithm terminates after each process has received a marker on all of its incoming channels. All the local snapshots get disseminated to all other processes and all the processes can determine the global state.
II. Experiment design
This research will apply the message complexity and time complexity to study the performance of Chandy-Mishra Snapshot algorithm which will run on top of a basic algorithm, namely random flooding. To better study the performance, various data points (number of processes) are inserted in the implementation of the algorithms to keep track on the number of messages and the time taken till that particular execution point. The number of processes will range from 5 to 35 with the increment of 5. For each data point, I will use the average of 10 trails. Overall, 70 runs of the implementation are taken to measure the message and time complexity.
III. PERFORMANCE EVALUATION
This section will analyze the results coming from the experiments.
The data is shown in TABLE I.
TABLE I. Table Styles data for time complexity and message complexity
No. of Processes / Time Complexity / Message Complexity5 / 35 / 280
10 / 85 / 529
15 / 170 / 798
20 / 275 / 995
25 / 390 / 1157
30 / 524 / 1379
35 / 652 / 1592
Fig 1 shows how the total time taken is related to the number of processes in the Chandy-Mishra Snapshot algorithm. Time taken is measured by the number of messages in the longest chain of causally dependent events. In the Chandy-Mishra Snapshot algorithm, time complexity is O(d) while d is the diameter of the network which is the total number of processes. According to the above analysis, the total time taken should be proportional to the number of processes in the network. In Fig 1, the values of time taken should be all on the same line as marked. The reason those who are not in the line is that it might need more trails(the current are 10) for each data point to make it vary smoothly.
Fig. 1. Time complexity vs processes
Fig 2 illustrates the relationship between the number messages and the number of processes in the network. The number of messages is calculated by the Message complexity - number of messages it takes the algorithm to carry out specified task. In the Chandy-Mishra Snapshot algorithm, message complexity is O(e) and e is the number of edges in the network. From Fig 2, it does represent a linear relationship between message complexity and number of processes.
CONCLUSIONS
As seen in the performance evaluation of the Chandy-Mishra Snapshot algorithm , both the time complexity and message complexity increase linearly as the number of processes increase in the network. To make this conclusion more convincing, future work should including as followings: 1) test it on large real distributed systems; 2) implement the Chandy-Mishra Snapshot algorithm based on other topologies (tree, ring, etc.)
References
[1] LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.
[2] CHANDY, K, LAMPORT, L. Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems, vol 3, no 1, Feb85.
[3] Babaoglu, O, Marzullo , K, Consistent Global States of Distributed Systems: Fundamental Concepts and Mechanisms, Distributed Systems, Sape J. Mullender, Addison-Wesley, 1993.
Fig. 2. Message complexity vs processes