期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
f1. 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 (n))
{\em of stable links} in such a network, provided g1−f4ln2.
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.
关键词：Communication Primitives, End-to-end Communication, Markov Processes, Networks, random graphs, Reliability
