A Pretty Flexible API for Generic Peer-to-Peer Programming∗Giuseppe CiaccioDISI, Universit`adiGenovavia Dodecaneso 3516146 Genova, ItalyE-mail: [email protected] propose and motivate an API for programmingdistributed applications using a structured overlay net-work of peers as infrastructure. The API offers simpleprimitives and powerful mechanisms, in a way that isindependent from the underlying overlay.The dynamic set of participants is abstracted byproviding a flat space of keys, transparently scatteredacross all participants in the overlay. The API prim-itives allow application instances to send messages to-wards individual keys. Two different kinds of mes-sages can be exchanged, namely, unidirectional andrequest-response; the latter takes place in a split-phase non-blocking way, so that the application canbe made latency-tolerant and thus more performing.The request-response pattern is also shown to be cru-cial for those applications demanding a degree of useranonymity.The semantics of messages is not defined by the APIitself. Rather, the API offers a mechanism to allowthe application to set up handlers, which are upcallsto run upon message arrivals at each peer. The over-all behaviour of the application is thus shaped by thehandlers.The API also allows to define application-level han-dlers for other two typical tasks of any dynamic peer-to-peer system, namely, the migration of keys acrosspeers after new peer arrivals, and the regeneration ofmissing keys after peer departures.1. Introduction and motivationOverlay networks, both structured [23, 8, 16, 19, 15]and unstructured [6, 2], have been receiving a lot of∗This research is supported by the Italian FIRB project Web-minds.attention by the research community as flexible andscalable low-level infrastructures for distributed ap-plications of many kinds, especially those ones basedon the peer to peer (p2p) paradigm. They havealso been proposed as generic networking infrastruc-tures [11, 22, 13], because of their potential ability todecouple network addresses from physical placementsof cooperating hosts, an important feature for privacyand mobility.Structured overlays are receiving far more attentioncompared to unstructured ones, because of the perfor-mance guarantees they can in principle provide thanksto their regular topologies. On the other hand, un-structured overlays were at the core of the first large-scale p2p applications deployed to the vast communityof users, with an astounding success that shedded lightover the immense potential of the p2p paradigm.It is because of the success of p2p applications, thatone could expect a corresponding effort towards thedefinition of mechanisms, abstractions, tools, and in-frastructures supporting the design and implementa-tion of p2p systems. However, it seems that the re-search effort has mostly been devoted to the design,validation and evaluation of impressively many vari-ants of structured overlays. In addition to inventingmore and more overlay networks, a significant effort hasbeen put on porting to existing overlays a lot of classi-cal distributed applications: network storage [12, 20],naming [7], content publication [10, 6, 24, 21], multi-cast [3], and secure communications [17].All such effort allowed to validate beyond any doubtthe generality and flexibility of structured overlays aslow level distributed infrastructures.In our opinion, it is now time for a deeper under-standing of which primitives and mechanisms are bet-ter provided by the low level infrastructure in order toease the development of distributed applications lay-ered onto them. This is indeed the goal of this paper.By “distributed application” we mean any kind of pro-1-4244-0910-1/07/$20.00 ©2007 IEEEgram whose state is scattered among a set of cooper-ating entities, rather than kept in a centralized store.Thus, we are not addressing any specific applicationdomain or family; the ultimate goal of a low-level p2pinfrastructure is to support distributed applications inthe broader sense.The work by Dabek et al. [9] is a notable effort(the only one, to our knowledge) to provide a general-purpose API for distributed applications layered atopp2p structured overlays. Our work was actually in-spired by that proposal, but we came up to a slightlydifferent API once we tried to carefully re-think andmotivate each design choice. Our API shares a lotwith the API of Dabek et al., but also marks somefundamental differences; these differences shall be high-lighted in Section 7.To fix the ideas, the work presented hereafter con-cerns an abstraction layer that Dabek et al. call the“Key-based Routing Layer” (KRB). Again, the readershould pay attention to the fact, that we are exam-ining primitives of a low-level infrastructure, which issupposed to be neutral with respect to any applicationdomain.2. Messages: name space, send, forward,and receiveLet us define the key space as the set of 2kbinarywords of k bits. This space is (dynamically) mappedonto the (changeable) set of peers involved in the over-lay, in such a way that each peer becomes responsiblefor a contiguous key range. The key space is a conve-nient abstraction for the set of peers involved in theoverlay, as it abstracts from Internet addresses as wellas membership changes in the overlay. The API thusprovides the key space, rather than Internet addresses,as name space for the applications.The key space is thus a name space, not a data set;each individual key always exists on its own. Specificapplication may associate pieces of information to indi-vidual keys, as well as leave most keys “unpopulated”(as it happens with DHTs), but this is just one partic-ular way to use the key space provided by the low-levelinfrastructure.The mission of an overlay is to allow the exchange ofmessages among, and throughout, participant entities.As we choose the key space as abstraction of the set ofparticipants, messages are addressed towards individ-ual keys, rather than individual peers.A message directed towards key A must be trans-parently routed towards its recipient, namely, the peerwhose key range contains A. The route traverses anumber of intermediate peers, starting from the sender.At each peer on the path, the runtime system must takea routing decision based on local information concern-ing the neighbourhood, and according to such decisionit forwards the message to another peer.The routing algorithm, transparently operated