分布式系统中失败结点的判定与优先列表的重构新方法

实时分布式系统中，如果结点n自从上一次收到结点i的广播信息后经过超时值时没有再收到结点i的广播信息，就认为结点i失败。这时需要调整各正常结点的优先列表，以保证每个结点被一个也只能是一个结点选择为自己的第后个优先结点，以减少任务的失败率。本文提出了一种确定最佳超时值以及检测结点失败并且调整结点的优先列表以处理结点失败的新方法。     

基于结点语义关系的信息抽取技术

提出了一种利用结点语义关系分析的新方法来优化自然语言信息抽取,以结点语义关系树和结点语义关系列表作为优先判断依据,在没有信息损失的前提下实现高效率的语义信息抽取。     

基于子网的三维Mesh网络容错广播路由算法

在并行计算机系统中,广播通信是极为重要的通信模式之一。该文基于k-Mesh子网(子立方体)连通的概念提出一个基于局部信息和分布式的三维Mesh网络容错广播路由算法。该算法利用邻结点的状态信息,动态地构建以单个k-Mesh子网为结点的广播树,该广播树能容忍相当多的结点出错。模拟结果表明广播路由算法的广播时间步接近最优的。该算法只要求结点知道它的邻结点的状态,而无需知道整个网络状态信息,也就是说,这些算法是基于局部信息的,因而具有很好的实际意义。     

使用DOM技术维护服务器列表

一、前言 由于在实际工作中需要维护数十个中间件服务器,必须创建一个合适的数据存储方案对这些服务器结点的配置信息加以描述并保存,以使其它应用程序能够方便地对服务器结点信息进行访问。经深思熟虑之后,决定使用XML文件来存储服务器列表信息,理由如下：     

关于最小广播图研究

广播是网络上信息的传播过程。在这个过程中一个结点将信息传给所有其他的结点。本文确定Ｂ（１９）的值。另外还给出Ｂ（２－＾ｋ－ｊ），ｊ＝１，２，３，４的下界，并确定Ｂ（２＾５－１）和Ｂ（２＾５－２）的值。     

智能表广播模型

紧密耦合系统中的广播模型仍是现代网络系统中讨论的重点之一,现今经常使用的广播模型的如传统广播模型及全局表模型都由于没有充分发挥软件的功能而具有较大的局限性。对此,作者提出了一种新的智能表广播模型ＩＬＢＭ。在该模型中每一结点都被赋予一个邻结点表与一个结点算法,由结点算法来灵活决定结点在广播过程中对各连接的转发顺序,从而以软件表态形式上的一致实现运行效果的不一致,进而统一表;     

基于异步自动机的网格广度优先搜索算法

在网格中，经常需要以某个结点源点，构造一棵广度优先生成树来进行广播和聚合通信，现有的广度优先搜索算法都是基于图论的同步式算法，而在异步式的网格系统中不能采用这种算法，在开发国家高性能计算环境的过程中，以异步自动机为基础建立了网格理论模型，在这个模型的基础上实现了一种异步式网格广度优先搜索算法－－GridBFS算法，还证明了，GridBFS算法最终将产生一棵广度优先生成树，并且能够检测到算法的终止。     

基于XML和关系数据库的树形结构的研究

本文介绍了一种树型结构的存储、显示和维护方法。以二叉链表的数据结构将树的信息存储在数据库中，服务器端将数据库中树的信息转化成XML，客户端将其加载到浏览器的（DOM）实例中，并采用深度优先搜索算法对该实例中的结点进行递归遍历，生成浏览器端树的HTML代码，它是一个与上述XML文档逻辑相同的树型结构。同时在各结点上设置JS事件，可以对该树进行维护，生成针对结点维护的XML，服务器解析该XML并生成一系列SQL提交到数据库中。     

基于P2P的数字证书撤销列表更新方案及性能分析

针对数字证书撤销列表更新中大量结点同时请求数据造成的系统性能瓶颈,本文提出了基于P2P的数字证书撤销列表更新方案,利用客户结点的资源改善证书撤销列表的更新性能;以数字校园应用为背景建立了分析模型,对所提方案进行了分析比较。     

基于扩展前缀编码的左孩子右兄弟结构连接算法

为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好.     

基于IMS移动终端的即时通信联系人列表管理器

本文主要介绍基于IMS移动终端的即时通信联系人管理器,该管理器主要由XML搜索器、XML解析器、XML管理模块、XCAP通信模块构成。分析联系人列表中联系人的XML片段的定长特性,设计了XML搜索器,实现了节点的快速查找。在XML管理器模块中,以节点路径和消息片段的方式提交联系人修改,减少XML消息传输的字节数,从而提高了消息的传输速率。     

Quasi-random rumor spreading: Reducing randomness can be costly

We give a time-randomness tradeoff for the quasi-random rumor spreading protocol proposed by Doerr, Friedrich and Sauerwald [SODA 2008] on complete graphs. In this protocol, the goal is to spread a piece of information originating from one vertex throughout the network. Each vertex is assumed to have a (cyclic) list of its neighbors. Once a vertex is informed by one of its neighbors, it chooses a position in its list uniformly at random and then informs its neighbors starting from that position and proceeding in order of the list. Angelopoulos, Doerr, Huber and Panagiotou [Electron. J. Combin. 2009] showed that after rounds, the rumor will have been broadcasted to all nodes with probability 1−o(1).We study the broadcast time when the amount of randomness available at each node is reduced in natural way. In particular, we prove that if each node can only make its initial random selection from every ?-th node on its list, then there exists lists such that steps are needed to inform every vertex with probability at least . This shows that a further reduction of the amount of randomness used in a simple quasi-random protocol comes at a loss of efficiency.     

Handling large-scale node failures in mobile sensor/robot networks

In Wireless Sensor Networks (WSNs), maintaining connectivity with the sink node is a crucial issue to collect data from sensors without any interruption. While sensors are typically deployed in abundance to tolerate possible node failures, a large number of simultaneous node failures within the same region may result in partitioning the network which may disrupt the network operation significantly. Given that WSNs are deployed in inhospitable environments, such node failures are very likely due to storms, fires, floods, etc. The self-recovery of the network from these large-scale node failures is challenging since the nodes will not have any information about the location and span of the damage. In this paper, we first present a distributed partition detection algorithm which quickly makes the sensors aware of the partitioning in the network. This process is led by the sensors whose upstream nodes fail due to damages. Upon partition detection, sensors federate the partitions and restore data communication by utilizing the former routing information stored at each sensor to the sink node and exploiting sensor mobility. Specifically, the locations of failed sensors on former routes are used to assess the span of the damage and some of the sensors are relocated to such locations to re-establish the routes with the sink node. Relocation on such former routes is performed in such a way that the movement overhead on sensors is also minimized. Our proposed approach solely depends on the local information to ensure autonomicity, timeliness and scalability. The effectiveness of the proposed federation approach is validated through realistic simulation experiments and has been shown to provide the mentioned features.     

Computing the fault tolerance of multi-agent deployment

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment—these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities—these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.     

Diagnosis of repeated failures for discrete event systems with linear-time temporal-logic specifications

In our earlier work, we introduced a state-based approach for the diagnosis of repeatedly occurring failures in discrete event systems (DESs). Since temporal logic provides a simpler way of specifying system properties; in this paper, a temporal-logic-based approach for diagnosing the occurrence of a repeated number of failures is developed. Linear-time temporal-logic (LTL) formulae are used to represent the specifications of DESs. Notions of prediagnosability for failures and diagnosability for repeated failures are introduced in the setting of temporal logic. A polynomial algorithm for the test of prediagnosability for failures is provided. The diagnosis problem for repeated failures in the temporal-logic setting is reduced to one in a state-based setting, and so the prior results of a state-based repeated failure diagnosis can be applied. Finally, a simple example is given for illustration. Note to Practitioners-Certain failures in a system are repeatable, such as routing errors in a manufacturing system. A theory for the diagnosis of such failures was presented in an earlier work of Jiang et al. The present paper uses temporal logic to specify such failures. It turns out that repeatable failures can be specified as violations of invariant properties (i.e., properties that must always hold). Given an invariant property that the system must always satisfy, an algorithm is presented to refine the system model and label those states of the refined system where the property is violated. The problem of repeated diagnosis then requires determining, within a bounded delay, each time a "failure-state" is visited. For this analysis, the existing theory developed by Jiang et al. is used.     

Modeling and evaluating the time overhead induced by BER in COMA multiprocessors

Designing multiprocessors based on distributed shared memory (DSM) architecture considerably increases their scalability. But as the number of nodes in a multiprocessor increases, the probability of encountering failures in one or more nodes of the system raises as a serious problem. Thus, every large-scale multiprocessor should be equipped with mechanisms that tolerate node failures. Backward error recovery (BER) is one of the most feasible strategies to build fault tolerant multiprocessors and it can be shown that among various DSM-based architectures, cache only memory architecture (COMA) is the most suitable for implementing BER. The main reason is the existence of built-in mechanisms for data replication in COMA memory system. BER is applicable to COMA multiprocessors with minor hardware redundancy, but it will obviously cause some other kinds of overheads. The most important overhead induced by BER is the time required to produce and store recovery data. This paper introduces an analytical model for predicting the amount of this time overhead and then verifies the correctness of the model through comparing the results predicted from this model with the previously published simulation results. Both the analytical model and simulation results show that the overhead is nearly independent of the number of nodes. The immediate result is that BER is a cost-effective strategy for tolerating node failures in large-scale COMA multiprocessors with large numbers of nodes.     

Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

This paper considers the problem of computing general commutative and associative aggregate functions (such as Sum) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question:

Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions?

This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.

     

Reliability Evaluation for an Information Network With Node Failure Under Cost Constraint

The quality of service is an important index to measure the performance of an information system. This paper constructs a stochastic-flow network to model the information system. In this network, each node and arc having a designated capacity will have different lower levels due to various partial and complete failures. The studied problem is to evaluate the possibility that a given amount of multicommodity can be sent through an information network under the cost constraint. Such a possibility, which is named the mission reliability, is an appropriate performance index to measure the quality level. The terminology "flow" represents the quantity of data transmitted via such a network, and "demand" represents the required data from clients. Based on the properties of minimal paths, a simple algorithm is first proposed to generate all lower boundary points for the demand; then, the mission reliability can be calculated in terms of such points. The lower boundary point for the demand is a minimal vector, which represents the capacity of each component (arc or node), such that the demand can be fulfilled. Extending the stochastic-flow network to the node failure case, another algorithm is proposed to calculate the mission reliability     

Dynamic SPT update for multiple link state decrements in network routing

Previous approaches to the dynamic updating of Shortest Path Trees (SPTs) have in the main focused on just one link state change. Not much work has been done on the problem of deriving a new SPT from an existing SPT for multiple link state decrements in a network that applies link-state routing protocols such as OSPF and IS-IS. This problem is complex because in the process of updating an SPT there are, firstly, no simple forms of node set to presumable contain all nodes to be updated and, secondly, multiple decrements can be accumulated to make the updating much harder. If we adopt the updating mechanisms engaged in one link state change for the case of multiple link state decrements, the result is node update redundancy, as a node changes several times before it reaches its final state in the new SPT. This paper proposes two dynamic algorithms (MaxR, MinD) for obviating unnecessary node updates by having part nodes updated in a branch on the SPT only after selecting a particular node from a built node list. The algorithm complexity analysis and simulation results show that MaxR and MinD require fewer node updates during dynamic update procedures than do other algorithms for updating SPT of multiple link state decrements.