Successful Percentages of Embedding Subsystems into Hypercubes

概要

論文の詳細を見る
In this papers, we will discuss the different percentages of embedding certain subsystems successfully into a n-cube according to the fault model used. We will discuss two fault models: the first one assumes that, in a faulty node, the computational function of the node is lost while the communication function of the faulty node remains intact, and, in the second, the communication function is also lost. In this paper, 2 types of fault tolerable subsystem embedding schemes will be introduced. The first one embeds a complete binary tree into a n-cube with faulty nodes, and the second embeds two (n-1)-subcubes whose total number of faulty nodes is less than half the number of nodes. These schemes are divided into 4 types based on the above two models. First, we will discuss how different the successful percentages of embedding are for 2 of the different types of embedded binary trees that are based on the above two models. Then, we will analyze the possibility that the component nodes of an embedded binary tree can communicate via the faulty nodes that are located in the embedded binary tree. In the embedding process, each faulty node was replaced with a nonfaulty node that was located on another (n-1)-subcude and at a Hamming distance of 1 from the faulty node. The number of faults that led to the successful percentage of embedding will be presented as an upper bound. Next, we will discuss how different the successful embedding percentages are for the 2 types of irregular (n-1)-subcubes based on the two models; that is, if 2^<n-2>+1 or more of the nonfaulty nodes in both of the (n-1)-subcubes can communicate or not via faulty nodes. Here also, the number of faults that led to a successful embedding percentage will be presented as a critical value.
社団法人電子情報通信学会の論文
1998-02-25

Successful Percentages of Embedding Subsystems into Hypercubes

スポンサーリンク

概要

著者

関連論文

スポンサーリンク