ALCOMFT-TR-01-140

J. D\'\iaz, J. Petit and M. Serna
Faulty random geometric networks
Barcelona. Work package 2. June 2001.

Abstract: In this paper we analyze the computational power of random geometric networks in the presence of random (edge or node) faults considering several important network parameters. We first analyze how to emulate an original random geometric network G on a faulty network F. Our results state that, under the presence of some natural assumptions, random geometric networks can tolerate a constant node failure probability with a constant slowdown. In the case of constant edge failure probability the slowdown is an arbitrarily small constant times the logarithm of the graph order. Then we consider several network measures, stated as linear layout problems (Bisection, Minimum Linear Arrangement and Minimum Cut Width). Our results show that random geometric networks can tolerate a constant edge (or node) failure probability while maintaining the order of magnitude of the measures considered here. Finally we show that, with high probability, random geometric networks with (edge or node) faults do have a Hamiltonian cycle, provided the failure probability is constant. Such capability enables performing distributed computations based on end-to-end communication protocols.

Postscript file: ALCOMFT-TR-01-140.ps.gz (121 kb).