Home

Currently, as a lot of very powerful micro-processors and high speed network hardwares are produced at low prices, large-scale distributed systems, composed of heterogeneous inter-connected nodes, may become the basis of high-performance and inexpensive parallel processing environments[1]. Therefore, long-running scientific applications on large-scale distributed systems can concurrently use all the available resources in clusters of heterogeneous computers[2][3]. However, when designing and implementing the systems for this purpose, an important problem should be considered. The problem is that as their size becomes greatly larger, their vulnerability to node failures may raise together[2][3]. Thus, they require ways to allow the applications computation to persist despite future crashes. Moreover, the techniques should not result in high overhead. With deliberately saving messages received by each process on volatile or stable storage with its checkpoints, log-based rollback recovery allows a system to be restored beyond its latest globally consistent state. This behavioral property is beneficial for the application fields with the difficulty of rolling back to the earlier state. Among this kind of techniques, sender-based message logging(SBML)[4]-[7] allows each message to be saved on its sender's volatile storage with no synchronous logging on stable storage. Therefore, it's normal operation overhead is much smaller than that of the receiver-based message logging(RBML)[8].

Although it has several advantages like being completely implemented as a software solution and supporting lower cost fault-tolerance compared to RBML, it holds two weaknesses in case there occur some temporary communication errors [4]. First, as the errors potentially have some messages received be partially logged, but their subsequently received messages, fully logged, the recovery process of the original SBML[5]-[7] may continue to perform no longer in case of failures of their receivers. Next, if several application messages may not be totally logged due to the transitory communication errors, this situation may make every send function call invoked after the last received message postponed till the termination of their fully logging procedures is notified by their receivers. To overcome this kind of shortcoming, our previous work presented a consistent SBML protocol enabling every process to piggyback a little control data for partially logged messages on each control message. In this case, the transmitter of every previously sent message can get the receive sequence number(rsn) granted for the message. But, it potentially have the complete recovery data for every message maintained both on the volatile storage of its sender and on volatile storages of senders of its dependents. This paper proposes selective stable message log purging algorithms to expunge needless recovery data from volatile storages of their dependents' senders without resulting in any extra control messages. This beneficial feature can be attained by piggybacking different size of data about receive sequence numbers with no extra messages for logging. The first algorithm only piggybacks an integer value with no extra messages for logging to impose minimum overhead on network link. The second exploits a table with piggybacking data to boost expunging needless recovery data and have enough available space of volatile storage remain long to the hilt.

The original SBML[5]-[7] has the following two problems.

• Potential Inconsistency problem and high recovery cost: its recovery process may not continue to go ahead when temporary transmission errors between failed and other processes occur and so should void rsns of completely logged messages and re-execute a large number of completely logging operations.
• Failure-free performance degradation: every send function call invoked after the last received message has to be postponed till the termination of their fully logging procedures is notified by their receivers.

To address these issues, our previous SBML protocol in [4] was proposed that piggybacks rsns of all the unstable messages on each notification message for a message received right before to its sender. So, this beneficial feature can ensure not only consistent recovery, but also processing postponed messages scheduled to be transmitted much earlier with a little extra cost despite temporary communication faults occurrence. The protocol has every process hold the variables as follows.

• Ssn_i: the send sequence number(SSN) of the last message P_i has sent before.
• Rsn_i: the receive sequence number(RSN) of the last message P_i has deliver before.
• SsnVector_i: a table where SSNVt_i[j] is the ssn of the latest message from process P_j that P_i delivered to the application.
• Sendlg_i: a set keeping e(rcvr, ssn, rsn, data) for every message P_i has sent. Here, element e is the recovery data of a message consisting of the four fields, the identifier of receiver(RID), SSN, RSN and data of the message.
• UMLg_i: a set keeping e(sndr, ssn, rcvr, rsn) from recovery data for all unstable messages included in the notification message to P_i. Here, e is the recovery data of each unstable message, where the four fields are composed of its sender's identifier(SID), SSN, RID and RSN.
• stableRSN_i: the RSN of the last message delivered to P_i or saved when checkpointing. It is exploited for indicating which messages are currently stable.

In the protocol, on delivering the rsn value of message m to q from p, it piggybacks recovery data about all unstable received ones before m and after its last checkpoint on the notification message. A message is called unstable if its dependents don't currently have complete information about its fully logging. In contrast, a message is named, stable, if its property is opposite to that of unstable message. Moreover, the recovery data of each piggybacked unstable message is composed of three fields, its RSN, SSN, and SID. As q obtains the notification message, it should hold the recovery data for the unstable messages attached to the notification message in its memory buffer while m's rsn is reflected into its own log element. The check message for the RSN receipt of m triggers invoking every send function call requested after the unstable messages, but postponed till the termination of their fully logging procedures is notified by their receivers. For instance, when p2 recognizes fully logging of m3 on p4's volatile buffer in Fig. 1, it makes every postponed send function call invoked for actually transmitting out it because the rsn values of all the three messages obtained from p4 can be delivered to p2 during recovery unlike the original SBML. If p tries to save a local checkpointed state, it also enables every postponed send function calls before this state to start executing.

Fig. 1. 
A case depicting shortcomings of [4]

However, it may save not only the complete recovery data for every message on its sender’s volatile storage, Sendlg_sndr, but also on the volatile storages of senders of its dependents, UMLg_P. For instance, after the check messages about the receipt of m1's and m2's RSNs can be obtained by p2 from p1 and p3 in Fig. 1, the recovery data for every message exists on both volatile storages of its sender and its successor’s sender. For this purpose, it needs cost-effective log purging algorithms to expunge needless recovery data from volatile storages of senders of message dependents.

For this purpose, one of two stable message log purging algorithms requiring no extra control message is first introduced, called L-PURGER, enabling a process to piggyback an integer value stableRSN_p on each notification or acknowledgment control message. Here, stableRSN_p is the RSN of the last message which was kept in its sender’s volatile memory and which has been received and seen by p. For instance, if a new message m4 is delivered to p2 from p4, p2 increases its RSN and reply with it with stableRSN₂ to p4, which can remove the recovery data of m1 and m2 from its volatile storage in Fig. 2.

Fig. 2. 
A case depicting effectiveness of L-PURGER

Also, if p4 has previously received several messages and p2 is the transmitter of their dependents, p2 can expunge the duplicated recovery data about the messages from the volatile storage of p2, UMLg₂, after m4’s RSN acknowledgement with stableRSN₄ is delivered to p2 by p4. This case shows our proposed algorithm requires no additional interactions among processes. The first is designed for imposing minimum piggybacking overhead on network links.

The second stable message log purging algorithm, named V-PURGER, exploits a table with piggybacking data, lRSNs_P, for incurring no extra message and forced checkpoint. With this table, this algorithm may significantly boost expunging needless recovery data and have enough available space of volatile storage remain long to the hilt compared with the first one L-PURGER.

V-PURGER can be combined with the protocol in [4] like in Fig. 3. The two algorithms enable their users to control piggybacking overhead depending on their preference and network condition.

Fig. 3. 
Our SBML protocol including V-PURGER

Brief experiments are performed in this paper to compare performance of our two algorithms, L-PURGER and V-PURGER, and that of the traditional one, T-PURGER[6], using a simulation tool[9]. For this purpose, the first performance index is exploited to measure the effectiveness of the presented algorithms; the mean time required till having the volatile memory used on logging for every process full-packed(T_bfull). This factor is the most important metric for this comparison because this kind of inter-message dependency data piggybacking algorithm is designed to potentially have the storage for logging messages available till as late as possible. The evaluation factor T_bfull is examined under the condition that the three algorithms execute with no duplicated control messages and checkpoints. The other factor is exploited for measuring extra checkpointing overheads unavoidably incurred despite each algorithm’s effort; the average number of additional checkpoints that should be forced to take due to the unavailability of the volatile storage(T_addckt).

A general network based system composed of 10 nodes inter-connected is simulated. Each process performs its own task on one node and it is supposed to start and terminate its execution at the same time for simplicity of experiment. The message transmission capacity of a link in the network is 100Mbps and its propagation delay is 1ms. For the simulation, suppose that the size for every message ranges from 1KB to 1MB and the volatile storage size for saving messages is 128MB per process. Every process takes normal checkpointing with a checkpoint interval following an exponential distribution with a mean T_nc=300 seconds. In addition, the mean message sending rate, T_interval, follows an exponential distribution.

Fig. 4 illustrates the mean time of the three algorithms spent till having the volatile memory used on logging for every process full-packed for the specified range of the T_interval values. As T_intervals of all the algorithms arise in Fig. 4, their corresponding T_bfulls also become higher. The outcome comes from the behavioral feature that as application messages are gradually transmitted slower, their message log size also increases at a lower rate. However, as we can expect, T_bfull of algorithm T-PURGER is significantly faster than the two algorithms L-PURGER and V-PURGER. Similarly, V-PURGER vastly surpass L-PURGER in T_bfull. Specifically, as T_interval increments accordingly, the increasing rate of V-PURGER becomes much higher than that of L-PURGER. The advantage of our algorithms comes from their following desirable feature: with these algorithms, each process p can willingly and locally expunge needless recovery data from the volatile storage by only carrying an integer value or a table with piggybacking data on each control message whereas the traditional algorithm does not so.

Fig. 4. 
T_bfull according to T_interval

Fig. 5 illustrates the average number of additional checkpoints to be forced to take triggered by the unavailability of the volatile storage(T_addckt) for the various T_interval values. With this result, it may be recognized that T_addckts of the three algorithms arise when T_interval becomes gradually lower.

Fig. 5. 
T_addckt according to T_interval

This outcome results from the following reason; as processes often disseminate messages, the speed of message log stacking up on the volatile storage may be much faster despite effectiveness of local message purging. In the figure, L-PURGER’s T_addckt is much lower than that of T-PURGER, reducing up to 58%, which illustrates effect of local garbage collection gained by inter-message dependency data piggybacking. Also, V-PURGER performs better than L-PURGER in terms of T_addckt because V-PURGER utilizes table data structure for exchanging dependency data about message stability. However, as the number of processes becomes larger, the piggybacking overhead of V-PURGER may be a performance bottleneck compared with L-PURGER.

Therefore, our proposed algorithms L-PURGER and V-PURGER are fairly effective for making enough available space of volatile storage remain long to the hilt while minimizing network overhead compared with the traditional one. In addition, depending on the scale of the system and its network characteristics, one of our proposed algorithms performs better than the other.

In this paper, two redundant stable message log purging algorithms L-PURGER and V-PURGER were proposed requiring no extra control message interaction. L-PURGER satisfies this goal with a very little overhead by piggybacking an integer value in the notification and check messages about the RSN for every message whereas V-PURGER exploits a table with piggybacking data to boost expunging needless recovery data and potentially have enough available space of volatile storage remain long to the hilt. The experimental outcomes illustrate the two algorithms perform vastly better than the traditional one in terms of volatile storage availability while they have their respective strengths and weaknesses against each other. Therefore, it is believed that the two algorithms can greatly enhance availability of the volatile memory each process holds with low cost if they are applied into the protocol in[4].

For future research, our SBML protocol with the proposed algorithms will be refined to enable their users to control piggybacking overhead depending on their preference and network condition.