3.5 Reliable FastReplica Algorithm

In this Section, we extend the FastReplica algorithm to be able to deal with node failures. The basic algorithm presented in Sections 3.2, 3.4 is sensitive to node failures. For example, if node $N_1$ fails during either transfer shown in Figures 1, 2 then this event may impact all nodes $N_2, ... , N_n$ in the group because each node depends on node $N_1$ to receive subfile $F_1$. In the described scenario, node $N_1$ is acting as a recipient node in the replication set. If a node fails when it acts as the origin node, e.g. node $N_1^1$ in Figure 6, this failure impacts all of the replication groups in the replication subtree rooted in node $N_1^1$. The reliable FastReplica algorithm proposed below efficiently deals with node failures by making the local repair decision within the particular group of nodes. It keeps the main structure of the FastReplica algorithm practically unchanged while adding the desired property of resilience to node failures. In reliable FastReplica, the nodes of each group are exchanging the heartbeat messages with their origin node. The heartbeat messages from nodes to their origin node are augmented with additional information on the corresponding algorithm step and group (list) of nodes to which the nodes currently perform their transfers.

Figure 8: Heartbeat group: the recipient nodes in $G^{\prime } = \{N^{\prime }_1, ..., N^{\prime }_k\}$ send heartbeat messages to the origin node $N^{\prime }_0$.

In Figure 8, the nodes $N^{\prime}_1, ..., N^{\prime}_k$ of group $G^{\prime }$ form the heartbeat group with their origin node $N^{\prime }_0$. Each node $N^{\prime }_i$ sends to $N^{\prime }_0$ the heartbeat messages with additional information on node state in the replication process. Similarly, node $N^{\prime }_0$ belongs to group $G$ with the corresponding origin node $\hat{N}_0$. Thus node $N^{\prime }_0$ sends the heartbeat messages and its node state to $\hat{N}_0$. There are different repair procedures depending on whether a failed node was acting as a recipient node, e.g. node $N^{\prime }_i$ in replication set $G^{\prime }$, or a failed node was acting as an origin node, e.g. $N^{\prime }_0$ for replication set $G^{\prime }$.

• If node $N^{\prime }_i$ fails while acting as a recipient node in replication set $G^{\prime }$ during the distribution step then the communication pattern is similar to the pattern shown in Figure 1. In this case, node $N^{\prime }_0$ is aware of the node $N_i^{\prime}$ failure. Node $N^{\prime }_0$ performs the following repair step: it uses $k-1$ already opened connections to the rest of the nodes in group $G^{\prime }$ to send the missing $F_i$ file to each node in the group as shown in Figure 9.

  Figure 9: Repair procedure for node $N^{\prime }_i$ failed during distribution step.

  
  In this way, each node in group $G^{\prime }$ receives all of the subfiles of the original file $F$. Additionally, node $N^{\prime }_0$ acts as a ``substitute'' for the failed node $N_i^{\prime}$ in the next algorithm step. If node $N_i^{\prime}$ was supposed to serve as the origin node to group $G^{{\prime}{\prime}}$ for the next algorithm iteration, then node $N^{\prime }_0$ acts as the origin node to group $G^{{\prime}{\prime}}$ for this iteration.
• If node $N^{\prime }_i$ fails while acting as a recipient node in replication set $G^{\prime }$ during the collection step then the communication pattern is similar to the pattern shown in Figure 2. Using the heartbeat messages, the failure of node $N^{\prime }_i$ is detected by node $N^{\prime }_0$. Node $N^{\prime }_0$ performs the following repair step: it opens connections to the impacted nodes in group $G^{\prime }$ to send missing file $F_i$ (similar to the repair step shown in Figure 9). In this way, each node in group $G^{\prime }$ receives all of the subfiles of the original file $F$. Analogously, node $N^{\prime }_0$ acts as a substitute for the failed node $N_i^{\prime}$ in the next algorithm step.
• If node $N^{\prime }_0$ fails while acting as the origin node for replication group $G^{\prime }$ during the distribution step then replication group $G^{\prime }$ should be ``reattached'' to a higher-level origin node. Let $\hat{N}_0$ be the corresponding origin node for $N^{\prime }_0$ from the previous iteration step as shown in Figure 8. From heartbeat messages, node $\hat{N}_0$ detects node $N^{\prime }_i$ failure. Node $\hat{N}_0$ analyzes what was the node $N^{\prime }_0$ state in the replication process preceding its failure. Then node $\hat{N}_0$ acts as a replacement for $N^{\prime }_0$: it opens connections to the impacted nodes in group $G^{\prime }$ to send corresponding missing files. Additionally, $\hat{N}_0$ updates every node in $G^{\prime }$ about the change of the origin node (for future exchange of heartbeat messages).

Reliable FastReplica, described above, aims to minimize the impact of node failures by making the local repair decision within the particular group of nodes. These groups are relatively small, e.g. 10-30 nodes. Each group has the origin node (with the original file for replication) and the recipient nodes. The number of heart-bit messages in such a group is very small because only the recipient nodes send heart-bit messages to their origin node, and there are no heart-bit messages between the recipient nodes. This structure significantly simplifies the protocol. Proposed failure mechanism easily handles a single node failure within the group with minimal performance penalty. The main structure of the FastReplica algorithm is practically unchanged during the repair steps.