Abstract
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 2 n-⌈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.
Original language | English (US) |
---|---|
Pages (from-to) | 578-589 |
Number of pages | 12 |
Journal | Computer Journal |
Volume | 55 |
Issue number | 5 |
DOIs | |
State | Published - May 2012 |
Keywords
- Hamming distance
- crash failures
- fault-tolerance
- hypercube networks
- inherent stabilization
- node-disjoint paths
- stabilization
- transient faults
ASJC Scopus subject areas
- General Computer Science