ECCC-Report TR00-011https://eccc.weizmann.ac.il/report/2000/011Comments and Revisions published for TR00-011en-usTue, 22 Feb 2000 09:49:24 +0200
Paper TR00-011
| Efficient Communication Establishment in Extremely Unreliable Large Networks |
Sotiris Nikoletseas,
Paul Spirakis
https://eccc.weizmann.ac.il/report/2000/011We 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.
Tue, 22 Feb 2000 09:49:24 +0200https://eccc.weizmann.ac.il/report/2000/011