An optimal inherently stabilizing 2-neighborhood crash resilient protocol for secure and reliable routing in hypercube networks

Mehmet Hakan Karaata, Ozgur Sinanoglu, Bader AlBdaiwi

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)578-589
Number of pages12
JournalComputer Journal
Volume55
Issue number5
DOIs
StatePublished - May 2012

Keywords

  • Hamming distance
  • crash failures
  • fault-tolerance
  • hypercube networks
  • inherent stabilization
  • node-disjoint paths
  • stabilization
  • transient faults

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'An optimal inherently stabilizing 2-neighborhood crash resilient protocol for secure and reliable routing in hypercube networks'. Together they form a unique fingerprint.

Cite this