Name
Abstract | ||
|---|---|---|
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 \Omega(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^2 n) time, i.e., within a poly-logarithmic factor of the corresponding lower bound. The algorithm has a O(n^2 log^2 n) message complexity and O(n^3 log^3 n) communication complexity. Simulation results for the algorithm illustrate the lower and upper bounds, and lead to interesting observations. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/ISPDC.2006.40 | ISPDC |
Keywords | Field | DocType |
randomized algorithm,poly-logarithmic factor,resource discovery problem,n log,constant number,single machine,time step,bandwidth limitations,communication complexity,upper bound,message complexity,broadcasting,bandwidth allocation,computer science,internet,distributed computing,lower bound,distributed processing,bandwidth | Randomized algorithm,Broadcasting,Upper and lower bounds,Bandwidth allocation,Computer science,Peer to peer computing,Real-time computing,Theoretical computer science,Communication complexity,Bandwidth (signal processing),The Internet,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-7695-2638-1 | 0 | 0.34 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kishori M. Konwar | 1 | 107 | 17.49 |
| Alex A. Shvartsman | 2 | 266 | 20.83 |