A distributed hash table for computational grids

Summary form only given. We present and analyze a distributed hash table-based supervised peer-to-peer system that allows an even distribution of and efficient lookup for objects (e.g. data or tasks) stored in the system. A supervised peer-to-peer system is a system that is formed by a supervisor but in which all other activities can be performed on a peer-to-peer basis without involving the supervisor. Our system has average constant degree and can distribute objects evenly among the peers up to a constant factor in expectation. The supervised peer-to-peer approach makes the system particularly useful for computational grids. As an example, we discuss the use of our structure for recursively defined algorithms such as dynamic programming and distributed tree searches, and practical problems such as Web crawling; our structure distributes tasks randomly and prevents repeated computations to optimize parallel efficiency.