Abstract of Paper Accepted to PODC 2000

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)).