Theoretical Computer Science 776 (2019) 138–147
Contents lists available at ScienceDirect
Theoretical Computer Science
www.elsevier.com/locate/tcs
Fault diagnosability of data center networks
Mei-Mei Gu
a
, Rong-Xia Hao
a,∗
, Shuming Zhou
b
a
Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, China
b
School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian 350108, China
a r t i c l e i n f o a b s t r a c t
Article history:
Received
31 December 2016
Received
in revised form 9 January 2019
Accepted
17 January 2019
Available
online 22 January 2019
Communicated
by C. Kaklamanis
Keywords:
Data
center network
g-g
ood-neighbor diagnosability
PMC
model
MM*
model
Fault-tolerance
A kind of generalization of diagnosability for a network G is g-good-neighbor diagnosability
which is denoted by t
g
(G). Let κ
g
(G) be the R
g
-connectivity. Lin et al. (2016) [17]and Xu
et al. (2017) [29]gave the same problem independently that: the relationship between
the R
g
-connectivity κ
g
(G) and t
g
(G) of a general graph G needs to be studied in the
future. In this paper, this open problem is solved for general regular graphs. We firstly
establish the relationship of κ
g
(G) and t
g
(G), and obtain that t
g
(G) = κ
g
(G) + g under
some conditions. Secondly, we obtain the g-good-neighbor diagnosability of data center
network D
k,n
which are t
g
(D
k,n
) = (g + 1)(k − 1) + n + g for 1 ≤ g ≤ n − 1 under the PMC
model and the MM* model, respectively. Furthermore, we show that D
k,n
is tightly super
(n + k − 1)-connected for n ≥ 2and k ≥ 2and we also prove that the largest connected
component of the survival graph contains almost all of the remaining vertices in D
k,n
when
n + 2k − 2vertices removed.
© 2019 Elsevier B.V. All rights reserved.
1. Introduction
The study of interconnection networks has been an important research area for parallel and distributed computer sys-
tems.
A network can be modeled as a graph, in which vertices and edges correspond to processors and communication
links, respectively. Network reliability is one of the major factors in designing the topology of an interconnection network.
With the rapid development of multiprocessor systems, processor failure is inevitable along with the number of processors
increasing. The process of identifying all the faulty units in a system is called as system-level diagnosis. For the purpose of
self-diagnosis of a system, a number of models have been proposed for diagnosing faulty processors in a network. Among
the proposed models, PMC model [20] and comparison model (MM model) [18]are widely used. In the PMC model, every
processor can test the processor that is adjacent to it and only the fault-free processor can guarantee reliable outcome. In
the MM model, to diagnose the system, a processor sends the same task to one pair of its neighbors, and then compares
their responses. The MM* model [21]is a special case of the MM model, in which each node must test any pair of its
adjacent nodes. A system is said to be t-diagnosable if all faulty units can be identified provided the number of faulty units
present does not exceed t. The diagnosability is the maximum number of faulty processors which can be correctly identified.
In 2005, Lai et al. [13]introduced a restricted diagnosability of the system called conditional diagnosability by assuming
that it is impossible that all neighbors of one vertex are faulty simultaneously. The diagnosabilities and conditional diag-
nosabilities
of many networks are studied in related works [1–3], [6–12], [14], [16], [22], [32], [33]etc. Inspired by this
*
Corresponding author.
E-mail
addresses: 12121620@bjtu.edu.cn (M.-M. Gu), rxhao@bjtu.edu.cn (R.-X. Hao), zhoushuming@fjnu.edu.cn (S. Zhou).
https://doi.org/10.1016/j.tcs.2019.01.020
0304-3975/
© 2019 Elsevier B.V. All rights reserved.
下载后可阅读完整内容，剩余9页未读，立即下载
weixin_38601878
- 粉丝: 6
- 资源: 960
我的内容管理
展开
最新资源
- ExtJS 2.0 入门教程与开发指南
- 基于TMS320F2812的能量回馈调速系统设计
- SIP协议详解：RFC3261与即时消息RFC3428
- DM642与CMOS图像传感器接口设计与实现
- Windows Embedded CE6.0安装与开发环境搭建指南
- Eclipse插件开发入门与实践指南
- IEEE 802.16-2004标准详解：固定无线宽带WiMax技术
- AIX平台上的数据库性能优化实战
- ESXi 4.1全面配置教程：从网络到安全与实用工具详解
- VMware ESXi Installable与vCenter Server 4.1 安装步骤详解
- TI MSP430超低功耗单片机选型与应用指南
- DOS环境下的DEBUG调试工具详细指南
- VMware vCenter Converter 4.2 安装与管理实战指南
- HP QTP与QC结合构建业务组件自动化测试框架
- JsEclipse安装配置全攻略
- Daubechies小波构造及MATLAB实现
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
