Algorithms for Resource Discovery in Distributed Networks

Abstract In a distributed network of computers the set of machines need to communicate with each other and establish a connection. The problem of how the machines discover each other by exchanging messages has been studied extensively. Generally finite sets of machines are considered and the asymptotic time bound for connecting to each other and exchanging address information have been considered. We discuss the commonly known resource discovery algorithms and discuss their connection and communication parameters and termination condition. We then propose another algorithm called New-Neighbor Algorithm whereby all machines learn about each other within O (log n ) rounds, where n is the number of machines in the finite network. The total number of connections requierd is O ( n 2 ) and the total number of pointers communicated is O ( n 3 ). This algorithm also terminates without any prior knowledge of the total number of machines, thus answering an open question of Lipton [3]. We then discuss properties of general resource discovery algorithms and show that in this setup any resource discovery algorithm requires at least Ω(log n ) number of rounds to discover each other and also the number of connections required and the number of pointers communcated is Ω( n ) and Ω( n 2 ) respectively.