Structured peer-to-peer overlay networks have recently gained popularity as a platform for the construction of resilient, large-scale distributed systems [1-5]. Structured overlays conform to a specific graph structure that allows them to locate objects by exchanging O(Lg N) messages where N is the number of nodes in the overlay.
Structured overlays can be used to construct scalable, robust, decentralized services such as distributed hash tables and application level multicast. These services in turn promise to enable novel classes of highly scalable, resilient, distributed applications, including cooperative archival storage, cooperative content distribution, and messaging.
Currently, each structured overlay protocol exports a different API with subtly different semantics. Thus, application designers must understand the intricacies of each protocol to decide which system best meets their needs. As a result, applications are locked into one system and unable to leverage innovations in other protocols. Moreover, the semantic differences make a comparative evaluation of different protocol designs difficult.
This work is an initial attempt to identify the fundamental abstractions provided by structured overlays and to define an API for the common services they provide. Such an API should be easily implemented by overlay protocols and allow efficient implementation of a wide range of applications. We believe that a common API will accelerate the adoption of structured overlays, facilitate independent innovation in overlay protocols, services, and applications, and permit direct experimental comparisons between systems.