基于比较诊断模型的超立方网络诊断算法

一个有效的诊断算法对多处理器系统而言极其重要。在多处理器系统中,识别所有故障节点的能力称为诊断系统的诊断度。在比较模型下,诊断 的执行是通过一个比较器处理器,给与之相邻的一对处理器发送相同的输入信号,并比较两者间的响应状态。为了提高超立方网络的诊断度,提出了一种新型的基于比较模型的超立方故障诊断算法,其利用超立方网络节点连接的特性生成一个拓扑图ES(k;n),最终得出一个3位二进制的诊断症候集,从而确定系统故障节点。该算法的诊断度最优能达到4n,大于传统超立方的诊断度n。     

3元◢n◣立方体网络的◢t/k◣可诊断度研究

可诊断度是评估多处理器系统可靠性的一个关键指标.t/k诊断策略通过允许至多k个无故障处理器被误诊为故障处理器,从而极大提高了系统的可诊断度.与t可诊断度和t1/t1可诊断度相比,t/k可诊断度可以更好地反映实际系统的故障模式.3元n立方是一种性质优良并且应用广泛的网络拓扑,在许多分布式多处理器的构建中被用做底层网络.根据一些引理以及确定系统为t/k可诊断的充分条件,研究得出当n≥3及0≤k≤n,3元n立方是tk,n/k-可诊断的,其中tk,n=2(k+1)n-(k+1)(k+2).这个结果显示,在选择恰当的k值时,3元n立方的t/k可诊断度tk,n远大于其t可诊断度2n和t1/t1可诊断度4n-3.     

基于敏感性分级的(k,δ,a_i)-匿名模型

(k,δ,a_i)-匿名模型是轨迹数据发布中保护数据隐私的一种k-匿名方法。该匿名模型需要满足所发布的轨迹数据库中任意轨迹在其半径为δ的圆柱内被重新标识出的概率不大于1/k,并且每个等价类中同一时刻处于同一敏感等级的轨迹数不超过k/l。然后从匿名数据库的可用性和安全性两方面与经典模型——(k,δ)-匿名模型进行了比较分析,实验结果表明,随着δ的增大,(k,δ,a_i)-模型与(k,δ)-模型在可用性方面越来越相似,但(k,δ,a_i)-模型比(k,δ)-模型的敏感性差异更大,因此,(k,δ,a_i)-模型安全性更高。     

交换超立方网络的嵌入问题研究

交换超立方网络作为超立方网络的一个变种,具有良好的递归性和理想的网络参数。根据交换超立方网络的相关性质研究了E-2DMesh网络和超立方网络的嵌入问题,并得出如下结论:(1)当max(s,t)<7时,不存在dilation=1的EM(2m,2n)到EH(s,t)的嵌入映射(m+n≤s+t+1)。(2)EM(2s,2t)可以expansion=2,dilation=4,load=1嵌入EH(s,t)。(3)当min(s,t)>1时,不存在dilation=1的Qn到EH(s,t)的嵌入映射(n=s+t)。(4)Qn可以ex-pansion=2,dilation=3,congestion=1,load=1嵌入EH(s,t)(n=s+t)。上述结论进一步说明了交换超立方网络具有良好的扩容性。     

增广立方体网络的t/k诊断度研究*

在多处理器系统,传统的t-可诊断算法在处理大规模故障集时有明显的局限性。针对增广立方体诊断度提升的问题,提出了一种t-可诊断的变形算法,即t/k可诊断。在该新算法下,可明显提高增广立方体的诊断度。算法核心思想是,在故障节点个数不大于t的情况下,允许故障集中出现k个非故障节点。从而在牺牲少数非故障节点的情况下,达到提高网络诊断度的目的。最终证明了,增广立方体在t/k诊断算法下的诊断度明显优于传统诊断度和条件诊断度。     

一种基于超立方体多处理机系统的快速诊断算法

为了提高可诊断系统的诊断度,可以采用悲观诊断策略进行诊断.超立方体是一种应用广泛的互连网络拓扑结构,具有可并行处理的某些性质,且n维超立方体是(2n-2)/(2n-2)-可诊断的.文中在MM*模型下,研究了超立方体的诊断问题,提出了一个O(Nolg2N)的悲观诊断算法,N是处理器总数.而经典的YML算法所需时间为O(N2.5).因此,文中的算法在时间复杂度方面是高效的.     

交换交叉立方网络的g正确邻结点条件诊断度研究

系统级故障诊断是保障多处理器计算机系统运行可靠性的一种重要手段。为了提高系统的诊断能力,增强系统的可靠性,在条件诊断度的基础上Peng等人进一步提出了[g]正确邻结点条件诊断度,[g]正确邻结点条件诊断度是一种更加适用于大规模多处理器计算机系统的故障诊断方式。以新型互连网络拓扑结构研究的最新成果--交换交叉立方网络为研究对象,在得到交换交叉立方网络的[Rg]点连通度的基础上,首次证得交换交叉立方网络[(ECQ(s,t))]在PMC模型下的[g]正确邻结点条件诊断度为[2g(s+2－g)－1],其中[t≥s>g],进而通过模拟实验验证了结论的正确性和有效性。该研究对于理清交换交叉立方网络的可靠性能并有效推动交换交叉立方网络的应用和推广,有着非常重要的理论价值和现实意义。     

抵制敏感属性相似性攻击的(p,k,d)-匿名模型

针对当前p-Sensitive k-匿名模型未考虑敏感属性语义相似性,不能抵制相似性攻击的问题,提出一种可抵制相似性攻击的(p,k,d)-匿名模型。根据语义层次树对敏感属性值进行语义分析,计算敏感属性值之间的语义相异值,使每个等价类在满足k匿名的基础上至少存在p个满足d-相异的敏感属性值来阻止相似性攻击。同时考虑到数据的可用性,模型采用基于距离的度量方法划分等价类以减少信息损失。实验结果表明,提出的(p,k,d)-匿名模型相对于p-Sensitive k-匿名模型不仅可以降低敏感属性泄露的概率,更能有效地保护个体隐私,还可以提高数据可用性。     

基于社会网络的(a,k)-匿名方法

随着网络技术的快速发展,大量在线社会网络的建立和使用,越来越多的人参加到社会网络中分享和交流信息,而在这种交互过程中,会产生大量的数据.这些数据中有些是用户个人生活领域中不愿意别人知道的事情,可以认为它们是用户的隐私.社会网络数据发布的隐私保护成为新兴的研究课题.本文提出了应用于社会网络的(a,k)-匿名方法,采用基于聚类的方法,对节点的属性及节点之间的关系进行保护.每个聚类中的节点数至少为k个,并且聚类中任一敏感属性值相关的节点的百分比不高于a.理论分析和实验结果表明,基于社会网络的(a,k)-匿名方法能在信息损失尽可能小的情况下有效地保护隐私.     

基于社会网络的(α,k)-匿名方法

随着网络技术的快速发展,大量在线社会网络的建立和使用,越来越多的人参加到社会网络中分享和交流信息,而在这种交互过程中,会产生大量的数据。这些数据中有些是用户个人生活领域中不愿意别人知道的事情,可以认为它们是用户的隐私。社会网络数据发布的隐私保护成为新兴的研究课题。本文提出了应用于社会网络的(α,k)-匿名方法,采用基于聚类的方法,对节点的属性及节点之间的关系进行保护。每个聚类中的节点数至少为k个,并且聚类中任一敏感属性值相关的节点的百分比不高于α。理论分析和实验结果表明,基于社会网络的(α,k)-匿名方法能在信息损失尽可能小的情况下有效地保护隐私。     

Diagnosability of optical multi-mesh hypercube networks under the comparison diagnosis model

Diagnosability of a multiprocessor system is one important study topic in the parallel processing area. As a family of promising optical interconnection topologies for massively parallel computers, the optical multi-mesh hypercube (OMMH) networks integrate positive features of both hypercube and mesh topologies and circumvent the lack of scalability of hypercubes and the large diameter of meshes. This paper studies an (l, m, n)-OMMH network and, proves that its diagnosability under the comparison diagnosis model is n+4 for l≥5, m≥5, n≥3.     

Adaptive diagnosis for torus systems under the comparison model

System level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Adaptive diagnosis, proposed by Nakajima, is one of many practical approach system level diagnostic schemes. As far as we know, the adaptive approach under the MM model has only been discussed in relation to a completely connected system. In this paper, we consider the problem of adaptive fault diagnosis for systems modelled by a cycle and a torus under the MM model. For cycles, we give some useful properties for identifying faulty vertices, show the minimum number of test rounds and provide some efficient test assignments. We also present two adaptive diagnosis algorithms for tori and show the minimum number of tests for these algorithms. Moreover, the two algorithms take linear time both for overall testing and syndrome decoding.     

基于FTA和比较模型的网络故障诊断算法

针对网络故障特点,将MM*模型和FTA方法引入网络故障诊断建模中,设计了一种用FTA方法进行网络故障的系统分析与诊断,并定量求解出所有故障可能的最小割集,然后用MM*模型从最小割集中选取测试点对进行单点故障检测与定位的网络故障诊断算法。实验结果表明,该算法有效提高了网络故障诊断的效率和准确率,具有较好的实用性。     

用于实现(k,e)-匿名模型的MDAV算法

MDAV算法是一种高效的微聚集算法,但它未考虑等价类中敏感属性多样性问题,生成的匿名表不能抵制同质性攻击和背景知识攻击。针对该问题,提出一种能够实现(k,e)-匿名模型的MDAV算法,简称(k,e)-MDAV算法。该算法将距离类中心最近的至少k个不同敏感值的元组聚为一类,并要求每个类内敏感属性值最大差异至少为e。实验结果表明,该算法能够生成满足(k,e)-匿名模型的匿名表。     

社会网络子集(θ, k)-匿名方法

针对目前社会网络邻域隐私保护相关研究并没有考虑对子集的保护,并且邻域子集中的特定属性分布情况也会造成个体隐私泄露这一问题,提出了一种新的(θ, k)-匿名模型。该模型移除社会网络中需要被保护的节点邻域子集标签后,基于k-同构思想,利用邻域组件编码技术和节点精炼方法处理候选集中的节点及其邻域子集信息,完成同构操作,其中考虑特定敏感属性分布问题。最终,该模型满足邻域子集中的每个节点都存在至少k-1个节点与其邻域同构,同时要求每个节点的属性分布在邻域子集内和在整个子集的差值不大于θ。实验结果表明,(θ, k)-匿名模型能够降低匿名成本并且最大化数据效用。     

Matching preclusion for the (n,k)-bubble-sort graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the (n, k)-bubble-sort graphs and classify all the optimal solutions.     

A sufficient condition for a graph to be an (a,b, k)-critical graph

Let G be a graph, and let a, b, k be integers with 0≤a≤b, k≥0. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a≤d _F (x)≤b for each x∈V(G). Then a graph G is called an (a, b, k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a, b]-factor. In this article, a sufficient condition is given, which is a neighborhood condition for a graph G to be an (a, b, k)-critical graph.     

Upper bounds on the size of LR(k) parsers

It is shown that in many cases the trivial upper bound 2^{|G|k + 1} on the number of states of an LR(k) parser for a grammar G is too conservative. In particular, if G is not right-recursive, the canonical LR(k) parser for G has at most |G^k|G|·2^|G| states. Examples of grammars with large LR(k) parsers are given.