| Presentation | 2007/7/26 Node-to-Set Cluster-Fault-Tolerant Disjoint Routing in Pancake Graphs Tatsuro WATANABE, Keiichi KANEKO, Shietung PENG, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | With rapid increase of parallel computation systems in their sizes, it is inevitable to develop algorithms that are applicable even if there exists faulty elements in the systems. In addition, the algorithms should tolerate cluster faults instead of a single fault for actual operation. In this paper, we assumed n-1-k cluster faults in an n-pancake graph, which is promising for a topology of interconnection networks and we developed a cluster-fault-tolerant routing algorithm that constructs disjoint paths from one node to k distinct nodes. The maximum length of the paths given by the algorithm is 2n + 3, and the time complexity to construct the paths is O(kn^2). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | parallel computation / algorithm / fault tolerance / dependability / Cayley graph |
| Paper # | DC2007-8 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2007/7/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Dependable Computing (DC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Node-to-Set Cluster-Fault-Tolerant Disjoint Routing in Pancake Graphs |
| Sub Title (in English) | |
| Keyword(1) | parallel computation |
| Keyword(2) | algorithm |
| Keyword(3) | fault tolerance |
| Keyword(4) | dependability |
| Keyword(5) | Cayley graph |
| 1st Author's Name | Tatsuro WATANABE |
| 1st Author's Affiliation | Graduate School of Engineering, Tokyo University of Agriculture and Technology() |
| 2nd Author's Name | Keiichi KANEKO |
| 2nd Author's Affiliation | Graduate School of Engineering, Tokyo University of Agriculture and Technology |
| 3rd Author's Name | Shietung PENG |
| 3rd Author's Affiliation | Faculty of Computer and Information Sciences, Hosei University |
| Date | 2007/7/26 |
| Paper # | DC2007-8 |
| Volume (vol) | vol.107 |
| Number (no) | 174 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |