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.