| Title | Choosing a random node in a large-scale network |
| Speaker | Prof. Jared Saia, University of New Mexico |
| Web page | http://www.cs.unm.edu/~saia/ |
| Time | Friday, May 6, 2:00pm |
| Location | HNB 107 |
We present a fully distributed algorithm which chooses a node uniformly at random from the set of all nodes in a large-scale network. Our algorithm makes use of a distributed hash table (DHT) data structure. Our algorithm has latency O(log n) and sends O(log n) messages in expectation for a standard DHT like Chord. Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms; and to support the creation and maintenance of random links, and thereby offer a simple means to improve fault-tolerance.