@article {18023,
title = {Deterministic Resource Discovery in Distributed Networks},
journal = {Theory of Computing Systems},
volume = {36},
year = {2003},
month = {2003///},
pages = {479 - 495},
abstract = {The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices{\textquoteright} knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| {\l}og n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O({\l}og^2n)$ to\pagebreak[4] $O({\l}og n )$, the message complexity from $O(n {\l}og^2 n)$ to $O(n {\l}og n )$, and the communication complexity from $O(n^2 {\l}og^3 n)$ to $O(|E_0|{\l}og ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.},
keywords = {Computer, Science},
isbn = {1432-4350},
url = {http://dx.doi.org/10.1007/s00224-003-1084-8},
author = {Kutten,Shay and Peleg,David and Vishkin, Uzi}
}