Fault-tolerance schemes for clusterheads in clustered mesh networks

To improve the overall system performance for distributed systems using mesh as their underlying structure, a hierarchical approach was proposed in [7]. The hierarchical configuration divides the mesh into clusters, thus allowing for processing to occur in small local groups at the lower levels. After local operations, the results are passed to higher logical levels. This method has been shown to be able to significantly reduce the total communication cost for the entire system. This paper is concerned with the hierarchical system's ability to handle node failure. When using a hierarchical configuration, certain nodes in the mesh become more important to the overall system than others. It is important that the hierarchical system have a reorganising mechanism in case of node failure, in such a way that the performance gain from hierarchical configuration is salvaged as much as possible. The work presented in this paper focuses on minimising the loss of performance in the system hierarchy due to the presence of failing nodes. We will propose fault-tolerance schemes for that purpose. The performance results will be compared to that of an ideal, fault-free system. We will present strategies to reconstruct the hierarchy, accommodating to the situation that some nodes in the original hierarchy are not functioning anymore. To that end, new local heads may be selected and local nodes regrouped. We will also present experiment results that examine the effectiveness of the proposed schemes. Examples of both faulty and fault-free hierarchical mesh systems will be tested to quantify how good the proposed schemes are.