Title: Choosing a random node in a large-scale network
Speaker: Jared Saia, University of New Mexico
Date: April 18, 2005 2:30 - 3:45 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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 or 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.
This is joint work with Valerie King (U. Victoria) and Scott Lewis (U. New Mexico). It was presented at Principles of Distributed Computing (PODC) 2004.