Assigning labels in an unknown anonymous network with a leader

We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms. Received: July 2000 / Accepted: February 2001     

A New Measure in System-Level Diagnosis of Hypercubes

In this paper a new measure in system-level diagnosis for hypercube multicomputer systems is defined. One-step diagnosis of hypercubes which involves only one testing phase during which processors test each other is discussed. Two different kinds of one-step diagnosis are considered: one called one-step diagnosis and studied earlier by other researchers and the other called one-step diagnosis with the forbidden faulty sets (one-step-FFS) and studied first here in the context of application to hypercubes. One of the two main results presented here is a proof that the degree of diagnosability of the n-dimensional hypercube (for short, n-cube), where n ≥ 4 increases from n to 2n − 2 as the diagnosis strategy changes from the one-step strategy to the one-step-FFS strategy. The other main result is the proof that if the fault bound; i.e., the upper bound on the possible number of faulty processors, is kept to the same number n in both cases of one-step and one-step-FFS diagnosis, then the one-step-FFS strategy requires [n/2] + 1 testing links per processor, whereas the one-step strategy requires n testing links per processor. An algorithm for selecting ([n/2] + 1)n/2 (2-way) links in an n-cube for use as testing links is presented.     

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.     

Reliable Communication on Cube-Based Multicomputers

We consider a distributed unicasting algorithm for hypercubes with faulty nodes(including disconnected hypercubes)using the safety level concept.The safety level of ach node in an n-dimensional hypercube in an approximated measure of the number and distribution of faulty nodes in the neighborhood and it can be easily calculated through n-1 rounds of information exchange among neighboring nodes.Optimal unicasting between two nodes is guaranteed if the safety level of the source node is no less than the Hamming distance between the source and the destination.The feasibility of an optimal or suboptimal unicasting can be easily determined at the source node by comparing its safety level,together with its neighbors‘ safety levels,with the Hamming distance between the source and the destination.The proposed scheme is also the first attempt to address the unicasting problem in discronnected hypercubes.The safety level concept is also extended to be used in hypercubes with both faulty nodes and links and in generalized hypercubes.     

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     

Efficient algorithms for system diagnosis with both processor andcomparator faults

For the comparison-based self-diagnosis of multiprocessor systems, an extended model that considers both processor and comparator faults is presented. It is shown that in this model the system diagnosability is t⩽Zδ/2Z, where δ is the minimum vertex degree of the system graph. However, if the number of faulty comparators is assumed not to exceed the number of faulty processors, the diagnosability of the model reaches t⩽δ. An optimal O(|E|) algorithm, where E is the set of comparators, is given for identifying all faulty processors and comparators, provided that the total number of faulty components does not exceed the system diagnosability, and an O(|E|)² algorithm for the case t⩽δ is also presented. These efficient algorithms determine the faulty processors by calculating each processor's weight, which is mainly defined by the number of adjacent relative tests stating `agreement'. After sorting the processors according to their weights, the algorithms determine all faulty components by separating the sorted processor list     

Torus orientation

A torus is oriented if the processes have assigned their communication links North-East-South-West labels in a globally consistent manner. This paper presents an orientation protocol that is self-stabilizing, i.e., resilient to corruption of data stored in working memories and communication links. The protocol is randomized, uses constant memory space, and orients tori where the processes do not know the network size and have no identifiers; probabilistic stabilization is proved under a restricted form of asynchrony and composite atomicity. Received: November 1998 / Accepted: March 2001     

Distributed computation for a hypercube network of sensor-drivenprocessors with communication delays including setup time

In this paper, the problem of optimal distribution of measurement data to be processed in minimal time on a hypercube network of sensor driven processors is considered. An analytical model is developed for solving the problem efficiently. Unlike the previous models, this model considers: 1) explicitly the setup time which constrains exploiting all the available processors; 2) simultaneous use of links to expedite the communication; 3) partial solution combining time to encompass wider class of related problems. By deriving a lower bound on the amount of data to be received by a processor for efficient distribution, a new technique called fractal hypercube is introduced here to get the optimal solution with fewer processors, An optimal iterative method for hypercubes and a near-optimal recursive method with a refinement are presented for the same with the analysis. The effect of varying the originating processor and the choice of fractal hypercube are discussed with an effective technique called processor isomorphism. This study reveals that always the fractal hypercubes outperform the other two methods, the optimal iterative method for hypercubes and the near-optimal method     

Summation and routing on a partitioned optical passive stars network with large group size

In a partitioned optical passive stars (POPS) network, n=dg processors are divided into g groups of d processors each, and such a POPS network is denoted by POPS(d,g). There is an optical passive star (OPS) coupler between every pair of groups. Hence, a POPS(d,g) requires g/sup 2/ couplers. It is likely that, in a practical system, the number of couplers will be less than the number of processors, i.e., d>/spl radic/n>g and the number of groups will be smaller than the number of processors in a group. Hence, it is important to design fast algorithms for basic operations on such POPS networks with large group size. We present fast algorithms for data sum, prefix sum, and permutation routing on a POPS(d,g) such that d>/spl radic/n>g. Our data sum and prefix sum algorithms improve upon the best known algorithms for these problems designed by Sahni (2000). Permutation routing can be solved on a POPS network by simulating a hypercube sorting algorithm. Our algorithm for permutation routing is more efficient compared to this simulated hypercube sorting algorithm.     

Optimal cube-connected cube multicomputers

Many CFD (computational fluid dynamics) and other scientific applications can be partitioned into subproblems. However, in general, the partitioned subproblems are very large. They demand high-performance computing power themselves, and their solutions have to be combined at each time step. In this paper, the cube-connect cube (CCCube) architecture is studied. The CCCube architecture is an extended hypercube structure with each node represented as a cube. It requires fewer physical links between nodes than the hypercube, and provides the same communication support as the hypercube does on many applications. The reduced physical links can be used to enhance the bandwidth of the remanding links and, therefore, enhance the overall performance. The concept and the method to obtain optimal CCCubes, which are the CCCubes with a minimum number of links under a given total number of nodes, are proposed. The superiority of optimal CCCubes over standard hypercubes has also been shown in terms of the link usage in the embedding of a binomial tree. A useful computation structure based on a semi-binomial tree for divide-and-conquer type of parallel algorithms has been identified. We have shown that this structure can be implemented in optimal CCCubes without performance degradation compared with regular hypercubes. The result presented in this paper should provide a useful approach to design of scientific parallel computers.     

超立方体并行计算机的一个新型故障诊断算法

提出了超立方体并行计算机的一个新型系统级故障诊断算法.与现有诊断算法相比,该算法能够在系统中存在较多故障处理器的情况下,正确定位全部故障处理器（代价是至多误诊断三个无故障处理器）.另外,该算法的时间复杂度与最好的现有算法相当.     

基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.     

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     

The scalability of FFT on parallel computers

The authors present the scalability analysis of a parallel fast Fourier transform (FFT) algorithm on mesh and hypercube connected multicomputers using the isoefficiency metric. The isoefficiency function of an algorithm architecture combination is defined as the rate at which the problem size should grow with the number of processors to maintain a fixed efficiency. It is shown that it is more cost-effective to implement the FFT algorithm on a hypercube rather than a mesh despite the fact that large scale meshes are cheaper to construct than large hypercubes. Although the scope of this work is limited to the Cooley-Tukey FFT algorithm on a few classes of architectures, the methodology can be used to study the performance of various FFT algorithms on a variety of architectures such as SIMD hypercube and mesh architectures and shared memory architecture     

Intermediate-level feature extraction in novel parallel environments

Abstract. Parallel systems provide an approach to robust computing. The motivation for this work arises from using modern parallel environments in intermediate-level feature extraction. This study presents parallel algorithms for the Hough transform (HT) and the randomized Hough transform (RHT). The algorithms are analyzed in two parallel environments: multiprocessor computers and workstation networks. The results suggest that both environments are suitable for the parallelization of HT. Because scalability of the parallel RHT is weaker than with HT, only the multiprocessor environment is suitable. The limited scalability forces us to use adaptive techniques to obtain good results regardless of the number of processors. Despite the fact that the speedups with HT are greater than with RHT, in terms of total computation time, the new parallel RHT algorithm outperforms the parallel HT. Received: 8 December 2001 / Accepted: 5 June 2002 Correspondence to: V. Kyrki     

Dimension-exchange-based global load balancing on injured hypercubes

A study is made of a global load balancing scheme on hypercubes with faulty links based on dimension exchange, where each node exchanges workloads with its neighbors along a selected dimension in such a way that their workloads become equal. A global load balancing algorithm that can tolerate $n-1$ faulty links is first presented. It is then extended to connected hypercubes with up to $2n-3$ faulty links. Comparisons between the proposed scheme with the regular dimension-exchange-based scheme are also presented. Simulation results show that the average number of message exchanges required in the proposed scheme is very close to the one obtained from the regular dimension-exchange-based scheme. © 1997 by John Wiley & Sons, Ltd.     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

Hierarchical Hypercube Networks (HHN) for Massively Parallel Computers

The hypercube is one of the most widely used topologies because it provides small diameter and embedding of various interconnection networks. For very large systems, however, the number of links needed with the hypercube may become prohibitively large. In this paper, we propose a hierarchical interconnection network based on hypercubes called hierarchical hypercube network (HHN) for massively parallel computers. The HHN has a smaller number of links than the comparable hypercube and in particular, when we construct networks with 2^Knodes, the node degree of HHN with the minimum node degree isO([formula]) while that of hypercube isO(K). Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in the hypercube.     

Computing Hough transforms on hypercube multicomputers

Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputer are developed. Our algorithms can compute p angles of the Hough transform of an N × N image, p N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ²) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.This research was supported by the National Science Foundation under grants DCR84-20935 and 86-17374. All correspondence should be mailed to Sanjay Ranka.     

On the Dynamic Initialization of Parallel Computers

The incremental and dynamic construction of interconnection networks from smaller components often leaves the fundamental problem of assigning addresses to processors to be contended with at power-up time. The problem is fundamental, for virtually all parallel algorithms known to the authors assume that the processors know their global coordinates within the newly created entity. We refer to this problem as the initialization problem. Rather surprisingly, the initialization problem has not received much attention in the literature. Our main contribution is to present parallel algorithms for the initialization problem on a number of network topologies, including complete binary trees, meshes of trees, pyramids, linear arrays, rings, meshes, tori, higher dimensional meshes and tori, hypercubes, butterflies, linear arrays with a global bus, rings with a global bus and meshes with multiple broadcasting, under various assumptions about edge labels, leader existence, and a priori knowledge of the number of nodes in the network. With two exceptions, the proposed algorithms are optimal.