| Traditional distributed systems generally use the client-server model, where data is served by dedicated servers and clients are consumers. This model has limited scalability since the servers can become performance bottlenecks and the maintenance costs are high. Peer-to-peer (P2P) systems have emerged as a scalable model for distributed computing as they allow the sharing of resources available at the client machines in a decentralized manner. They gained a lot of popularity with file sharing applications such as Napster and Gnutella. These applications, however, do not provide efficient search mechanisms and do not scale well with the increasing number of users. As a result, Distributed Hash Table (DHT) based structured P2P systems have been proposed. DHTs support efficient exact key lookups in addition to offering very desirable properties such as scalability, dynamic node insertion and departure, fault tolerance, and efficient routing. However their applicability is limited as they only support exact key lookups. We believe that DHTs can be extended to support more complex querying operations, and thus provide the infrastructure for a larger set of applications. In this thesis, we describe how various complex querying operations can be supported over DHTs. Among the operations we explored are range queries, content-based event dissemination, and similarity search. We also describe several applications that can benefit from these operations such as publish/subscribe systems and distributed Web service discovery. |
