%0 Journal Article %J Theory of Computing Systems %D 2003 %T Deterministic Resource Discovery in Distributed Networks %A Kutten,Shay %A Peleg,David %A Vishkin, Uzi %K Computer %K Science %X 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’ 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| ł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(łog^2n)$ to\pagebreak[4] $O(łog n )$, the message complexity from $O(n łog^2 n)$ to $O(n łog n )$, and the communication complexity from $O(n^2 łog^3 n)$ to $O(|E_0|ł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. %B Theory of Computing Systems %V 36 %P 479 - 495 %8 2003/// %@ 1432-4350 %G eng %U http://dx.doi.org/10.1007/s00224-003-1084-8 %N 5