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 [3] we present an Ω2(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 [4]. When each node knows the size of its connected component, we provide a novel and highly efficient algorithm with near linear O(nα(n, n)) message complexity (where α 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α(n, n)) message complexity. The algorithm efficiently deals with dynamic node additions to the system, thus addressing an open question of [3]. We present a Ω(nα(n, n)) lower bound for the Ad-hoc Resource Discovery Problem, showing that our algorithm is asymptotically message optimal.

References

1. S. Ratnasamy, P. Francis, M. Handley, R. Karp and S. Shenker. A scalable content-addressable network. In Proceedings of the ACM SIGCOMM 2001 Technical Conference. August 2001.
2. I. Cidon, I. Gopal, and S. Kutten, "New Models and Algorithms for Future Networks", IEEE Transactions on Information Theory, Vol. 41, No.3, pp. 769--780, May 1995.
3. M. Harchol-Balter, T. Leighton, and D. Lewin. Resource Discovery in Distributed Networks. In Proc. 15th ACM Symp. on Principles of Distributed Computing, May 1999, pp. 229--237.
4. S. Kutten, and D. Peleg, Asynchronous Resource Discovery in Peer to Peer Networks. In 21st Syrup. on Reliable Distributed Systems, October 2002 Japan, pp. 224--231.
5. S. Kutten, D. Peleg, and U. Vishkin. Deterministic Resource Discovery in Distributed Networks. In Proc. 13th ACM Symp. on Parallel Algorithms and Architectures, 2001 Crete, pp. 77--83.
6. C. Law, and K-Y. Siu. An O(log n) Randomized Resource Discovery Algorithm. In Brief Announcements of the l4th Int. Symp. on Distributed Computing, Technical Report FIM/110.1/DLSIIS/2000, Technical University of Madrid, Oct. 2000, pp. 5--8.
7. D. Malkhi, M. Naor and D. Ratajczak. Viceroy: A scalable and dynamic emulation of the butterfly. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), August 2002.
8. G. Pandurangan, P. Raghavan and E. Upfal. Building low-diameter p2p networks. In Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2001.
9. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proceedings of the SIGCOMM 2001, August 2001.
10. R.E. Tarjan, and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. In Journal of the ACM, 31, 1984, pp. 245--281.
11. R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. In Journal of Computer and System Sciences, 18(2):110--127, April 1979.
12. B. Y. Zhao, J. D. Kubiatowicz and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. U. C. Berkeley Technical Report UCB/CSD-01-1141, April, 2001.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Networks

  • Network architectures

  • Network protocols

    • Link-layer protocols

• Theory of computation

  • Design and analysis of algorithms