Asynchronous
Resource Discovery
Abstract
Consider a dynamic, large-scale communication
infrastructure (e.g., the Internet) where nodes (e.g., in a peer to peer
system) can communicate only with nodes whose id (e.g., IP address) are known
to them. One of the basic building blocks of such a distributed system is
resource discovery - efficiently discovering the ids of the nodes that
currently exist in the system. We
present both upper and lower bounds for the resource discovery problem. For the
original problem raised by Harchol-Balter, Leighton,
and Lewin [HLL99] we present an $\Omega(n
\log n)$ message complexity lower bound for asynchronous networks whose size is
unknown. For this model, we give an asymptotically message optimal algorithm
that improves the bit complexity of Kutten and Peleg [KP02]. When each node
knows the size of its connected component, we provide a novel and highly
efficient algorithm with near linear $O(n \alpha(n,n))$ message complexity where $\alpha$ is the inverse of
Ackerman’s function). In addition, we define and study the Ad-hoc
Resource Discovery Problem, which is a practical relaxation of the original
problem. Our algorithm for ad-hoc resource discovery has near linear $O(n alpha(n,n))$ message
complexity. The algorithm efficiently deals with dynamic node additions to the
system, thus addressing an open question of [HLL99]. We present a $\Omega(n \alpha(n,n))$ lower bound
for the Ad-hoc Resource Discovery Problem, showing that our algorithm is
asymptotically message optimal.
[PODC pdf] [Journal submission pdf]