Embedding and reconfiguration of spanning trees in faultyhypercubes

The problem of tolerating faulty nodes in hypercubes has been studied by many researchers either by using spares or by reconfiguration. Algorithms for tolerating faulty nodes and links in hypercubes are presented. The algorithms are based on using general spanning trees (GST), complete unbalanced spanning trees (CUST), and balanced spanning trees (BST) for reconfiguring the hypercube to avoid faulty nodes and links. The algorithms contain two phases: the first phase involves the construction of the spanning tree and the second one is for reconfiguring the hypercube should a faulty node be detected. The reconfiguration process consists of two basic steps. First, the faulty node is disconnected from the spanning tree. Then, a new spanning tree is constructed by reconnecting the children of the faulty node to the spanning tree. One hundred percent single fault correction (avoidance) and almost 100 percent fault correction (avoidance) of double and triple faults are achieved by the proposed algorithms for hypercubes having a dimension of n⩾6. Simulation results for the algorithm under more than three faults also are presented. For any k faulty nodes (1⩽k⩽2ⁿ-1), the reconfiguration algorithm may be applied k times to avoid these k faulty nodes as long as no combination of any two of the faults results in a blocking situation. The proposed reconfiguration algorithms tolerate all possible single-link faults. The reconfiguration algorithms are extended to tolerate (k⩽n-1) multiple faults, causing blocking situation, with a backtracking     

Deterministic Rendezvous in Graphs

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n²) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.     

Adaptive Fault-Tolerant Multicast in Hypercube Multicomputers

Fault-tolerant message routing mechanism is a key to the performance of reliable multicomputers. Multicast refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. This paper presents two types of partially adaptive fault tolerant multicast algorithms. The Type A algorithm can deliver messages to all destinations through shortest paths if each fault-free node has at most one faulty neighbor. The Type B algorithm can deliver messages to all destinations if the total number of faulty links and faulty nodes is less than the dimension of the hypercube. The proposed algorithms have the following important features: they are distributed, they only require local information to determine the paths, and they need very little additional message overhead. The performance of the algorithms, measured by the traffic created by the communication, is very close to that in fault-free hypercubes.     

A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

All-to-all broadcast and matrix multiplication in faulty SIMDhypercubes

In this paper, we develop algorithms in order of efficiency for all-to-all broadcast problem in an N=2ⁿ-node n-dimensional faulty SIMD hypercube, Q_n, with up to n-1 node faults. The algorithms use a property of a certain ordering of dimensions. Our analysis includes startup time (α) and transfer time (β). We have established the lower bound for such an algorithm to be nα+(2N-3)Lβ in a faulty hypercube with at most n-1 faults (each node has a value of L bytes). Our best algorithm requires 2nα+2NLβ and is near-optimal. We develop an optimal algorithm for matrix multiplication in a faulty hypercube using all-to-all broadcast and compare the efficiency of all-to-all broadcast approach with broadcast approach and global sum approach for matrix multiplication. The algorithms are congestion-free and applicable in the context of available hypercube machines     

Embedding and reconfiguration of binary trees in faulty hypercubes

We consider the problem of embedding and reconfiguring binary tree structures in faulty hypercubes. We assume that the number of faulty nodes is at most (n-2), where n is the number of dimensions of the hypercube; we further assume that the location of faulty nodes are known. Our embedding techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains at most one faulty node. Using this approach, two distributed schemes are provided for embedding and reconfiguration in faulty hypercubes. We extend the free dimension concept to degree of occupancy and use this to develop a distributed scheme for reconfiguration of binary tree in faulty hypercubes with up to [3n/2] node faults     

Simulation of Complete Binary Tree Structures in a Faulty Flexible Hypercube

The Flexible Hypercube is a generalization of binary hypercube networks in that the number of nodes can be arbitrary in contrast to a strict power of 2. Restated, the Flexible Hypercube retains the connectivity and diameter properties of the corresponding hypercube. Although the embedding of complete binary trees in faulty hypercubes has received considerable attention, to our knowledge, no paper has demonstrated how to embed a complete binary tree in a faulty Flexible Hypercube. Therefore, this investigation presents a novel algorithm to facilitate the embedding job when the Flexible Hypercube contains faulty nodes. Of particular concern are the network structures of the Flexible Hypercube that balance the load before as well as after faults start to degrade the performance of the Flexible Hypercube. Furthermore, to obtain the replaceable node of the faulty node, 2-expansion is permitted such that up to (n – 2) faults can be tolerated with congestion 1, dilation 4 and load 1. That is, (n – 1) is the dimension of a Flexible Hypercube. Results presented herein demonstrate that embedding methods are optimized.     

An O(log n) algorithm for parallel update of minimum spanning trees

Parallel algorithms are presented for updating a minimum spanning tree when the cost of an edge changes or when a new node is inserted in the underlying graph. Our model of computation is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper for updating a minimum spanning tree require O(log n) time and O(n²) processors. These algorithms are efficient when compared to previously known algorithms for initial construction of a minimum spanning tree that require O(log²n) time and use O(n²) processors. The two main contributions of this paper are: (i) usage of an inverted tree for updating minimum spanning trees, and (ii) discovery of an interesting property of minimum spanning trees that we exploit to develop a novel algorithm for vertex insertion update.     

Optimal Broadcasting in Faulty Trees

We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an “off-line” algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault tolerance of broadcasting schemes in trees. We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn²+n² log n), where n is the size of the tree. We also give an algorithm to find a “universally fault-tolerant” broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, for all k simultaneously.     

An efficient fault-tolerant multicast routing protocol withcore-based tree techniques

In this paper, we design and analyze an efficient fault-tolerant multicast routing protocol. Reliable multicast communication is critical for the success of many Internet applications. Multicast routing protocols with core-based tree techniques (CBT) have been widely used because of their scalability and simplicity. We enhance the CBT protocol with fault tolerance capability and improve its efficiency and effectiveness. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our approach is in contrast to other approaches that often require relatively large tree reformation when faults occur. These global methods are usually costly and complicated in their attempt to achieve theoretically optimal performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost     

广域网中的快速组播树生成算法

在组播树生成算法中,MPH(minimum path cost heuristic)的费用性能几乎是最好的,但它的计算时间相对较长,提出了两种新的组播树生成算法：TNS-MPH(tree-mode started minimum-cost path heuristic)和NTDS-MPH(non-tree-destination started minimum-cost path heuristic).同时提出了一种使节点平均度非常精确的随机网络产生模型。新算法的仿真结果表明,新算法用较少的费用性能恶化来换取更快的计算速度。新算法比SCTF（selective closest terminal first）算法有更好的扩展性。     

基于增量最短路径优先算法的高效LFA实现方法

针对已有LFA实现方式计算开销大和部署难度高的问题,提出了一种基于增量最短路径优先算法的LFA实现方法（LFA implementation method based on incremental shortest path first algorithm,ERPISPF）。首先将快速实现LFA的问题转换为如何在以计算节点为根的最短路径树上高效地计算其所有邻居节点到网络其余所有节点的最小代价问题;然后提出了计算该代价的定理并且证明了它的正确性,最后从理论上分析了算法的时间复杂度。仿真结果表明,ERPISPF不仅计算开销小,并且与LFC的故障保护率是相同的。     

基于故障敏感图的回卷算法和故障恢复

扩充的面向图结构的分布式程序设计模型(extended graph-oriented model,简称ExGOM)提供了一个支持动态配置的系统框架.系统的动态配置包括系统运行时的伸缩、运行时的升级以及出现故障后的重配置.故障后的重配置所涉及的问题之一是如何恢复系统原状态,该文着重就此问题进行了讨论,给出了基于故障敏感图的异步检查点回卷算法和故障恢复策略.该算法和策略考虑了在暂时性主机故障中单个主机上有多个故障进程的情况.与其他异步回卷及故障恢复算法相比,该算法将故障区域局部化,仅对故障敏感节点进行回卷,从而有效地降低了系统开销.     

Depth-First Branch-and-Bound versus Depth-Bounded IDA: New Results

In a real-time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed-up cost. The standard algorithm for such a search is Depth-First Branch-and-Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning . This article shows that a depth-bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA , is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty-four, and Ninety-nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.     

一种基于旁听的机会网络路由算法

针对基于议价博弈的概率路由算法存在消息传送成功率提升偏慢、开销大、节点无序情况下竞争信道引起碰撞以及节点在多邻居状态下存在冗余交互的问题,提出一种基于旁听的机会网络路由算法—ORON。ORON算法通过旁听邻居节点信息,设计博弈策略使激励相容,节点对邻居与自身的交易状态进行分析,选择最佳策略,使得网络性能得到提升。仿真验证了ORON算法设计的有效性,结果表明：与基于议价博弈的现有路由算法GSCP相比,ORON算法的吞吐量和消息传送成功率至少提高了6.72%,而控制开销和平均端到端消息时延则分别降低了20%和3.55%以上。     

A QoS Multicast Routing Algorithm Working with Imprecise State Information

In large networks, maintaining precise global network state information is almost impossible. Many factors, including non-negligible propagation delay, infiequent link state update due to overhead concerns, link state update policy, and hierarchical topology aggregation, have impacts on the precision of the network state information. The existing QoS multicast routing algorithms do not provide satisfactory performance with imprecise state information. In this paper, we propose a distributed QoS multicast routing scheme based on traffic lights, called QMRI algorithm, which can probe multiple feasible tree branches, and select the optimal or near-optimal branch through the UR or TL mode for constructing a multicast tree with QoS guarantees if it exists. The proposed algorithm considers not only the QoS requirements but also the cost optimality of the multicast tree. Extensive simulations show that our algorithm achieves high call-admission ratio and low-cost multicast trees with modest message overhead. The algorithm can tolerate high degree of state information imprecision.     

Efficient algorithms to create and maintain balanced and threaded binary search trees

The algorithm proposed by Chang and lyengar to perfectly balance binary search trees has been modified to not only balance but also thread binary search trees. Threads are constructed in the same sequence as normal pointers during the balancing process. No extra workspace is necessary, and the running time is also linear for the modified algorithm. Such produced tree structure has minimal average path length for fast information retrieval, and threads to facilitate more flexible and efficient traversing schemes. Maintenance and manipulation of the data structure are discussed and relevant algorithms given.     

Achieving Robustness and Minimizing Overhead in Parallel Algorithms Through Overlapped Communication/Computation

One of the major goals in the design of parallel processing machines and algorithms is to achieve robustness and reduce the effects of the overhead introduced when a given problem is parallelized or a fault occurs. A key contributor to overhead is communication time, in particular when a node is faulty and another node is substuiting for its operation. Many architectures try to reduce this overhead by minimizing the actual time for a communication to occur, including latency and bandwidth figures. Another approach is to hide communication by overlapping it with computation assuming that the computation is the most prominent factor. This paper presents the mechanisms provided in the Proteus parallel computer and its effective use of communication hiding through overlapping communication/computation techniques with and without the presence of a fault. These techniques are easily extended for use in compiler support of parallel programming. We also address the complexity (or rather simplicity) in achieving complete exchange on the Proteus Machine.     

Reconfiguration models and algorithms for stateful interactiveprocesses

We present new results in the area of reconfiguration of stateful interactive processes in the presence of faults. More precisely, we consider a set of servers/processes that have the same functionality, i.e., are able to perform the same tasks and provide the same set of services to their clients. In the case when several of them turn out to be faulty, we want to reconfigure the system so that the clients of the faulty servers/processes are served by some other, fault-free, servers of the system in a way that is transparent to all the system clients. We propose a novel method for reconfiguring in the presence of faults: compensation paths. Compensation paths are an efficient way of shifting spare resources from where they are available to where they are needed. We also present optimal and suboptimal simple reconfiguration algorithms of low polynomial time complexity O(nmlog(n²/m)) for the optimal and O(m) for the suboptimal algorithms, where n is the number of processes and m is the number of primary-backup relationships. The optimal algorithms compute the way to reconfigure the system whenever the reconfiguration is possible. The suboptimal algorithms may sometimes fail to reconfigure the system, although reconfiguration would be possible by using the optimal centralized algorithms. However, suboptimal algorithms have other competitive advantages over the centralized optimal algorithms with regard to time complexity and communication overhead     

Extended impossibility results for asynchronous complete networks

It is proved that a large class of distributed tasks cannot be solved in the presence of faulty processors. This class contains tasks whose unsolvability in the presence of faults is known (the consensus task and its variants. cf. Fischer et al. (1985)) as well as some new tasks (e.g., constructing a spanning tree). In particular, we introduce the notion of the decision graph of a task, and show that every problem whose decision graph is disconnected cannot be solved in the presence of one faulty processor, by reducing the unsolvability of this problem to the unsolvability of the consensus problem. The notion of unsolvability used here is very weak: We say that a protocol solves a given problem in spite of one faulty processor if in any execution it satisfies (i) all nonfaulty processors eventually halt, and (ii) if no processor is faulty, it solves the problem. Hence, the unsolvability of a problem in this model implies its unsolvability in other models appearing in the literature.