Narrow Results

In this paper, we propose a mesh with a global bus as a multi-computer topology. This structure enhances the communication capability of the mesh and shows that the mesh with a global bus has more salient properties than the mesh, the hypercube, or other variants. These properties includes a small diameter, a relatively small degree, small average distance, suitability for broadcasting, small initial data distribution time, etc. We propose a dynamic load distribution algorithm to utilize the enhanced communication capability of the mesh with a global bus. Also, asynchronous bus control and arbitration logics are designed to support the proposed algorithm efficiently. It has been shown through simulation that the proposed dynamic load distribution is superior to the Receiver Initiated Diffusion method, previously known as the best to-date. The proposed algorithm shows better total task execution time and better processor utilization with a smaller number of task migrations.

We propose a general framework for broadcasting in ad hoc networks through self-pruning. The approach is based on selecting a small subset of hosts (also called nodes) to form a forward node set on carry out a broadcast process. Each node, upon receiving a broadcast packet, determines whether to forward the packet or not based on two neighborhood coverage conditions proposed in this paper. These coverage conditions depend on neighbor connectivity and history of visited nodes, and in general, resort to global network information. Using local information such as k-hop neighborhood information, the forward node set is selected through a distributed and local pruning process. The forward node set can be constructed and maintained through either a proactive process (i.e., "up-to-date") or a reactive process (i.e., "on-the-fly"). Several existing broadcast algorithms can be viewed as special cases of the coverage conditions with k-hop neighborhood information. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the coverage conditions, and self-pruning based on 2- or 3-hop neighborhood information is relatively more cost-effective.

This paper introduces Neighbor Aware Adaptive Power flooding, an optimized flooding mechanism used in mobile ad hoc networks (MANETS) that employs several mechanisms (neighbor coverage, power control, neighbor awareness and local optimization) to limit the broadcast storm problem, reduce duplicate packet reception and lower power consumption in both transmission and reception. Upon receiving an optimized broadcast, a relay determines a new set of possible relays (to continue the flood) based upon local neighbor information and the previous optimized broadcast. Additionally, neighboring relays only consider the shared neighbors they are closest to. A relay may perform local optimization (to reduce power consumption and isolate broadcasts) by substituting one high power broadcast with two or more low power broadcasts, thereby introducing additional hops, We show that compared to blind flooding and multipoint relaying, NAAP in a static environment greatly reduces the problems associated with the broadcast storm problem, duplicate packet reception and power consumption.

We construct and analyze a fast broadcasting algorithm working in the presence of Byzantine component faults. Such faults are particularly difficult to deal with, as faulty components may behave arbitrarily (even maliciously) as transmitters, by either blocking, rerouting, or altering transmitted messages in a way most detrimental to the broadcasting process. We assume that links and nodes of a communication network are subject to Byzantine failures, and that faults are distributed randomly and independently, with link failure probability p and node failure probability q, these parameters being constant and satisfying the inequality (1 - p)²(1 - q) > 1/2. A broadcasting algorithm, working in an n-node network, is called almost safe if the probability of its correctness is at least 1 - 1/n, for sufficiently large n. Thus the robustness of the algorithm grows with the size of the network. Our main result is the design and analysis of an almost safe broadcasting algorithm working in time O(log² n) and using O(n log n) messages in n-node networks. Under a stronger assumption on failure probability parameters, namely (1 - p)²(1 - q)² > 1/2, our algorithm can be modified to work in time O(log² n/ log log n), also using O(n log n) messages. The novelty of our algorithm is that it can cope with the most difficult type of faults, potentially affecting all components of the network (both its links and nodes), and that it is simultaneously robust and efficient.

We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.

We show that the edges of the modified Knödel graph can be grouped into dimensions which are similar to the dimensions of hypercubes. In particular, routing, broadcasting and gossiping, can be done easily in modified Knödel graphs using these dimensions.

The capability of fault tolerance is one of the advantages of multiprocessor systems. In this paper, we prove that the fault tolerance of an n-star graph is 2n-5 with restriction to the forbidden faulty set. And we propose an algorithm for examining the connectivity of an n-star graph when there exist at most 2n - 4 faults. The algorithm requires O(n²log n) time. Besides, we improve the fault-tolerant routing algorithm proposed by Bagherzadeh et al. by calculating the cycle structure of a permutation and the avoidance of routing message to a node without any nonfaulty neighbor. This calculation needs only constant time. And then, we propose an efficient fault-tolerant broadcasting algorithm. When there is no fault, our broadcasting algorithm remains optimal. The penalty is O(n) if there exists only one fault, and the penalty is O(n²) if there exist at most n - 2 faults.

Fast and efficient communication is one of the most important requirements in today's multicomputers. When reaching a larger scale of processors, the probability of faults in the network increases, hence communication must be robust and fault tolerant. The recently introduced family of folded Petersen networks, constructed by iteratively applying the cartesian product operation on the well-known Petersen graph, provides a regular, node– and edge-symmetric architecture with optimal connectivity (hence maximal fault-tolerance), and logarithmic diameter. Compared to the closest sized hypercube, the folded petersen network has a smaller diameter, lower node degree and higher packing density.

In this paper, we study fundamental communication primitives like single routing, permutation routing, one-to-all broadcasting, multinode-broadcasting (gossiping), personalized communications like scattering, and total exchange on the folded Petersen networks, considering two communication models, namely single link availability (SLA) and multiple link availability (MLA). We derive lower bounds for these problems and design optimal algorithms in terms of both time and the number of message transmissions. The results are based on the construction of minimal height spanning trees in the fault-free folded Petersen network. We further analyze these communication primitives in faulty networks, where processing nodes and transmission links cease working. This analysis is based on multiple arc-disjoint spanning trees, a construct also useful for analyzing other families of multicomputer networks.

We propose a constant node degree network topology, multitriangle, which is hierarchical, recursive, and expansive. First we introduce a corner cutting approach that generates a set of new network topologies (including multitriangles), followed by a formal definition of the multitriangle network and discussion of its properties. The salient features of this network are that it is a constant node degree network and it can be viewed as a hierarchical ring, a popular topology which has been adopted in several commercial systems. Algorithms for node-to-node routing, hierarchical ring routing, optimal ring routing, and broadcasting are presented. The multitriangle network is analyzed in terms of diameter, degree, average distance, and message density, and results are compared with other relevant networks.

The network properties of double and triple fixed step graphs are considered. We determine that the broadcast times of double and triple fixed step graphs of diameter D are equal to D+2 and D+3, respectively. Some results on the embeddings of grids into these graphs with dilation 1 and 2 are given. For a triple fixed step graph we give a method to calculate the routing between any two vertices of the graph. Furthermore, we show that the diameter of the surviving route graph remains two for any set F of faults for |F|=5, which is optimum.

We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+nlog n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.

We consider a broadcasting problem in the n-dimensional k-ary even torus in the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time step a number of links of the network can be faulty. Moreover the faults are dynamic. The problem is to determine the minimum broadcasting time if at most 2n - 1 faults are allowed in any step. In [4], it was shown that the broadcasting time is at most diameter+O(1), provided that k is limited by a polynomial of n. In our paper we drop this additional assumption and prove that the broadcasting can be always done in time diameter +2. The bound is the best possible.

Free-space optical interconnection is used to fashion a reconfigurable network. Since network reconfiguration is expensive compared to message transmission in such networks, latency hiding techniques can be used to increase the performance of collective communications operations. Berthome and Ferreira have recently proposed a broadcasting algorithm for their loosely-coupled optically reconfigurable parallel computer where they have shown that the total number of nodes, N(S), informed up to step S follows a recurrence relation. We have adapted their algorithm to our reconfigurable optical network, RON (K, N), which has slightly different modeling. We present a new analysis of this broadcasting algorithm on our network. This paper contributes by providing closed formulations for the N(S) that yield the termination time for both single-port and k-port modeling. The derived closed formulate are easier to computer than the recurrence relations.

We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer that synchronizes nodes with their neighbors in a tree network. The scheme has optimal memory requirement — only one bit per processor. is snap-stabilizing [11], meaning that it always behaves according to its specification. The proposed synchronizer being snap-stabilizing is optimal in terms of stabilization time. We show an application of the synchronizer by designing an efficient broadcast algorithm in tree networks. is also snap-stabilizing and needs only 2h + 2m - 1 rounds to broadcast m messages, where h is the height of the tree.

In a 1-fault tolerant minimal broadcast network, a node of a network, called the originator, has a message which is to be transmitted to all other nodes of the network in minimum time regardless of the failure of a single communication line. In some instances, it is advantageous to use time-relaxed broadcast networks that require slightly more than the minimum transmission time, but have sparser edge sets. This paper presents a general compounding algorithm to construct sparse, time-relaxed, 1-fault tolerant broadcast networks. In the algorithm, copies of a broadcast network without faults are interconnected with additional edges according to the structure of a 1-fault tolerant broadcast network with two special properties. Both the 1-fault tolerant broadcast network and the broadcast network without faults may be time-relaxed. Computational results show that the algorithm yields sparser networks by allowing additional time units.

Broadcasting is a fundamental problem in the information dissemination area. In classical broadcasting, a message must be sent from one network member to all other members as rapidly as feasible. Although it has been demonstrated that this problem is NP-Hard for arbitrary graphs, it has several applications in various fields. As a result, the universal lists model, replicating real-world restrictions like the memory limits of nodes in large networks, is introduced as a branch of this problem in the literature. In the universal lists model, each node is equipped with a fixed list and has to follow the list regardless of the originator.

In this study, we focus on the non-adaptive branch of universal lists broadcasting. In this regard, we establish the optimal broadcast time of $k$-ary trees and binomial trees under the non-adaptive model and provide an upper bound for complete bipartite graphs. We also improved a general upper bound for trees under the same model and showed that our upper bound cannot be improved in general.

In this paper, we derive array processors which are synthesized from uniform but non-local DAGs. We introduce limited broadcast facilities that can be adjusted to cope with current integration constraints. Our target problem is the Algebraic Path Problem, whose implementation on systolic architectures has been studied by numerous authors. We show how to compare, to classify and to improve several proposed architectures.

One node of a communication network holds a message which should reach all other nodes. In a unit of time a node can communicate with all neighbors but some transmissions may be faulty. In the model which assumes a bounded number of failures per time unit, all nodes must get the message for any location of faults, while for random independent failures the goal is to reach all nodes with high probability, for large networks. We establish relations between the number of links in networks and the time of fault-tolerant broadcasting.

The scattering problem refers to the gossiping and the broadcasting problems [1, 2]. It consists in distributing a set of data from a single source such that each component is sent to a distinct address. The gathering operation is the reverse of the scattering operation. This paper studies the problem of pipelining a scattering-gathering sequence in order to overlap these operations. We first give a general solution for distributed memory parallel computers, and next we particularly study this problem on hypercubes.

In this paper, we introduce a new information dissemination problem in which gossiping is to occur continuously but with restricted use of the network. In this problem, information continues to be generated by each member of the network and, thus, the gossip process must be ongoing. However, in order to allow the network to be used for other purposes, the communications used by the gossip process are limited to k calls per time unit. We present some preliminary results on this new problem.