Indexing in peer-to-peer systems
Jayavel Shanmugasundaram, Prakash Linga · 2007
Peer-to-Peer systems are large scale distributed systems whose component nodes participate in similar roles and hence are peers. Peer-to-peer systems have generated a lot of interest because of their scalability, fault-tolerance and robustness properties. The peer-to-peer paradigm was first popularized by file sharing systems like Napster, Kazaa and BitTorrent. It is increasingly being used in an enterprise setting to enable highly scalable applications using low cost commodity clusters. Amazon S3 is one such example that uses peer-to-peer technology to provide a simple scalable storage service. With large number of peers and large amounts of data, one of the questions of fundamental interest in a peer-to-peer system is: how to find relevant data quickly? In this thesis, I present efficient peer-to-peer indices that support lookup of relevant data quickly. My thesis contains (1) Kelips, an efficient Distributed Hash Table (DHT), (2) Kache, a cooperative caching application, and (3) r-Kelips, an efficient peer-to-peer range index. In addition to complex range query support, demanding applications like transaction processing and military applications require strong correctness/availability guarantees. The final part of my thesis contains techniques that provably guarantee correctness and availability of peer-to-peer range indices.