โ Scribed by C.S Raghavendra; M.A Sridhar
No coin nor oath required. For personal study only.
computing. Therefore, it is necessary to compute important primitive functions even in the presence of faults. The hypercube network is quite robust [2,20]; in fact, at least n faults are needed to disconnect Q n into two components. The symmetry and robustness of hypercube can be exploited to compute many functions efficiently even when there are about n faults in the systems. Several researchers have developed algorithms for solving a wide range of different problems in the presence of processor and/or communication link faults [2,8,17,4].
In this paper, we develop algorithms for an important global operation, namely, broadcasting from a specific node in the n-dimensional hypercube to all other nonfaulty processors, in the presence of up to n ฯช 1 faulty processors. We are particularly interested in the SIMD mode of operation, in which processors operate in lock-step and every data transfer that occurs at a given time step is made along the same dimension. Further, the broadcasting algorithms presented in this paper are source independent, meaning that the sequence of dimensions used for broadcasting is the same regardless of which source is broadcasting. SIMD operation has the merit that node programs implementing the algorithms are independent of the processor ID, and therefore very simple to develop; thus, our results have direct practical application. It is important to point out here that the broadcasting problem in general has been addressed by many researchers in the past [6,5,12,1,15]. Some of these techniques utilize only local faulty nodes information and/or MIMD mode of operation. Others use table based approach and require large amount of preprocessing. However, very few papers have addressed faulttolerant broadcasting in the SIMD mode of operation. A recent paper studies broadcasting with only link faults and present an optimal broadcasting algorithm with up to n ฯช 1 link faults [14]. This algorithm works in SIMD mode of operation, however, it is not source independent, which means the successive dimensions used depends on the source node address.
We also make two further simplifying assumptions: (1) that there are no more than n ฯช 1 faulty node processors, and no faulty links, in the network and (2) that we know a priori and set of faulty nodes in the network. Our primary intent in making these assumptions is to gain insight into
๐ SIMILAR VOLUMES