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.