文章基本信息

标题：Efficient Communication Establishment in Extremely Unreliable Large Networks
本地全文：下载
作者：Sotiris Nikoletseas ; Paul Spirakis
期刊名称：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