Resource discovery in distributed networks

Abstract

In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence of each other. In this paper we are interested in distributed algorithms whereby machines in a network learn of other machines in the network by making queries to machines they already know. The algorithms should be efficient both in terms of the time required and in terms of the total network communication required until all machines have discovered all other machines. We propose a very simple algorithm called Name-Dropper whereby all machines learn about each other within O(log 2 n) rounds, where n is the number of machines in the network. The total number of connections required is O(n log 2 n), and the total number of pointers which must be communicated is O(n 2 log 2 n). Each of the preceding bounds is optimal to within polylogarithmic factors. Contact author: Mor Harc...