4.3 Article

Fault tolerance in bubble-sort graph networks

Journal

THEORETICAL COMPUTER SCIENCE
Volume 421, Issue -, Pages 62-69

Publisher

ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2011.11.016

Keywords

Distributed systems; Interconnection networks; Node failure; Link failure; Bubble-sort graphs

Funding

  1. National Natural Science Foundation of China [61070229]
  2. Natural Science Foundation for Young Scientists of Shanxi Province, China [2011021004]

Ask authors/readers for more resources

The bubble-sort graph B-n is one of the attractive underlying topologies for distributed systems. F-B(n, k) (resp. f(B)(n, k)) is the minimum number of faulty nodes (resp. links) that make every (n - k)-dimensional sub-bubble-sort graph faulty in B, under node (resp. link) failure model. In this paper, we proved that F-B(n, 0) = f(B)(n, 0) = 1, F-B(n, 1) = f(B)(n, 1) = n for n >= 4, F-B(n, 2) <= f(B)(n, 2) <= n(2n - 3) for n >= 6, F-B(n, n - 2) = n!/2 for n >= 3, f(B)(n, n - 2) = (n - 1)n!/2 for n >= 3, F-B(n, n - 1) = n! for n >= 2, and F-B(n, k) <= f(B)(n, k) <= inverted right perpendicular(k+ 1)/2inverted left perpendiculark!C-k(n) for n >= 6 and 3 <= k <= n - 3. (C) 2011 Elsevier B.V. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available