Resource discovery in networks under bandwidth limitations

The Resource Discovery Problem [4], where cooperating machines need to find one another in a network, was introduced by Harchol-Balter, Leighton, and Lewin in the context of Akamai Technologies with the goal of building an Internet-wide content-distribution system. In the solutions for the synchronous setting proposed so far [4, 11, 12] there is a possibility that during some time step many machines may contact a single machine, and this is not a realistic assumption. This work assumes a synchronous model, however at each step a machine can send and receive only a constant number of messages. It is shown that the conjectured poly-logarithmic upper bound [4] for such a setting is not possible. This is done by proving a lower bound on time of Ω(n), where n is the number of participating nodes. For this model a randomized algorithm is presented that solves the resource discovery problem in O(n log² n) time, i.e., within a poly-logarithmic factor of the corresponding lower bound. The algorithm has a O(n² log² n) message complexity and O(n³ log³ n) communication complexity. Simulation results for the algorithm illustrate the lower and upper bounds, and lead to interesting observations.