（n，k）-星图的g邻域可诊断性资源-CSDN文库

126 浏览量 2021-03-24 02:37:35 上传评论收藏 395KB PDF 举报

在讨论多处理器系统中，随着系统规模的增加和应用的拓展，系统组件更加易于出现故障，因此故障诊断性成为了评估多处理器系统可靠性的一个重要指标。本文中提到的两个基础模型是基于多种策略来确定多处理器系统的诊断性。Preparata、Metze和Chien首次提出了一个模型，而MM*模型则是另一种。在这两种模型中，故障诊断性的概念被扩展到了g邻域诊断性的概念，g邻域诊断性指出了每一个无故障节点至少需要有g个无故障邻居的概念。文中详细研究了(n,k)-星图的g邻域可诊断性问题，其中(n,k)-星图是多处理器系统中常见的互联网络拓扑结构。作者得出了在PMC模型和比较模型下(n,k)-星图Sn,k的g邻域可诊断性分别为n+g(k-1)-1。此外，作者还推导出在比较模型下对于3≤k≤n-1和n≥4时，(n,k)-星图Sn,k的一邻域可诊断性为n+k-2。对于(n,1)-星图Sn,1的情况，作者补充了在PMC模型和比较模型下，g邻域可诊断性分别为[(n/2)]-1。这些研究结果为理解和设计大规模多处理器系统提供了一种新的视角，即通过g邻域可诊断性来评估其容错能力。多处理器系统由大量处理器组成，这些处理器通过互联网络相连，形成复杂的网络拓扑结构。在这样的系统中，互联网络扮演了关键角色，它不仅影响系统的通信效率，还直接关系到系统的容错能力和诊断性。一般来说，系统的诊断性指的是系统识别自身故障部件的能力，而g邻域诊断性则是一种更为细致的诊断性度量，它要求每一个无故障的节点周围至少有一定数量的无故障邻居，这有助于在部分故障发生时仍然维持系统的正常运作。研究中提到的PMC模型和比较模型是用于评估多处理器系统诊断性的两种不同的理论模型。PMC模型由Preparata, Metze和Chien提出，是诊断性问题研究的一个经典模型。而比较模型（MM*模型）则是一种在PMC模型基础上的进一步扩展或变体，它在某些情况下提供了一种不同的诊断性分析方法。这些模型的目的都是为了更好地理解系统的容错特性和故障处理机制。研究的结果不仅在理论上有重要意义，在实际应用中也有很强的指导作用。通过分析不同星图的g邻域可诊断性，系统设计者可以更好地选择合适的拓扑结构，以增强系统在遇到单点故障或部分故障时的容错能力。此外，通过理论推导出的诊断性公式，可以为系统诊断策略的制定提供数学依据，使得在系统发生故障时可以更高效地进行故障定位和恢复。本文还提到了在大规模多处理器系统中，组件的故障是常见现象。由于多处理器系统通常由成百上千个节点组成，每一个节点都有可能发生故障，因此提高系统诊断性对于整个系统的稳定性与可靠性至关重要。通过研究不同系统模型下的g邻域可诊断性，可以为设计更可靠的多处理器系统提供科学依据，为未来多处理器系统的发展奠定基础。

资源推荐

资源详情

资源评论

Theoretical Computer Science 659 (2017) 53–63

Contents lists available at ScienceDirect

Theoretical Computer Science

www.elsevier.com/locate/tcs

The g-good-neighbor diagnosability of (n, k )-star graphs

Xiang Xu

, Xiaowang Li

, Shuming Zhou

a,b,∗

, Rong-Xia Hao

, Mei-Mei Gu

School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian 350108, PR China

Fujian Provincial Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou, Fujian 350108, PR China

Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, PR China

a r t i c l e i n f o a b s t r a c t

Article history:

Received

4 May 2016

Received

in revised form 5 September 2016

Accepted

7 November 2016

Available

online 23 November 2016

Communicated

by S.-Y. Hsieh

Keywords:

Multiprocessor

systems

(n, k)-star graphs

PMC

model

MM*

model

Diagnosability

The

g-good-neighbor diagnosability

Many large-scale multiprocessor or multi-computer systems take interconnection networks

as underlying topologies. Fault diagnosis is especially important to identify fault tolerability

of such systems. The g-good-neighbor (conditional) diagnosability such that every fault-free

node has at least g fault-free neighbors is a novel measure of diagnosability. In this paper,

we show that the g-good-neighbor diagnosability of the (n, k)-star graph S

n,k

under the

PMC model (2 ≤ k ≤ n − 1and 1 ≤ g ≤ n − k) and the comparison model (2 ≤ k ≤ n − 1and

2 ≤ g ≤ n − k ) is n + g(k − 1) − 1, respectively. In addition, we derive that 1-good-neighbor

diagnosability of S

n,k

under the comparison model is n + k − 2for 3 ≤ k ≤ n − 1and n ≥ 4.

As a supplement, we also derive that the g-good-neighbor diagnosability of the (n, 1)-star

graph S

n,1

(1 ≤ g ≤n/2 − 1and n ≥ 4) under the PMC model and the comparison model

is n/2 − 1, respectively.

1. Introduction

With the development of scalability and application of multiprocessor systems, the components of such systems are

prone to failure. So fault diagnosability becomes an important metric to evaluate the reliability of multiprocessor systems.

Two fundamental models have been proposed for determining multiprocessor system’s diagnosability based on various

strategies. Preparata, Metze, and Chien [22] ﬁrst proposed the PMC model for fault diagnosis in multiprocessor systems. Its

target is to identify the exact set of all faulty processors before their repair or replacement. Under the PMC model, all tests

are performed between two adjacent processors, and the result of a test is reliable (respectively, unreliable) if the processor

that initiates the test is fault-free (respectively, faulty). The PMC model has been adopted to identify faults in various

topologies [2,4,13,25,31,32]. The comparison-based diagnosis model, ﬁrst proposed by Malek [19], has been considered to

be a practical approach for fault diagnosis in multiprocessor systems. In 1981, Maeng and Malek [20] extended Malek’s

comparison approach to allow the comparisons carried out by the processors themselves. Maeng and Malek’s model is

referred to as the MM model. Sengupta and Dahbura [23] further suggested a modiﬁcation of the MM model, called the

MM* model, in which any processor has to test any two processors if the former is adjacent to the later two, and proposed a

general diagnostic algorithm with time complexity O (N

) in a N-processor system. Numerous studies on fault identiﬁcation

of multiprocessor-systems under the comparison model have been developed [2,10,11,30].

system-level diagnosis theory, identifying faulty processors is called fault diagnosis. The diagnosability, denoted by

t(G), of a system G is the maximum number t such that the system is self-diagnosable as long as the number of faulty

Corresponding author at: School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian 350108, PR China.

E-mail

address: zhoushuming@fjnu.edu.cn (S. Zhou).

http://dx.doi.org/10.1016/j.tcs.2016.11.007

0304-3975/

54 X. Xu et al. / Theoretical Computer Science 659 (2017) 53–63

processors is not greater than t. Because it is impossible that all neighbors of some processor are faulty simultaneously

in a large-scale multiprocessor system, Lai et al. [13] introduced conditional diagnosability under the assumption that all

neighbors of any processor in a multiprocessor system cannot be faulty simultaneously. Conditional diagnosability is more

realistic and appropriate than traditional diagnosability in system-level diagnosis theory. The conditional diagnosabilities

of many topologies under the PMC model or the comparison model have been studied, including folded hypercubes [32],

BC networks [33], Cayley graphs generated by transposition trees [15], shuﬄe-cubes [16], alternating group networks [30],

split-star graphs [17], (n, k)-star graphs [29], and arrangement graphs [18]. Recently, Hao et al. [12] have established the

general relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs.

2012, Peng et al. [21] proposed a new measure for fault diagnosis of multiprocessor systems, namely, the g-good-

neighbor (conditional)

diagnosability, which requires that every fault-free node has at least g fault-free neighbors. The

maximum t for which the multiprocessor system G is g-good-neighbor t-diagnosable is called the g-good-neighbor di-

agnosability

of G. Peng et al. [21] established the g-good-neighbor diagnosability of the n-dimensional hypercube under the

PMC model. Meanwhile, Yuan et al. [27,28] studied the g-good-neighbor diagnosability of k-ary n-cube networks (k ≥ 3)

under the PMC model and the MM* model. Yuan et al. showed that the g-good-neighbor conditional diagnosability of 3-ary

n-cube is g(2n − g + 1)/2 − 1(resp., (g − 1)(4n − 2g + 1)/2 − 1) when g is even (resp., odd); and they determined that the

g-good-neighbor conditional diagnosability of k-ary n-cube under the PMC model and the MM* model is (2n − g + 1)2

− 1

for

k ≥ 4, n ≥ 3 and 0 ≤ g ≤ n. Wang et al. [24] explored 2-good-neighbor diagnosability of the Cayley graph C 

gen-

erated

by the transposition tree 

under the PMC model and the MM* model, and obtained that the 2-good-neighbor

diagnosability is g(n − 2) − 1, where g is the girth of C 

(n ≥ 5).

a generalized version of n-dimensional star graph S

, the (n, k)-star graph S

n,k

, proposed by Chiang and Chen [1],

preserves most attractive properties of S

. Agreat deal of researches have been done already on the S

n,k

. Cheng et al.

[8] established explicit formulas for the length two path centered surface areas of (n, k )-star graph S

n,k

. Cheng et al. [5]

determined

the strong matching preclusion number for S

n,k

. Cheng et al. [6], Chang et al. [3] and Zhou [29] independently

investigated the conditional diagnosability of S

n,k

for n ≥ 4 and 2 ≤ k ≤ n − 1under the comparison diagnosis model. Chiu

et al. [9] proposed an eﬃcient routing algorithm for S

n,k

based on the probabilistic safety vector. Yang et al. [26] explored

low order conditional connectivity of S

n,k

, and determined κ

n,k

) = n + k − 3for n ≥ 3 and κ

n,k

) = n + 2k − 5for n ≥ 5.

Li et al. [14] extended the conditional connectivity of S

n,k

, and obtained κ

n,k

) = n + g(k − 2) − 1for 2 ≤ k ≤ n − 1 and

0 ≤ g ≤ n − 1.

this paper, we show that the g-good-neighbor diagnosability of the (n, k)-star graph S

n,k

under the PMC model

(2 ≤ k ≤ n − 1 and 1 ≤ g ≤ n − k) and the comparison model (2 ≤ k ≤ n − 1 and 2 ≤ g ≤ n − k) is n + g(k − 1) − 1,

respectively. In addition, we derive that 1-good-neighbor diagnosability of S

n,k

under the comparison model is n + k − 2for

3 ≤ k ≤ n − 1 and n ≥ 4. As a supplement, we also derive that the g-good-neighbor diagnosability of the (n, 1)-star graph

n,1

(1 ≤ g ≤n/2 − 1 and n ≥ 4) under the PMC model and the comparison model is n/2 − 1, respectively.

The

rest of this paper is organized as follows. Section 2 provides some preliminaries to be used in the context. Sec-

tion 3 and

Section 4 explore the g-good-neighbor diagnosability of S

n,k

under the PMC model and the comparison model,

respectively. Finally, Section 5 concludes the paper.

2. Preliminaries

2.1. Terminologies and notations

In the study of multiprocessor systems, the underlying topology is usually modeled by a graph G = (V , E), where the

vertex set V represents processors and the set of edges E represents all communication links between processors. Through-

out

this paper, we only consider an undirected graph without loops. If (u, v) is an edge in a graph G, we say that u is

adjacent to v and both of u, v are incident to the edge (u, v). Agraph H is called a subgraph of G, denoted by H ⊆ G, if

V (H) ⊆ V (G) and E(H ) ⊆ E(G). Let S be a non-empty subset of V (G). The induced subgraph by S, denoted by G[S], is a

subgraph of G whose vertex-set is S and whose edge-set is the set of those edges of G that have both end-vertices in S. The

symbol G − S denotes the induced subgraphs G[V − S]. The maximal connected subgraphs of G − S are called components.

S is called a vertex-cut of a graph G if and only if G − S is disconnected or a single-vertex set. The connectivity of a graph G,

denoted κ(G), is deﬁned as the minimum cardinality of all vertex cuts of G. We use the notation E

(v) to denote the set

of edges incident with a vertex v ∈ V (G). The cardinality |E

(v)| is called the degree of v, denoted by deg

(v) (or simply

deg(v)). We denote by δ(G) the minimum degrees of vertices of G. G is d-regular if deg(v) = d for every v ∈ V (G). The

neighborhood N

(v) of a vertex v in G is the set of all vertices that are adjacent to v in G. The neighborhood set of S is

deﬁned as N(S) ={u ∈ V − S | there exists some vertex v ∈ S such that (u, v) ∈ E}. Let N[S] = N(S) ∪ S. Let S be a subset

of V (G), u ∈ V (G) − S. We deﬁne N

G[S]

(u) ={v | v ∈ S, (u, v) ∈ E(G)} and deg

G[S]

(u) =|N

G[S]

(u)|. Given two sets of nodes

, F

⊂ V (G), the symmetric difference of two subsets F

and F

is deﬁned as F

 F

= (F

− F

) ∪ (F

− F

For

a given nonnegative integer g, a faulty set F of V (G) is called a g-good-neighbor faulty set, if G − F has the minimum

cardinality degree at least g. Moreover, if G − F is disconnected, the g-good-neighbor faulty set F is called g-good-neighbor

cut of G. The R

-connectivity of G, denoted by κ

(G), is the minimum cardinality over all g-good-neighbor cuts of G.

剩余10页未读，继续阅读

评论收藏

内容反馈

weixin_38723527

粉丝: 3
资源: 953

（n，k）-星图的g邻域可诊断性

基于k-d tree的邻域搜索

论文研究 - 交换超立方体的g邻域可诊断性的证明

论文研究-基于邻域模型的K-means初始聚类中心选择算法 .pdf

论文研究-融合邻域扰动的简化粒子群K-均值聚类算法.pdf

计算机研究 -基于AFS邻域的全局聚类算法.pdf

论文研究-求k邻域的体素栅格算法研究.pdf

论文研究-基于d-邻域子图匿名的社会网络隐私保护.pdf

一些关于粒子群算法的文献-自适应变邻域混沌搜索微粒群算法.pdf

网络游戏-用于在邻域知悉网络中共享上下文信息的系统和方法.zip

图像处理 梯度锐化法 逆反处理 均衡化 k-邻域

论文研究-基于自适应邻域的核密度动态目标分割方法.pdf

关于1的简短说明； 平衡超立方体的2邻域可诊断性

nbselect_邻域半径_MATLAB实现三维点云邻近点的搜索定位_K-dist_K._

行业分类-设备装置-基于对称邻域信息的盲隐写分析方法.zip

音视频-编解码-融入空间邻域信息的图像阈值分割方法研究.pdf

最新资源

图像处理梯度锐化法逆反处理均衡化 k-邻域

关于1的简短说明；平衡超立方体的2邻域可诊断性