TR00-011 Authors: Sotiris Nikoletseas, Paul Spirakis

Publication: 22nd February 2000 09:49

Downloads: 1701

Keywords:

We consider here a large network of $n$ nodes which supports

only the following unreliable basic communication primitive:

when a node requests communication then this request

{\em may fail}, independently of other requests, with probability

$f<1$. Even if it succeeds, the request is answered by returning

a stable link to a {\em random} node of the network. Furthermore,

each node is allowed to perform {\em at most} $g$ {\em such requests}

where $g$ is constant (independent of $n$).

We present here a protocol that manages (with probability tending

to 1) to establish a {\em very long path} (i.e. of length $\Theta(n)$)

{\em of stable links} in such a network, provided $g>\frac{4 \ln 2}{1-f}$.

This protocol thus manages to {\em establish end-to-end communication}

for a large part of the network,

even in the (worst) case when

the failure probaility $f$ is constant and the number

$g$ of random requests is constant too.

This protocol is {\em optimal}\, in the sense that no linear path can be

established with a sublinear number of requests.

We also show that our protocol

is {\em fair} in the sense that any node can equiprobably

be in the established path.

We expect this protocol to be useful for establishing communication

in uncontrolled networks such as the Internet.