(n,k)-星图网络的t/m-诊断度及诊断算法

故障诊断度在衡量多处理机系统可靠性上起着极其重要的作用.t/m-诊断分析是一种能极大提高多处理机系统自我诊断性能的诊断策略,该诊断策略能至多识别t个故障处理机,其中最多包含m个被误诊的无故障处理机.在PMC诊断模型下,证明了(n,k)-星图是n+(m-1)k-2m+1/m-可诊断的,其中2≤m≤4,且给出了复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点,其中N是(n,k)-星图网络节点总数.     

Pancake网络的t/k-诊断度及其算法

由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略,该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.