Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-011 | 27th January 2000 00:00

Efficient Communication Establishment in Extremely Unreliable Large Networks



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.

ISSN 1433-8092 | Imprint