ALCOMFT-TR-01-65

Sotiris Nikoletseas and Paul Spirakis
Efficient Communication Establishment in Adverse Communication Environments
Patras. Work package 2. May 2001.

Abstract: We consider a large network of n nodes which supports only the following unreliable basic communication primitive: when a node requests communication then this request 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 random node of the network. Furthermore, each node is allowed to perform at most g such requests where g is constant (independent of n).

We present a protocol that manages (with probability tending to 1) to establish a very long path (i.e. of length Theta(n)) of stable links in such a network, provided g>(4 \ln 2)/(1-f). This protocol thus manages to 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 optimal in the sense that no linear path can be established with a sublinear number of requests. We also show that our protocol is 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 adverse communication environments.

Postscript file: ALCOMFT-TR-01-65.ps.gz (49 kb).