Search

Many fundamental problems in the area of distributed systems such as security, reliable routing, network survivability and broadening available bandwidth can be addressed through the use of disjoint paths between communication endpoints. Therefore, distributed solutions to the disjoint paths problem are of crucial importance to these fundamental problems. Disjoint paths naturally exist in traditional networks; however, these networks provide no guarantees regarding the presence and the number of available disjoint paths. On the other hand, network topologies structured based on Caley graphs such as hypercube, star networks and their variations possess many desirable properties related to disjoint paths. Therefore, it is anticipated that backbones of future networks will be structured following some Caley graph topologies. In this paper, we present a simple novel stabilizing and inherently stabilizing algorithm to route messages over all node-disjoint paths of optimal length from one non-faulty process to another in at most n+1 rounds in an n-dimensional hypercube network in the presence of crash failures. The proposed algorithm can tolerate up to 2n−⌈log (n+1)⌉ process/link failures in the network and a maximum of ⌊(L−2)/3⌋ process/link failures on each disjoint path, where L is the number of processes on a disjoint path and the distance between any two failed processes/links is at least three. The proposed algorithm tolerates a large number of process and link failures, while delivering all n messages over optimal-length disjoint paths in the presence of maximum permissible process/link failures on each path. This is achieved by a simple uniform distributed algorithm using only local knowledge of failure locations. [ABSTRACT FROM AUTHOR]

Abstract: This work addresses the problem of having a limited number of resources in a multicomputer system that each processing element needs to access. Placing these resources in the system so that all processing elements can access them in a comparable manner is called the “resource placement problem”. In this paper, we present resource placement methods for two-dimensional toroidal networks. These methods assure uniformity such that the resources are distributed uniformly over the network where each resource is assigned an equivalent number of non-resource nodes. Hence, the resources’ related traffic would have a balanced distribution over the network. This increases the overall network utilization rather than having parts of the network congested while others are barely utilized. Furthermore, the presented methods minimize the maximum distance between a non-resource node and its closest resource. There are many messages in a multi-computer system competing for its communication channels. The longer the path, traversed by a message, the higher the probability becomes that the message blocks or is blocked by other messages. Indeed, reducing the distance between a resource and a non-resource decreases the average network latency and increases the traffic volume a network could handle before it saturates. Analytical and simulation results show that the presented methods are superior to some existing methods in terms of reducing the average network latency. [Copyright &y& Elsevier]

A perfect distance-d placement distributes a limited number of resources in a multicomputer parallel system so that every non-resource node is within a distance d or less from exactly one resource node. In this paper, we prove a necessary and sufficient condition for the existence of perfect distance-d placements in 2D toroidal networks. Furthermore, we describe how to generate these placements when they exist. [ABSTRACT FROM AUTHOR]