##
Deterministic Distributed Resource Discovery

###
Shay Kutten and David Peleg

**To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC2000),
Portland, Oregon, 16-19 July 2000**

##
Abstract

The resource discovery problem was introduced by Harchol-Balter, Leighton
and Lewin. They developed a randomized algorithm for the problem in the
weakly connected directed graph model. The current paper proposes a deterministic
algorithm for the problem in the same model, with improved time, message
and communication complexities. Specifically, the time complexity is reduced
from O(log^2 n) to O(log n log* n), the message complexity from O(n log^2 n) to O(n log n log* n), and the communication complexity from O(n^2 log^3 n) to O(n^2 log^2 n). 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)).