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. |