doc: Add RFC documents

1 files changed, 5099 insertions, 0 deletions

diff --git a/doc/rfc/rfc4981.txt b/doc/rfc/rfc4981.txt
new file mode 100644
index 0000000..6e832a9
--- /dev/null
+++ b/doc/rfc/rfc4981.txt
@@ -0,0 +1,5099 @@
+
+
+
+
+
+
+Network Working Group                                          J. Risson
+Request for Comments: 4981                                      T. Moors
+Category: Informational                    University of New South Wales
+                                                          September 2007
+
+
+       Survey of Research towards Robust Peer-to-Peer Networks:
+                            Search Methods
+
+Status of This Memo
+
+   This memo provides information for the Internet community.  It does
+   not specify an Internet standard of any kind.  Distribution of this
+   memo is unlimited.
+
+IESG Note
+
+   This RFC is not a candidate for any level of Internet Standard.  The
+   IETF disclaims any knowledge of the fitness of this RFC for any
+   purpose and notes that the decision to publish is not based on IETF
+   review apart from IESG review for conflict with IETF work.  The RFC
+   Editor has chosen to publish this document at its discretion.  See
+   RFC 3932 for more information.
+
+Abstract
+
+   The pace of research on peer-to-peer (P2P) networking in the last
+   five years warrants a critical survey.  P2P has the makings of a
+   disruptive technology -- it can aggregate enormous storage and
+   processing resources while minimizing entry and scaling costs.
+
+   Failures are common amongst massive numbers of distributed peers,
+   though the impact of individual failures may be less than in
+   conventional architectures.  Thus, the key to realizing P2P's
+   potential in applications other than casual file sharing is
+   robustness.
+
+   P2P search methods are first couched within an overall P2P taxonomy.
+   P2P indexes for simple key lookup are assessed, including those based
+   on Plaxton trees, rings, tori, butterflies, de Bruijn graphs, and
+   skip graphs.  Similarly, P2P indexes for keyword lookup, information
+   retrieval and data management are explored.  Finally, early efforts
+   to optimize range, multi-attribute, join, and aggregation queries
+   over P2P indexes are reviewed.  Insofar as they are available in the
+   primary literature, robustness mechanisms and metrics are highlighted
+   throughout.  However, the low-level mechanisms that most affect
+   robustness are not well isolated in the literature.  Recommendations
+   are given for future research.
+
+
+
+Risson & Moors               Informational                      [Page 1]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+Table of Contents
+
+   1. Introduction ....................................................3
+      1.1. Related Disciplines ........................................6
+      1.2. Structured and Unstructured Routing ........................7
+      1.3. Indexes and Queries ........................................9
+   2. Index Types ....................................................10
+      2.1. Local Index (Gnutella) ....................................10
+      2.2. Central Index (Napster) ...................................12
+      2.3. Distributed Index (Freenet) ...............................13
+   3. Semantic Free Index ............................................15
+      3.1. Origins ...................................................15
+           3.1.1. Plaxton, Rajaraman, and Richa (PRR) ................15
+           3.1.2. Consistent Hashing .................................16
+           3.1.3. Scalable Distributed Data Structures (LH*) .........16
+      3.2. Dependability .............................................17
+           3.2.1. Static Dependability ...............................17
+           3.2.2. Dynamic Dependability ..............................18
+           3.2.3. Ephemeral or Stable Nodes -- O(log n) or
+                  O(1) Hops ..........................................19
+           3.2.4. Simulation and Proof ...............................20
+      3.3. Latency ...................................................21
+           3.3.1. Hop Count and the O(1)-Hop DHTs ....................21
+           3.3.2. Proximity and the O(log n)-Hop DHTs ................22
+      3.4. Multicasting ..............................................23
+           3.4.1. Multicasting vs. Broadcasting ......................23
+           3.4.2. Motivation for DHT-based Multicasting ..............23
+           3.4.3. Design Issues ......................................24
+      3.5. Routing Geometries ........................................25
+           3.5.1. Plaxton Trees (Pastry, Tapestry) ...................25
+           3.5.2. Rings (Chord, DKS) .................................27
+           3.5.3. Tori (CAN) .........................................28
+           3.5.4. Butterflies (Viceroy) ..............................29
+           3.5.5. de Bruijn (D2B, Koorde, Distance Halving, ODRI) ....30
+           3.5.6. Skip Graphs ........................................32
+   4. Semantic Index .................................................33
+      4.1. Keyword Lookup ............................................34
+           4.1.1. Gnutella Enhancements ..............................36
+           4.1.2. Partition-by-Document, Partition-by-Keyword ........38
+           4.1.3. Partial Search, Exhaustive Search ..................39
+      4.2. Information Retrieval .....................................39
+           4.2.1. Vector Model (PlanetP, FASD, eSearch) ..............41
+           4.2.2. Latent Semantic Indexing (pSearch) .................43
+           4.2.3. Small Worlds .......................................43
+   5. Queries ........................................................44
+      5.1. Range Queries .............................................45
+      5.2. Multi-Attribute Queries ...................................48
+      5.3. Join Queries ..............................................50
+
+
+
+Risson & Moors               Informational                      [Page 2]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+      5.4. Aggregation Queries .......................................50
+   6. Security Considerations ........................................52
+   7. Conclusions ....................................................52
+   8. Acknowledgments ................................................53
+   9. References .....................................................54
+      9.1. Informative References ....................................54
+
+1.  Introduction
+
+   Peer-to-peer (P2P) networks are those that exhibit three
+   characteristics: self-organization, symmetric communication, and
+   distributed control [1].  A self-organizing P2P network
+   "automatically adapts to the arrival, departure and failure of nodes"
+   [2].  Communication is symmetric in that peers act as both clients
+   and servers.  It has no centralized directory or control point.
+   USENET servers and BGP peers have these traits [3] but the emphasis
+   here is on the flurry of research since 2000.  Leading examples
+   include Gnutella [4], Freenet [5], Pastry [2], Tapestry [6], Chord
+   [7], the Content Addressable Network (CAN) [8], pSearch [9], and
+   Edutella [10].  Some have suggested that peers are inherently
+   unreliable [11].  Others have assumed well-connected, stable peers
+   [12].
+
+   This critical survey of P2P academic literature is warranted, given
+   the intensity of recent research.  At the time of writing, one
+   research database lists over 5,800 P2P publications [13].  One vendor
+   surveyed P2P products and deployments [14].  There is also a tutorial
+   survey of leading P2P systems [15].  DePaoli and Mariani recently
+   reviewed the dependability of some early P2P systems at a high level
+   [16].  The need for a critical survey was flagged in the peer-to-peer
+   research group of the Internet Research Task Force (IRTF) [17].
+
+   P2P is potentially a disruptive technology with numerous
+   applications, but this potential will not be realized unless it is
+   demonstrated to be robust.  A massively distributed search technique
+   may yield numerous practical benefits for applications [18].  A P2P
+   system has potential to be more dependable than architectures relying
+   on a small number of centralized servers.  It has potential to evolve
+   better from small configurations -- the capital outlays for high
+   performance servers can be reduced and spread over time if a P2P
+   assembly of general purpose nodes is used.  A similar argument
+   motivated the deployment of distributed databases -- one thousand,
+   off-the-shelf PC processors are more powerful and much less expensive
+   than a large mainframe computer [19].  Storage and processing can be
+   aggregated to achieve massive scale.  Wasteful partitioning between
+   servers or clusters can be avoided.  As Gedik and Liu put it, if P2P
+   is to find its way into applications other than casual file sharing,
+   then reliability needs to be addressed [20].
+
+
+
+Risson & Moors               Informational                      [Page 3]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   The taxonomy of Figure 1 divides the entire body of P2P research
+   literature along four lines: search, storage, security, and
+   applications.  This survey concentrates on search aspects.  A P2P
+   search network consists of an underlying index (Sections 2 to 4) and
+   queries that propagate over that index (Section 5).
+
+   Search [18, 21-29]
+      Semantic-Free Indexes [2, 6, 7, 30-52]
+         Plaxton Trees
+         Rings
+         Tori
+         Butterflies
+         de Bruijn Graphs
+         Skip Graphs
+      Semantic Indexes [4, 53-71]
+         Keyword Lookup
+         Peer Information Retrieval
+         Peer Data Management
+      Queries [20, 22, 23, 25, 32, 38, 41, 56, 72-100]
+         Range Queries
+         Multi-Attribute Queries
+         Join Queries
+         Aggregation Queries
+         Continuous Queries
+         Recursive Queries
+         Adaptive Queries
+
+   Storage
+      Consistency & Replication [101-112]
+         Eventual consistency
+         Trade-offs
+      Distribution [39, 42, 90, 92, 113-131]
+         Epidemics, Bloom Filters
+      Fault Tolerance [40, 105, 132-139]
+         Erasure Coding
+         Byzantine Agreement
+      Locality [24, 43, 47, 140-160]
+      Load Balancing [37, 86, 100, 107, 151, 161-171]
+
+
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                      [Page 4]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Security
+      Character [172-182]
+         Identity
+         Reputation and Trust
+         Incentives
+      Goals [25, 27, 71, 183-197]
+         Availability
+         Authenticity
+         Anonymity
+         Access Control
+         Fair Trading
+
+   Applications [1, 198-200]
+      Memory [32, 90, 142, 201-222]
+         File Systems
+         Web
+         Content Delivery Networks
+         Directories
+      Service Discovery
+      Publish / Subscribe ...
+   Intelligence [223-228]
+      GRID
+      Security...
+   Communication [12, 92, 119, 229-247]
+      Multicasting
+      Streaming Media
+      Mobility
+      Sensors...
+
+            Figure 1: Classification of P2P Research Literature
+
+   This survey is concerned with two questions.  The first, "How do P2P
+   search networks work?"  This foundation is important given the pace
+   and breadth of P2P research in the last five years.  In Section 2, we
+   classify indexes as local, centralized and distributed.  Since
+   distributed indexes are becoming dominant, they are given closer
+   attention in Sections 3 and 4.  Section 3 compares distributed P2P
+   indexes for simple key lookup; in particular, their origins (Section
+   3.1), dependability (Section 3.2), latency (Section 3.3), and their
+   support for multicast (Section 3.4).  It classifies those indexes
+   according to their routing geometry (Section 3.5) -- Plaxton trees,
+   rings, tori, butterflies, de Bruijn graphs and skip graphs.  Section
+   4 reviews distributed P2P indexes supporting keyword lookup (Section
+   4.1) and information retrieval (Section 4.2).  Section 5 probes the
+   embryonic research on P2P queries; in particular, range queries
+   (Section 5.1), multi-attribute queries (Section 5.2), join queries
+   (Section 5.3), and aggregation queries (Section 5.4).
+
+
+
+
+Risson & Moors               Informational                      [Page 5]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   The second question, "How robust are P2P search networks?"  Insofar
+   as it is available in the research literature, we tease out the
+   robustness mechanisms and metrics throughout Sections 2 to 5.
+   Unfortunately, robustness is often more sensitive to low-level design
+   choices than it is to the broad P2P index structure, yet these
+   underlying design choices are seldom isolated in the primary
+   literature [248].  Furthermore, there has been little consensus on
+   P2P robustness metrics (Section 3.2).  Section 8 gives
+   recommendations to address these important gaps.
+
+1.1.  Related Disciplines
+
+   Peer-to-peer research draws upon numerous distributed systems
+   disciplines.  Networking researchers will recognize familiar issues
+   of naming, routing, and congestion control.  P2P designs need to
+   address routing and security issues across network region boundaries
+   [152].  Networking research has traditionally been host-centric.  The
+   Web's Universal Resource Identifiers are naturally tied to specific
+   hosts, making object mobility a challenge [216].
+
+   P2P work is data-centric [249].  P2P systems for dynamic object
+   location and routing have borrowed heavily from the distributed
+   systems corpus.  Some have used replication, erasure codes, and
+   Byzantine agreement [111].  Others have used epidemics for durable
+   peer group communication [39].
+
+   Similarly, P2P research is set to benefit from database research
+   [250].  Database researchers will recognize the need to reapply
+   Codd's principle of physical data independence, that is, to decouple
+   data indexes from the applications that use the data [23].  It was
+   the invention of appropriate indexing mechanisms and query
+   optimizations that enabled data independence.  Database indexes like
+   B+ trees have an analog in P2P's distributed hash tables (DHTs).
+   Wide-area, P2P query optimization is a ripe, but challenging, area
+   for innovation.
+
+   More flexible distribution of objects comes with increased security
+   risks.  There are opportunities for security researchers to deliver
+   new methods for availability, file authenticity, anonymity, and
+   access control [25].  Proactive and reactive mechanisms are needed to
+   deal with large numbers of autonomous, distributed peers.  To build
+   robust systems from cooperating but self-interested peers, issues of
+   identity, reputation, trust, and incentives need to be tackled.
+   Although it is beyond the scope of this paper, robustness against
+   malicious attacks also ought to be addressed [195].
+
+   Possibly the largest portion of P2P research has majored on basic
+   routing structures [18], where research on algorithms comes to the
+
+
+
+Risson & Moors               Informational                      [Page 6]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   fore.  Should the overlay be "structured" or "unstructured"?  Are the
+   two approaches competing or complementary?  Comparisons of the
+   "structured" approaches (hypercubes, rings, toroids, butterflies, de
+   Bruijn, and skip graphs) have weighed the amount of routing state per
+   peer and the number of links per peer against overlay hop counts.
+   While "unstructured" overlays initially used blind flooding and
+   random walks, overheads usually trigger some structure, for example,
+   super-peers and clusters.
+
+   P2P applications rely on cooperation between these disciplines.
+   Applications have included file sharing, directories, content
+   delivery networks, email, distributed computation, publish-subscribe
+   middleware, multicasting, and distributed authentication.  Which
+   applications will be suited to which structures?  Are there adaptable
+   mechanisms that can decouple applications from the underlying data
+   structures?  What are the criteria for selection of applications
+   amenable to a P2P design [1]?
+
+   Robustness is emphasized throughout the survey.  We are particularly
+   interested in two aspects.  The first, dependability, was a leading
+   design goal for the original Internet [251].  It deserves the same
+   status in P2P.  The measures of dependability are well established:
+   reliability, a measure of the mean-time-to-failure (MTTF);
+   availability, a measure of both the MTTF and the mean-time-to-repair
+   (MTTR); maintainability; and safety [252].  The second aspect is the
+   ability to accommodate variation in outcome, which one could call
+   adaptability.  Its measures have yet to be defined.  In the context
+   of the Internet, it was only recently acknowledged as a first-class
+   requirement [253].  In P2P, it means planning for the tussles over
+   resources and identity.  It means handling different kinds of queries
+   and accommodating changeable application requirements with minimal
+   intervention.  It means "organic scaling" [22], whereby the system
+   grows gracefully, without a priori data center costs or architectural
+   breakpoints.
+
+   In the following section, we discuss one notable omission from the
+   taxonomy of P2P networking in Figure 1 -- routing.
+
+1.2.  Structured and Unstructured Routing
+
+   P2P routing algorithms have been classified as "structured" or
+   "unstructured".  Peers in unstructured overlay networks join by
+   connecting to any existing peers [254].  In structured overlays, the
+   identifier of the joining peer determines the set of peers that it
+   connects to [254].  Early instantiations of Gnutella were
+   unstructured -- keyword queries were flooded widely [255].  Napster
+   [256] had decentralized content and a centralized index, so it only
+   partially satisfies the distributed control criteria for P2P systems.
+
+
+
+Risson & Moors               Informational                      [Page 7]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Early structured algorithms included Plaxton, Rajaraman and Richa
+   (PRR) [30], Pastry [2], Tapestry [31], Chord [7], and the Content
+   Addressable Network [8].  Mishchke and Stiller recently classified
+   P2P systems by the presence or absence of structure in routing tables
+   and network topology [257].
+
+   Some have cast unstructured and structured algorithms as competing
+   alternatives.  Unstructured approaches have been called "first
+   generation", implicitly inferior to the "second generation"
+   structured algorithms [2, 31].  When generic key lookups are
+   required, these structured, key-based routing schemes can guarantee
+   location of a target within a bounded number of hops [23].  The
+   broadcasting unstructured approaches, however, may have large routing
+   costs, or fail to find available content [22].  Despite the apparent
+   advantages of structured P2P, several research groups are still
+   pursuing unstructured P2P.
+
+   There have been two main criticisms of structured systems [61].  The
+   first relates to peer transience, which in turn, affects robustness.
+   Chawathe, et al. opined that highly transient peers are not well
+   supported by DHTs [61].  P2P systems often exhibit "churn", with
+   peers continually arriving and departing.  One objection to concerns
+   about highly transient peers is that many applications use peers in
+   well-connected parts of the network.  The Tapestry authors analyzed
+   the impact of churn in a network of 1000 nodes [31].  Others opined
+   that it is possible to maintain a robust DHT at relatively low cost
+   [258].  Very few papers have quantitatively compared the resilience
+   of structured systems.  Loguinov, Kumar, et al. claimed that there
+   were only two such works [24, 36].
+
+   The second criticism of structured systems is that they do not
+   support keyword searches and complex queries as well as unstructured
+   systems.  Given the current file-sharing deployments, keyword
+   searches seem more important than exact-match key searches in the
+   short term.  Paraphrased, "most queries are for hay, not needles"
+   [61].
+
+   More recently, some have justifiably seen unstructured and structured
+   proposals as complementary, and have devised hybrid models [259].
+   Their starting point was the observation that unstructured flooding
+   or random walks are inefficient for data that is not highly
+   replicated across the P2P network.  Structured graphs can find keys
+   efficiently, irrespective of replication.  Castro, et al. proposed
+   Structella, a hybrid of Gnutella built on top of Pastry [259].
+   Another design used structured search for rare items and unstructured
+   search for massively replicated items [54].
+
+
+
+
+
+Risson & Moors               Informational                      [Page 8]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   However, the "structured versus unstructured routing" taxonomy is
+   becoming less useful, for two reasons, Firstly, most "unstructured"
+   proposals have evolved and incorporated structure.  Consider the
+   classic "unstructured" system, Gnutella [4].  For scalability, its
+   peers are either ultrapeers or leaf nodes.  This hierarchy is
+   augmented with a query routing protocol whereby ultrapeers receive a
+   hashed summary of the resource names available at leaf nodes.
+   Between ultrapeers, simple query broadcast is still used, though
+   methods to reduce the query load here have been considered [260].
+   Secondly, there are emerging schema-based P2P designs [59], with
+   super-node hierarchies and structure within documents.  These are
+   quite distinct from the structured DHT proposals.
+
+1.3.  Indexes and Queries
+
+   Given that most, if not all, P2P designs today assume some structure,
+   a more instructive taxonomy would describe the structure.  In this
+   survey, we use a database taxonomy in lieu of the networking
+   taxonomy, as suggested by Hellerstein, Cooper, and Garcia-Molina [23,
+   261].  The structure is determined by the type of index (Sections 2 ,
+   3, and 4).  Queries feature in lieu of routing (Section 5).  The DHT
+   algorithms implement a "semantic-free index" [216].  They are
+   oblivious of whether keys represent document titles, meta-data, or
+   text.  Gnutella-like and schema-based proposals have a "semantic
+   index".
+
+   Index engineering is at the heart of P2P search methods.  It captures
+   a broad range of P2P issues, as demonstrated by the Search/Index
+   Links model [261].  As Manber put it, "the most important of the
+   tools for information retrieval is the index -- a collection of terms
+   with pointers to places where information about documents can be
+   found" [262].  Sen and Wang noted that a "P2P network" usually
+   consists of connections between hosts for application-layer
+   signaling, rather than for the data transfer itself [263].
+   Similarly, we concentrate on the "signaled" indexes and queries.
+
+   Our focus here is the dependability and adaptability of the search
+   network.  Static dependability is a measure of how well queries route
+   around failures in a network that is normally fault-free.  Dynamic
+   dependability gives an indication of query success when nodes and
+   data are continually joining and leaving the P2P system.  An
+   adaptable index accommodates change in the data and query
+   distribution.  It enables data independence, in that it facilitates
+   changes to the data layout without requiring changes to the
+   applications that use the data [23].  An adaptable P2P system can
+   support rich queries for a wide range of applications.  Some
+   applications benefit from simple, semantic-free key lookups [264].
+   Others require more complex, Structured Query Language (SQL)-like
+
+
+
+Risson & Moors               Informational                      [Page 9]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   queries to find documents with multiple keywords, or to aggregate or
+   join query results from distributed relations [22].
+
+2.  Index Types
+
+   A P2P index can be local, centralized, or distributed.  With a local
+   index, a peer only keeps the references to its own data, and does not
+   receive references for data at other nodes.  The very early Gnutella
+   design epitomized the local index (Section 2.1).  In a centralized
+   index, a single server keeps references to data on many peers.  The
+   classic example is Napster (Section 2.2).  With distributed indexes,
+   pointers towards the target reside at several nodes.  One very early
+   example is Freenet (Section 2.3).  Distributed indexes are used in
+   most P2P designs nowadays -- they dominate this survey.
+
+   P2P indexes can also be classified as non-forwarding and forwarding.
+   When queries are guided by a non-forwarding index, they jump to the
+   node containing the target data in a single hop.  There have been
+   semantic and semantic-free one-hop schemes [138, 265, 266].  Where
+   scalability to a massive number of peers is required, these schemes
+   have been extended to two hops [267, 268].  More common are the
+   forwarding P2Ps, where the number of hops varies with the total
+   number of peers, often logarithmically.  The related trade-offs
+   between routing state, lookup latency, update bandwidth, and peer
+   churn are critical to total system dependability.
+
+2.1.  Local Index (Gnutella)
+
+   P2Ps with a purely local data index are becoming rare.  In such
+   designs, peers flood queries widely and only index their own content.
+   They enable rich queries - the search is not limited to a simple key
+   lookup.  However, they also generate a large volume of query traffic
+   with no guarantee that a match will be found, even if it does exist
+   on the network.  For example, to find potential peers on the early
+   instantiations of Gnutella, 'ping' messages were broadcast over the
+   P2P network and the 'pong' responses were used to build the node
+   index.  Then, small 'query' messages, each with a list of keywords,
+   are broadcast to peers that respond with matching filenames [4].
+
+   There have been numerous attempts to improve the scalability of
+   local-index P2P networks.  Gnutella uses fixed time-to-live (TTL)
+   rings, where the query's TTL is set less than 7-10 hops [4].  Small
+   TTLs reduce the network traffic and the load on peers, but also
+   reduce the chances of a successful query hit.  One paper reported,
+   perhaps a little too bluntly, that the fixed "TTL-based mechanism
+   does not work" [67].  To address this TTL selection problem, they
+   proposed an expanding ring, known elsewhere as iterative deepening
+   [29].  It uses successively larger TTL counters until there is a
+
+
+
+Risson & Moors               Informational                     [Page 10]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   match.  The flooding, ring, and expanding ring methods all increase
+   network load with duplicated query messages.  A random walk, whereby
+   an unduplicated query wanders about the network, does indeed reduce
+   the network load but massively increases the search latency.  One
+   solution is to replicate the query k times at each peer.  Called
+   random k-walkers, this technique can be coupled with TTL limits, or
+   periodic checks with the query originator, to cap the query load
+   [67].  Adamic, Lukose, et al. suggested that the random walk searches
+   be directed to nodes with a higher degree, that is, with larger
+   numbers of inter-peer connections [269].  They assumed that higher-
+   degree peers are also capable of higher query throughputs.  However,
+   without some balancing design rule, such peers would be swamped with
+   the entire P2P signaling traffic.  In addition to the above
+   approaches, there is the 'directed breadth-first' algorithm [29].  It
+   forwards queries within a subset of peers selected according to
+   heuristics on previous performance, like the number of successful
+   query results.  Another algorithm, called probabilistic flooding, has
+   been modeled using percolation theory [270].
+
+   Several measurement studies have investigated locally indexed P2Ps.
+   Jovanovic noted Gnutella's power law behaviour [70].  Sen and Wang
+   compared the performance of Gnutella, Fasttrack [271], and Direct
+   Connect [263, 272, 273].  At the time, only Gnutella used local data
+   indexes.  All three schemes now use distributed data indexes, with
+   hierarchy in the form of Ultrapeers (Gnutella), Super-Nodes
+   FastTrack), and Hubs (Direct Connect).  It was found that a very
+   small percentage of peers have a very high degree and that the total
+   system dependability is at the mercy of such peers.  While peer up-
+   time and bandwidth were heavy-tailed, they did not fit well with the
+   Zipf distribution.  Fortunately for Internet Service Providers,
+   measures aggregated by IP prefix and Autonomous System (AS) were more
+   stable than for individual IP addresses.  A study of University of
+   Washington traffic found that Gnutella and Kazaa together contributed
+   43% of the university's total TCP traffic [274].  They also reported
+   a heavy-tailed distribution, with 600 external peers (out of 281,026)
+   delivering 26% of Kazaa bytes to internal peers.  Furthermore,
+   objects retrieved from the P2P network were typically three orders of
+   magnitude larger than Web objects -- 300 objects contributed to
+   almost half the total outbound Kazaa bandwidth.  Others reported
+   Gnutella's topology mismatch, whereby only 2-5% of P2P connections
+   link peers in the same Autonomous System (AS), despite over 40% of
+   peers being in the top 10 ASs [65].  Together these studies
+   underscore the significance of multimedia sharing applications.  They
+   motivate interesting caching and locality solutions to the topology
+   mismatch problem.
+
+   These same studies bear out one main dependability lesson: total
+   system dependability may be sensitive to the dependability of high-
+
+
+
+Risson & Moors               Informational                     [Page 11]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   degree peers.  The designers of Scamp translated this observation to
+   the design heuristic, "have the degree of each node be of nearly
+   equal size" [153].  They analyzed a system of N peers, with mean
+   degree c.log(n), where link failures occur independently with
+   probability e.  If d>0 is fixed and c>(1+d)/(-log(e)), then the
+   probability of graph disconnection goes to zero as N->infinity.
+   Otherwise, if c<(1-d)/(-log(e)), then the probability of
+   disconnection goes to one as N->infinity.  They presented a
+   localizer, which finds approximate minima to a global function of
+   peer degree and arbitrary link costs using only local information.
+   The Scamp overlay construction algorithms could support any of the
+   flooding and walking routing schemes above, or other epidemic and
+   multicasting schemes for that matter.  Resilience to high churn rates
+   was identified for future study.
+
+2.2.  Central Index (Napster)
+
+   Centralized schemes like Napster [256] are significant because they
+   were the first to demonstrate the P2P scalability that comes from
+   separating the data index from the data itself.  Ultimately, 36
+   million Napster users lost their service not because of technical
+   failure, but because the single administration was vulnerable to the
+   legal challenges of record companies [275].
+
+   There has since been little research on P2P systems with central data
+   indexes.  Such systems have also been called 'hybrid' since the index
+   is centralized but the data is distributed.  Yang and Garcia-Molina
+   devised a four-way classification of hybrid systems [276]: unchained
+   servers, where users whose index is on one server do not see other
+   servers' indexes; chained servers, where the server that receives a
+   query forwards it to a list of servers if it does not own the index
+   itself; full replication, where all centralized servers keep a
+   complete index of all available metadata; and hashing, where keywords
+   are hashed to the server where the associated inverted list is kept.
+   The unchained architecture was used by Napster, but it has the
+   disadvantage that users do not see all indexed data in the system.
+   Strictly speaking, the other three options illustrate the distributed
+   data index, not the central index.  The chained architecture was
+   recommended as the optimum for the music-swapping application at the
+   time.  The methods by which clients update the central index were
+   classified as batch or incremental, with the optimum determined by
+   the query-to-login ratio.  Measurements were derived from a clone of
+   Napster called OpenNap[277].  Another study of live Napster data
+   reported wide variation in the availability of peers, a general
+   unwillingness to share files (20-40% of peers share few or no files),
+   and a common understatement of available bandwidth so as to
+   discourage other peers from sharing one's link [202].
+
+
+
+
+Risson & Moors               Informational                     [Page 12]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Influenced by Napster's early demise, the P2P research community may
+   have prematurely turned its back on centralized architectures.
+   Chawathe, Ratnasamy, et al. opined that Google and Yahoo demonstrate
+   the viability of a centralized index.  They argued that "the real
+   barriers to Napster-like designs are not technical but legal and
+   financial" [61].  Even this view may be a little too harsh on the
+   centralized architectures -- it implies that they always have an up-
+   front capital hurdle that is steeper than for distributed
+   architectures.  The closer one looks at scalable 'centralized'
+   architectures, the less the distinction with 'distributed'
+   architectures seems to matter.  For example, it is clear that
+   Google's designers consider Google a distributed, not centralized,
+   file system [278].  Google demonstrates the scale and performance
+   possible on commodity hardware, but still has a centralized master
+   that is critical to the operation of each Google cluster.  Time may
+   prove that the value of emerging P2P networks, regardless of the
+   centralized-versus-distributed classification, is that they smooth
+   the capital outlays and remove the single points of failure across
+   the spectra of scale and geographic distribution.
+
+2.3.  Distributed Index (Freenet)
+
+   An important early P2P proposal for a distributed index was Freenet
+   [5, 71, 279].  While its primary emphasis was the anonymity of peers,
+   it did introduce a novel indexing scheme.  Files are identified by
+   low-level "content-hash" keys and by "secure signed-subspace" keys,
+   which ensure that only a file owner can write to a file while anyone
+   can read from it.  To find a file, the requesting peer first checks
+   its local table for the node with keys closest to the target.  When
+   that node receives the query, it too checks for either a match or
+   another node with keys close to the target.  Eventually, the query
+   either finds the target or exceeds time-to-live (TTL) limits.  The
+   query response traverses the successful query path in reverse,
+   depositing a new routing table entry (the requested key and the data
+   holder) at each peer.  The insert message similarly steps towards the
+   target node, updating routing table entries as it goes, and finally
+   stores the file there.  Whereas early versions of Gnutella used
+   breadth-first flooding, Freenet uses a more economic depth-first
+   search [280].
+
+   An initial assessment has been done of Freenet's robustness.  It was
+   shown that in a network of 1000 nodes, the median query path length
+   stayed under 20 hops for a failure of 30% of nodes.  While the
+   Freenet designers considered this as evidence that the system is
+   "surprisingly robust against quite large failures" [71], the same
+   datapoint may well be outside meaningful operating bounds.  How many
+   applications are useful when the first quartile of queries have path
+   lengths of several hundred hops in a network of only 1000 nodes, per
+
+
+
+Risson & Moors               Informational                     [Page 13]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Figure 4 of [71]?  To date, there has been no analysis of Freenet's
+   dynamic robustness.  For example, how does it perform when nodes are
+   continually arriving and departing?
+
+   There have been both criticisms and extensions of the early Freenet
+   work.  Gnutella proponents acknowledged the merit in Freenet's
+   avoidance of query broadcasting [281].  However, they are critical on
+   two counts: the exact file name is needed to construct a query; and
+   exactly one match is returned for each query.  P2P designs using
+   DHTs, per Section 3, share similar characteristics -- a precise query
+   yields a precise response.  The similarity is not surprising since
+   Freenet also uses a hash function to generate keys.  However, the
+   query routing used in the DHTs has firmer theoretical foundations.
+   Another difference with DHTs is that Freenet will take time, when a
+   new node joins the network, to build an index that facilitates
+   efficient query routing.  By the inventor's own admission, this is
+   damaging for a user's first impressions [282].  It was proposed to
+   download a copy of routing tables from seed nodes at startup, even
+   though the new node might be far from the seed node.  Freenet's slow
+   startup motivated Mache, Gilbert, et al. to amend the overlay after
+   failed requests and to place additional index entries on successful
+   requests -- they claim almost an order of magnitude reduction in
+   average query path length [280].  Clarke also highlighted the lack of
+   locality or bandwidth information available for efficient query
+   routing decisions [282].  He proposed that each node gather response
+   times, connection times, and proportion of successful requests for
+   each entry in the query routing table.  When searching for a key that
+   is not in its own routing table, it was proposed to estimate response
+   times from the routing metrics for the nearest known keys and
+   consequently choose the node that can retrieve the data fastest.  The
+   response time heuristic assumed that nodes close in the key space
+   have similar response times.  This assumption stemmed from early
+   deployment observations that Freenet peers seemed to specialize in
+   parts of the keyspace -- it has not been justified analytically.
+   Kronfol drew attention to Freenet's inability to do keyword searches
+   [283].  He suggested that peers cache lists of weighted keywords in
+   order to route queries to documents, using Term Frequency Inverse
+   Document Frequency (TFIDF) measures and inverted indexes (Section
+   4.2.1).  With these methods, a peer can route queries for simple
+   keyword lists or more complicated conjunctions and disjunctions of
+   keywords.  Robustness analysis and simulation of Kronfol's proposal
+   remain open.
+
+   The vast majority of P2P proposals in following sections rely on a
+   distributed index.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 14]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+3.  Semantic Free Index
+
+   Many of today's distributed network indexes are semantic.  The
+   semantic index is human-readable.  For example, it might associate
+   information with other keywords, a document, a database key, or even
+   an administrative domain.  It makes it easy to associate objects with
+   particular network providers, companies, or organizations, as
+   evidenced in the Domain Name System (DNS).  However, it can also
+   trigger legal tussles and frustrate content replication and migration
+   [216].
+
+   Distributed Hash Tables (DHTs) have been proposed to provide
+   semantic-free, data-centric references.  DHTs enable one to find an
+   object's persistent key in a very large, changing set of hosts.  They
+   are typically designed for [23]:
+
+   a) low degree.  If each node keeps routing information for only a
+      small number of other nodes, the impact of high node arrival and
+      departure rates is contained;
+
+   b) low hop count.  The hops and delay introduced by the extra
+      indirection are minimized;
+
+   c) greedy routing.  Nodes independently calculate a short path to the
+      target.  At each hop, the query moves closer to the target; and
+
+   d) robustness.  A path to the target can be found even when links or
+      nodes fail.
+
+3.1.  Origins
+
+   To understand the origins of recent DHTs, one needs to look to three
+   contributions from the 1990s.  The first two -- Plaxton, Rajaraman,
+   and Richa (PRR) [30] and Consistent Hashing [49] -- were published
+   within one month of each other.  The third, the Scalable Distributed
+   Data Structure (SDDS) [52], was curiously ignored in significant
+   structured P2P designs despite having some similar goals [2, 6, 7].
+   It has been briefly referenced in other P2P papers [46, 284-287].
+
+3.1.1.  Plaxton, Rajaraman, and Richa (PRR)
+
+   PRR is the most recent of the three.  It influenced the designs of
+   Pastry [2], Tapestry [6], and Chord [7].  The value of PRR is that it
+   can locate objects using fixed-length routing tables [6].  Objects
+   and nodes are assigned a semantic-free address, for example a 160-bit
+   key.  Every node is effectively the root of a spanning tree.  A
+   message routes toward an object by matching longer address suffixes,
+   until it encounters either the object's root node or another node
+
+
+
+Risson & Moors               Informational                     [Page 15]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   with a 'nearby' copy.  It can route around link and node failure by
+   matching nodes with a related suffix.  The scheme has several
+   disadvantages [6]: global knowledge is needed to construct the
+   overlay; an object's root node is a single point of failure; nodes
+   cannot be inserted and deleted; and there is no mechanism for queries
+   to avoid congestion hot spots.
+
+3.1.2.  Consistent Hashing
+
+   Consistent Hashing [288] strongly influenced the designs of Chord [7]
+   and Koorde [37].  Karger, et al. introduced Consistent Hashing in the
+   context of the Web-caching problem [49].  Web servers could
+   conceivably use standard hashing to place objects across a network of
+   caches.  Clients could use the approach to find the objects.  For
+   normal hashing, most object references would be moved when caches are
+   added or deleted.  On the other hand, Consistent Hashing is "smooth"
+   -- when caches are added or deleted, the minimum number of object
+   references move so as to maintain load balancing.  Consistent Hashing
+   also ensures that the total number of caches responsible for a
+   particular object is limited.  Whereas Litwin's Linear Hashing (LH*)
+   scheme requires 'buckets' to be added one at a time in sequence [50],
+   Consistent Hashing allows them to be added in any order [49].  There
+   is an open Consistent Hashing problem pertaining to the fraction of
+   items moved when a node is inserted [165].  Extended Consistent
+   Hashing was recently proposed to randomize queries over the spread of
+   caches to significantly reduce the load variance [289].
+   Interestingly, Karger [49] referred to an older DHT algorithm by
+   Devine that used "a novel autonomous location discovery algorithm
+   that learns the buckets' locations instead of using a centralized
+   directory" [51].
+
+3.1.3.  Scalable Distributed Data Structures (LH*)
+
+   In turn, Devine's primary point of reference was Litwin's work on
+   SDDSs and the associated LH* algorithm [52].  An SDDS satisfies three
+   design requirements: files grow to new servers only when existing
+   servers are well loaded; there is no centralized directory; and the
+   basic operations like insert, search, and split never require atomic
+   updates to multiple clients.  Honicky and Miller suggested the first
+   requirement could be considered a limitation since expansion to new
+   servers is not under administrative control [286].  Litwin recently
+   noted numerous similarities and differences between LH* and Chord
+   [290].  He found that both implement key search.  Although LH* refers
+   to clients and servers, nodes can operate as peers in both.  Chord
+   'splits' nodes when a new node is inserted, while LH* schedules
+   'splits' to avoid overload.  Chord requests travel O(log n) hops,
+   while LH* client requests need, at most, two hops to find the target.
+   Chord stores a small number of 'fingers' at each node.  LH* servers
+
+
+
+Risson & Moors               Informational                     [Page 16]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   store N/2 to N addresses while LH* clients store 1 to N addresses.
+   This trade-off between hop count and the size of the index affects
+   system robustness, and bears striking similarity to recent one- and
+   two-hop P2P schemes in Section 2.  The arrival and departure of LH*
+   clients does not disrupt LH* server metadata at all.  Given the size
+   of the index, the arrival and departure of LH* servers are likely to
+   cause more churn than that of Chord nodes.  Unlike Chord, LH* has a
+   single point of failure, the split coordinator.  It can be
+   replicated.  Alternatively, it can be removed in later LH* variants,
+   though details have not been progressed for lack of practical need
+   [290].
+
+3.2.  Dependability
+
+   We make four overall observations about their dependability.
+   Dependability metrics fall into two categories: static dependability,
+   a measure of performance before recovery mechanisms take over; and
+   dynamic dependability, for the most likely case in massive networks
+   where there is continual failure and recovery ("churn").
+
+3.2.1.  Static Dependability
+
+   Observation A: Static dependability comparisons show that no O(log n)
+   DHT geometry is significantly more dependable than the other O(log n)
+   geometries.
+
+   Gummadi, et al. compared the tree, hypercube, butterfly, ring, XOR,
+   and hybrid geometries.  In such geometries, nodes generally know
+   about O(log n) neighbors and route to a destination in O(log n) hops,
+   where N is the number of nodes in the overlay.  Gummadi, et al. asked
+   "Why not the ring?"  They concluded that only the ring and XOR
+   geometries permit flexible choice of both neighbors and alternative
+   routes [24].  Loguinov, et al. added the de Bruijn graph to their
+   comparison [36].  They concluded that the classical analyses, for
+   example the probability that a particular node becomes disconnected,
+   yield no major differences between the resilience of Chord, CAN, and
+   de Bruijn graphs.  Using bisection width (the minimum edge count
+   between two equal partitions) and path overlap (the likelihood that
+   backup paths will encounter the same failed nodes or links as the
+   primary path), they argued for the superior resilience of the de
+   Bruijn graph.  In short, ring, XOR, and de Bruijn graphs all permit
+   flexible choice of alternative paths, but only in de Bruijn are the
+   alternate paths independent of each other [36].
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 17]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+3.2.2.  Dynamic Dependability
+
+   Observation B: Dynamic dependability comparisons show that DHT
+   dependability is sensitive to the underlying topology maintenance
+   algorithms.
+
+   Li, et al. give the best comparison to date of several leading DHTs
+   during churn [291].  They relate the disparate configuration
+   parameters of Tapestry, Chord, Kademlia, Kelips, and OneHop to
+   fundamental design choices.  For each of these DHTs, they plotted the
+   optimal performance in terms of lookup latency (milliseconds) and
+   fraction of failed lookups.  The results led to several important
+   insights about the underlying algorithms, for example: increasing
+   routing table size is more cost-effective than increasing the rate of
+   periodic stabilization; learning about new nodes during the lookup
+   process sometimes eliminates the need for stabilization; and parallel
+   lookups reduce latency due to timeouts more effectively than faster
+   stabilization.  Similarly, Zhuang, et al. compared keep-alive
+   algorithms for DHT failure detection [292].  Such algorithmic
+   comparisons can significantly improve the dependability of DHT
+   designs.
+
+   In Figure 2, we propose a taxonomy for the topology maintenance
+   algorithms that influence dependability.  The algorithms can be
+   classified by how nodes join and leave, how they first detect
+   failures, how they share information about topology updates, and how
+   they react when they receive information about topology updates.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 18]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Normal Updates
+      Joins (passive; active) [293]
+      Leaves (passive; active) [293]
+
+   Fault Detection [292]
+      Maintenance
+         Proactive (periodic or keep-alive probes)
+         Reactive (correction-on-use, correction-on-failure) [294]
+      Report
+         Negative (all dead nodes, nodes recently failed)
+         Positive (all live nodes; nodes recently recovered) [292]
+
+   Topology Sharing: yes/ no [292]
+         Multicast Tree (explicit, implicit) [267, 295]
+         Gossip (timeouts; number of contacts) [39]
+
+   Corrective Action
+      Routing
+         Rerouting actions
+            (reroute once; route in parallel [291]; reject)
+         Routing timeouts
+            (TCP-style, virtual coordinates) [296]
+      Topology
+         Update action (evict/ replace/ tag node)
+         Update timeliness (immediate, periodic[296], delayed [297])
+
+        Figure 2: Topology Maintenance in Distributed Hash Tables
+
+3.2.3.  Ephemeral or Stable Nodes -- O(log n) or O(1) Hops
+
+   Observation C: Most DHTs use O(log n) geometries to suit ephemeral
+   nodes.  The O(1) hop DHTs suit stable nodes and deserve more research
+   attention.
+
+   Most of the DHTs in Section 3.5 assume that nodes are ephemeral, with
+   expected lifetimes of one to two hours.  Therefore, they mostly use
+   an O(log n) geometry.  The common assumption is that maintenance of
+   full routing tables in the O(1) hop DHTs will consume excessive
+   bandwidth when nodes are continually joining and leaving.  The
+   corollary is that, when they run on stable infrastructure servers
+   [298], most of the DHTs in Section 3.5 are less than optimal --
+   lookups take many more hops than necessary, wasting latency and
+   bandwidth budgets.  The O(1) hop DHTs suit stable deployments and
+   high lookup rates.  For a churning 1024-node network, Li, et al.
+   concluded that OneHop is superior to Chord, Tapestry, Kademlia, and
+   Kelips in terms of latency and lookup success rate [291].  For a
+   3000-node network, they concluded that "OneHop is only preferable to
+   Chord when the deployment scenario allows a communication cost
+
+
+
+Risson & Moors               Informational                     [Page 19]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   greater than 20 bytes per node per second" [291].  This apparent
+   limitation needs to be put in context.  They assumed that each node
+   issues only one lookup every 10 minutes and has a lifetime of only 60
+   minutes.  It seems reasonable to expect that in some deployments,
+   nodes will have a lifetime of weeks or more, a maintenance bandwidth
+   of tens of kilobits per second, and a load of hundreds of lookups per
+   second.  O(1) hop DHTs are superior in such situations.  OneHop can
+   scale at least to many tens of thousands of nodes [267].  The recent
+   O(1) hop designs [267, 295] are vastly outnumbered by the O(log n)
+   DHTs in Section 3.5.  Research on the algorithms of Figure 2 will
+   also yield improvements in the dependability of the O(1) hop DHTs.
+
+3.2.4.  Simulation and Proof
+
+   Observation D: Although not yet a mature science, the study of DHT
+   dependability is helped by recent simulation and formal development
+   tools.
+
+   While there are recent reference architectures [294, 298], much of
+   the DHT literature in Section 3.5 does not lend itself to repeatable,
+   comparative studies.  The best comparative work to date [291] relies
+   on the Peer-to-Peer Simulator (P2PSIM) [299].  At the time of
+   writing, it supports more DHT geometries than any other simulator.
+   As the study of DHTs matures, we can expect to see the simulation
+   emphasis shift from geometric comparison to a comparison of the
+   algorithms of Figure 2.
+
+   P2P correctness proofs generally rely on less-than-complete formal
+   specifications of system invariants and events [7, 45, 300].  Li and
+   Plaxton expressed concern that "when many joins and leaves happen
+   concurrently, it is not clear whether the neighbor tables will remain
+   in a 'good' state" [47].  While acknowledging that guaranteeing
+   consistency in a failure-prone network is impossible, Lynch, Malkhi,
+   et al. sketched amendments to the Chord algorithm to guarantee
+   atomicity [301].  More recently, Gilbert, Lynch, et al. gave a new
+   algorithm for atomic read/write memory in a churning distributed
+   network, suggesting it to be a good match for P2P [302].  Lynch and
+   Stoica show in an enhancement to Chord that lookups are provably
+   correct when there is a limited rate of joins and failures [303].
+   Fault Tolerant Active Rings is a protocol for active joins and leaves
+   that was formally specified and proven using B-method tools [304].  A
+   good starting point for a formal DHT development would be the
+   numerous informal API specifications [22, 305, 306].  Such work could
+   be informed by other efforts to formally specify routing invariants
+   [307, 308].
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 20]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+3.3.  Latency
+
+   The key metrics for DHT latency are:
+
+   1) Shortest-Path Distance and Diameter.  In graph theory, the
+      shortest-path distance is the minimum number of edges in any path
+      between two vertices of the graph.  Diameter is the largest of all
+      shortest-path distances in a graph [309].  Networking synonyms for
+      distance on a DHT are "hop count" and "lookup length".
+
+   2) Latency and Latency Stretch.  Two types of latency are relevant
+      here -- network-layer latency and overlay latency.  Network-layer
+      latency has been referred to as "proximity" or "locality" [24].
+      Stretch is the cost of an overlay path between two nodes, divided
+      by the cost of the direct network path between those nodes [310].
+      Latency stretch is also known as the "relative delay penalty"
+      [311].
+
+3.3.1.  Hop Count and the O(1)-Hop DHTs
+
+   Hop count gives an approximate indication of path latency.  O(1)-hop
+   DHTs have path latencies lower than the O(log n)-hop DHTs [291].
+   This significant advantage is often overlooked on account of concern
+   about the messaging costs to maintain large routing tables (Section
+   3.2.3).  Such concern is justified when the mean node lifetime is
+   only a few hours and the mean lookup interval per node is more than a
+   few seconds (the classic profile of a P2P file-sharing node).
+   However, for a large, practical operating range (node lifetimes of
+   days or more, lookup rates of over tens of lookups per second per
+   node, up to ~100,000 nodes), the total messaging cost in O(1) hop
+   DHTs is lower than in O(log n) DHTs [312].  Lookups and routing table
+   maintenance contribute to the total messaging cost.  If a deployment
+   fits this operating range, then O(1)-hop DHTs will give lower path
+   latencies and lower total messaging costs.  An additional merit of
+   the O(1)-hop DHTs is that they yield lower lookup failure rates than
+   their O(log N)-hop counterparts [291].
+
+   Low hop count can be achieved in two ways: each node has a large O(N)
+   index of nodes; or the object references can be replicated on many
+   nodes.  Beehive [313], Kelips [39], LAND [310], and Tulip [314] are
+   examples of the latter category.  Beehive achieves O(1) hops on
+   average and O(log n) hops in the worst case, by proactive replication
+   of popular objects.  Kelips replicates the 'file index'.  It incurs
+   O(sqrt(N)) storage costs for both the node index and the file index.
+   LAND uses O(log n) reference pointers for each stored object and an
+   O(log n) index to achieve a worst-case 1+e stretch, where 0<e.  The
+   Kelips-like Tulip [314] requires 2 hops per lookup.  Each node
+
+
+
+
+Risson & Moors               Informational                     [Page 21]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   maintains 2sqrt(N)log(N) links to other nodes and objects are
+   replicated on O(sqrt(N)) nodes.
+
+   The DHTs with a large O(N) node index can be divided into two groups:
+   those for which the index is always O(N); and those for which the
+   index opportunistically ranges from O(log n) to O(N).  Linear Hashing
+   (LH*) servers [52], OneHop [267], and 1h-Calot [295] fall into the
+   former category.  EpiChord [315] and Accordion [316] are examples of
+   the latter.
+
+3.3.2.  Proximity and the O(log n)-Hop DHTs
+
+   If one chooses not to use single-hop DHTs, hop count is a weak
+   indicator of end-to-end path latency.  Some hops may incur large
+   delays because of intercontinental or satellite links.  Consequently,
+   numerous DHT designs minimize path latency by considering the
+   proximity of nodes.  Gummadi, et al. classified the proximity methods
+   as follows [24]:
+
+   1) Proximity Neighbor Selection (PNS).  The nodes in the routing
+      table are chosen based on the latency of the direct hop to those
+      nodes.  The latency may be explicitly measured [317], or it may be
+      estimated using one of several synthetic coordinate systems [150,
+      154, 318].  As a lower bound on PNS performance, Dabek, et al.
+      showed that lookups on O(log n) DHTs take at least 1.5 times the
+      average roundtrip time of the underlying network [154].
+
+   2) Proximity Route Selection (PRS).  At lookup time, the choice of
+      the next-hop node relies on the latency of the direct hop to that
+      node.  PRS is less effective than PNS, though it may complement it
+      [24].  Some of the routing geometries in Section 3.5 do not
+      support PNS and/or PRS [24].
+
+   3) Proximity Identifier Selection (PIS).  Node identifiers indicate
+      geographic position.  PIS frustrates load balancing, increases the
+      risk of correlated failures, and is not often used [24].
+
+   The proximity study by Gummadi, et al. assumed recursive routing,
+   though they suggested that PNS would also be superior to PRS with
+   iterative routing [24].  Dabek, et al. found that recursive lookups
+   take 0.6 times as long as iterative lookups [150].
+
+   Beyond the explicit use of proximity information, redundancy can help
+   to avoid slow paths and servers.  One may increase the number of
+   replicas [150], use parallel lookups [291, 316], use alternate routes
+   on failure [150], or use multiple gateway nodes to enter the DHT
+   [317].
+
+
+
+
+Risson & Moors               Informational                     [Page 22]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+3.4.  Multicasting
+
+3.4.1.  Multicasting vs. Broadcasting
+
+   "Multicasting" here means sending a message to a subset of an
+   overlay's nodes.  Nodes explicitly join and leave this subset, called
+   a "multicast group".  "Broadcasting" here is a special case of
+   multicasting in which a message is sent to all nodes in the overlay.
+   Broadcasting relies on overlay membership messages -- it does not
+   need extra group membership messaging.  Castro, et al. said
+   multicasting on structured overlays is either "flooding" (one overlay
+   per group) or "tree-based" (one tree per group) [319].  These are
+   synonyms for broadcasting and multicasting respectively.
+
+   The first DHT-based designs for multicasting were CAN multicast
+   [320], Scribe [241], Bayeux [242], and i3 [231].  They were based on
+   CAN [8], Pastry [2], Tapestry [31], and Chord [7] respectively.  El-
+   Ansary, et al. devised the first DHT-based broadcasting scheme [321].
+   It was based on Chord.
+
+   Multicast trees can be constructed using reverse-path forwarding or
+   forward-path forwarding.  Scribe uses reverse-path forwarding [241].
+   Bayeux uses forward-path forwarding [242].  Borg, a multicast design
+   based on Pastry, uses a combination of forward-path and reverse-path
+   forwarding to minimize latency [237].
+
+3.4.2.  Motivation for DHT-based Multicasting
+
+   Multicasting complements DHT search capability.  DHTs naturally
+   support exact match queries.  With multicasting, they can support
+   more complex queries.  Multicasting also enables the dissemination
+   and collection of global information.
+
+   Consider, for example, aggregation queries like minimum, maximum,
+   count, sum, and average (Section 5.4).  A node at the root of a
+   dissemination tree might multicast such a query [322].  The leaf
+   nodes return local results towards the root node.  Successive parents
+   aggregate the result so that eventually the root node can compute the
+   global result.  Such queries may help to monitor the capacity and
+   health of the overlay itself.
+
+   Why bother with structured overlays for multicasting?  In Section
+   2.1, we saw that Gnutella can multicast complex queries without them
+   [4].  Castro, et al. posed the question, "Should we build Gnutella on
+   a structured overlay?" [259].  While acknowledging that their study
+   was preliminary, they did conclude that "we see no reason to build
+   Gnutella on top of an unstructured overlay" [259].  The supposedly
+   high maintenance costs of structured overlays were outweighed by
+
+
+
+Risson & Moors               Informational                     [Page 23]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   query cost savings.  The structured overlay ensured that nodes were
+   only visited once during a complex query.  It also helped to
+   accurately limit the total number of nodes visited.  Pai, et al.
+   acknowledged that multicast trees based on structured overlays
+   contribute to simple routing rules, low delay and low delay variation
+   [323].  However, they opted for unstructured, gossip-based
+   multicasting for reliability reasons: data loss near the tree root
+   affects all subtended nodes; interior node failures must be repaired
+   quickly; interior nodes are obliged to disseminate more than their
+   fair share of traffic, giving leaf nodes a "free ride".  The most
+   promising research direction is to improve on the Bimodal
+   Multicasting approach [324].  It combines the bandwidth efficiency
+   and low latency of structured, best-effort multicasting trees with
+   the reliability of unstructured gossip protocols.
+
+3.4.3.  Design Issues
+
+   None of the early structured overlay multicast designs addressed all
+   of the following issues [325]:
+
+   1) Heterogeneous Node Capacity.  Nodes differ in their processing,
+      memory, and network capacity.  Multicast throughput is largely
+      determined by the node with smallest throughput [325].  To limit
+      the multicasting load on a node, one might cap its out-degree.  If
+      the same node receives further join requests, it refers them to
+      its children ("pushdown") [240].  Bharambe, et al. explored
+      several pushdown strategies but found them inadequate to deal with
+      heterogeneity [326].  They concluded that the heterogeneity issue
+      remains open, and should be addressed before deploying DHTs for
+      high-bandwidth multicasting applications.  Independently, Zhang et
+      al. partially tackled heterogeneity by allowing nodes in their
+      CAM-Chord and CAM-Koorde designs to vary out-degree according to
+      the node's capacity [325].  However, they made no mention of the
+      "pushdown" issue -- they did not describe topology maintenance
+      when the out-degree limit is reached.
+
+   2) Reliability (Dynamic Membership).  If a multicast tree is to be
+      resilient, it must survive dynamic membership.  There are several
+      ways to deal with dynamic membership: ensure that the root node of
+      the multicasting tree does not handle all requests to join or
+      leave the multicast group [242]; use multiple interior-node-
+      disjoint trees to avoid single points of failure in tree
+      structures [322]; and split the root node into several replicas
+      and partition members across them [241].  For example, Bayeux
+      requires the root node to track all group membership changes
+      whereas Scribe does not [241].  CAN-multicast uses a single,
+      well-known host to bootstrap the join operations [320].  The
+      earliest DHT-based broadcasting work by El-Ansary, et al. did not
+
+
+
+Risson & Moors               Informational                     [Page 24]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+      address the issue of dynamic membership [321].  Ghodsi, et al.
+      addressed it in a subsequent paper, though, giving two broadcast
+      algorithms that accommodate routing table inconsistencies [327].
+      One algorithm achieves a more optimal multicasting network at the
+      expense of greater correction overhead.  Splitstream, based on
+      Scribe and Pastry, redundantly striped content across multiple
+      interior-node-disjoint multicast trees -- if one interior node
+      fails, then only one stripe is lost [240].
+
+   3) Large Any-Source Multicast Groups.  Any group member should be
+      allowed to send multicast messages.  The group should scale to a
+      very large number of hosts.  CAN-based multicast was the first
+      application-level multicast scheme to scale to groups of several
+      thousands of nodes without restricting the service model to a
+      single source [320].  Bayeux scales to large groups but has a
+      single root node for each multicast group.  It supports the any-
+      source model only by having the root node operate as a reflector
+      for multiple senders [242].
+
+3.5.  Routing Geometries
+
+   In Sections 3.5.1 to 3.5.6, we introduce the main geometries for
+   simple key lookup and survey their robustness mechanisms.
+
+3.5.1.  Plaxton Trees (Pastry, Tapestry)
+
+   Work began in March 2000 on a structured, fault-tolerant, wide-area
+   Dynamic Object Location and Routing (DOLR) system called Tapestry [6,
+   155].  While DHTs fix replica locations, a DOLR API enables
+   applications to control object placement [31].  Tapestry's basic
+   location and routing scheme follows Plaxton, Rajaraman, and Richa
+   (PRR) [30], but it remedies PRR's robustness shortcomings described
+   in Section 3.1.  Whereas each object has one root node in PRR,
+   Tapestry uses several to avoid a single point of failure.  Unlike
+   PRR, it allows nodes to be inserted and deleted.  Whereas PRR
+   required a total ordering of nodes, Tapestry uses 'surrogate routing'
+   to incrementally choose root nodes.  The PRR algorithm does not
+   address congestion, but Tapestry can put object copies close to nodes
+   generating high query loads.  PRR nodes only know of the nearest
+   replica, whereas Tapestry nodes enable selection from a set of
+   replicas (for example, to retrieve the most up to date).  To detect
+   routing faults, Tapestry uses TCP timeouts and UDP heartbeats for
+   detection, sequential secondary neighbours for rerouting, and a
+   'second chance' window so that recovery can occur without the
+   overhead of a full node insertion.  Tapestry's dependability has been
+   measured on a testbed of about 100 machines and on simulations of
+
+
+
+
+
+Risson & Moors               Informational                     [Page 25]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   about 1000 nodes.  Successful routing rates and maintenance
+   bandwidths were measured during instantaneous failures and ongoing
+   churn [31].
+
+   Pastry, like Tapestry, uses Plaxton-like prefix routing [2].  As in
+   Tapestry, Pastry nodes maintain O(log n) neighbours and route to a
+   target in O(log n) hops.  Pastry differs from Tapestry only in the
+   method by which it handles network locality and replication [2].
+   Each Pastry node maintains a 'leaf set' and a 'routing table'.  The
+   leaf set contains l/2 node IDs on either side of the local node ID in
+   the node ID space.  The routing table, in row r, column c, points to
+   the node ID with the same r-digit prefix as the local node, but with
+   an r+1 digit of c.  A Pastry node periodically probes leaf set and
+   routing table nodes, with periodicity of Tls and Trt and a timeout
+   Tout.  Mahajan, Castry, et al. analyzed the reliability versus
+   maintenance cost trade-offs in terms of the parameters l, Tls, Trt,
+   and Tout [328].  They concluded that earlier concerns about excessive
+   maintenance cost in a churning P2P network were unfounded, but
+   suggested follow-up work for a wider range of reliability targets,
+   maintenance costs, and probe periods.  Rhea Geels, et al. concluded
+   that existing DHTs fail at high churn rates [329].  Building on a
+   Pastry implementation from Rice University, they found that most
+   lookups fail to complete when there is excessive churn.  They
+   conjectured that short-lived nodes often leave the network with
+   lookups that have not yet timed out, but no evidence was provided to
+   confirm the theory.  They identified three design issues that affect
+   DHT performance under churn: reactive versus periodic recovery of
+   peers; lookup timeouts; and choice of nearby neighbours.  Since
+   reactive recovery was found to add traffic to already congested
+   links, the authors used periodic recovery in their design.  For
+   lookup timeouts, they advocated an exponentially weighted moving
+   average of each neighbour's response time, over alternative fixed
+   timeout or 'virtual coordinate' schemes.  For selection of nearby
+   neighbours, they found that 'global sampling' was more effective than
+   simply sampling a 'neighbour's neighbours' or 'inverse neighbours'.
+   Castro, Costa, et al. have refuted the suggestion that DHTs cannot
+   cope with high churn rates [330].  By implementing methods for
+   continuous detection and repair, their MSPastry implementation
+   achieved shorter routing paths and a maintenance overhead of less
+   than half a message per second per node.
+
+   There have been more recent proposals based on these early Plaxton-
+   like schemes.  Kademlia uses a bit-wise exclusive or (XOR) metric for
+   the 'distance' between 160-bit node identifiers [45].  Each node
+   keeps a list of contact nodes for each section of the node space that
+   is between 2^i and 2^(i+1) from itself (0.i<160).  Longer-lived nodes
+   are deliberately given preference on this list -- it has been found
+   in Gnutella that the longer a node has been active, the more likely
+
+
+
+Risson & Moors               Informational                     [Page 26]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   it is to remain active.  Like Kademlia, Willow uses the XOR metric
+   [32].  It implements a Tree Maintenance Protocol to 'zipper' together
+   broken segments of a tree.  Where other schemes use DHT routing to
+   inefficiently add new peers, Willow can merge disjoint or broken
+   trees in O(log n) parallel operations.
+
+3.5.2.  Rings (Chord, DKS)
+
+   Chord is the prototypical DHT ring, so we first sketch its operation.
+   Chord maps nodes and keys to an identifier ring [7, 34].  Chord
+   supports one main operation: find a node with the given key.  It uses
+   Consistent Hashing (Section 3.1) to minimize disruption of keys when
+   nodes join and leave the network.  However, Chord peers need only
+   track O(log n) other peers, not all peers as in the original
+   consistent hashing proposal [49].  It enables concurrent node
+   insertions and deletions, improving on PRR.  Compared to Pastry, it
+   has a simpler join protocol.  Each Chord peer tracks its predecessor,
+   a list of successors, and a finger table.  Using the finger table,
+   each hop is at least half the remaining distance around the ring to
+   the target node, giving an average lookup hop count of (1/2)log
+   n(base 2).  Each Chord node runs a periodic stabilization routine
+   that updates predecessor and successor pointers to cater to newly
+   added nodes.  All successors of a given node need to fail for the
+   ring to fail.  Although a node departure could be treated the same as
+   a failure, a departing Chord node first notifies the predecessor and
+   successors, so as to improve performance.
+
+   In their definitive paper, Chord's inventors critiqued its
+   dependability under churn [34].  They provided proofs on the
+   behaviour of the Chord network when nodes in a stable network fail,
+   stressing that such proofs are inadequate in the general case of a
+   perpetually churning network.  An earlier paper had posed the
+   question, "For lookups to be successful during churn, how regularly
+   do the Chord stabilization routines need to run?" [331].  Stoica,
+   Morris, et al. modeled a range of node join/departure rates and
+   stabilization periods for a Chord network of 1000 nodes.  They
+   measured the number of timeouts (caused by a finger pointing to a
+   departed node) and lookup failures (caused by nodes that temporarily
+   point to the wrong successor during churn).  They also modeled the
+   'lookup stretch', the ratio of the Chord lookup time to optimal
+   lookup time on the underlying network.  They demonstrated the latency
+   advantage of recursive lookups over iterative lookups, but there
+   remains room for delay reduction.  For further work, the authors
+   proposed to improve resilience to network partitions, using a small
+   set of known nodes or 'remembered' random nodes.  To reduce the
+   number of messages per lookup, they suggested an increase in the size
+   of each step around the ring, accomplished via a larger number of
+   fingers at each node.  Much of the paper assumed independent, equally
+
+
+
+Risson & Moors               Informational                     [Page 27]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   likely node failures.  Analysis of correlated node failures, caused
+   by massive site or backbone failures, will be more important in some
+   deployments.  The paper did not attempt to recommend a fixed optimal
+   stabilization rate.  Liben-Nowell, Balakrishnan, et al. had suggested
+   that optimum stabilization rate might evolve according to
+   measurements of peers' behaviour [331] -- such a mechanism has yet to
+   be devised.
+
+   Alima, El-Ansary, et al. considered the communication costs of
+   Chord's stabilization routines, referred to as 'active correction',
+   to be excessive [332].  Two other robustness issues also motivated
+   their Distributed K-ary Search (DKS) design, which is similar to
+   Chord.  Firstly, the total system should evolve for an optimum
+   balance between the number of peers, the lookup hop count, and the
+   size of the routing table.  Secondly, lookups should be reliable --
+   P2P algorithms should be able to guarantee a successful lookup for
+   key/value pairs that have been inserted into the system.  A similar
+   lookup-correctness issue was raised elsewhere by one of Chord's
+   authors; "Is it possible to augment the data structure to work even
+   when nodes (and their associated finger lists) just disappear?" [333]
+   Alima, El-Ansary, et al. asserted that P2Ps using active correction,
+   like Chord, Pastry, and Tapestry, are unable to give such a
+   guarantee.  They propose an alternate 'correction-on-use' scheme,
+   whereby expired routing entries are corrected by information
+   piggybacking lookups and insertions.  A prerequisite is that lookup
+   and insertion rates are significantly higher than node arrival,
+   departure, and failure rates.  Correct lookups are guaranteed in the
+   presence of simultaneous node arrivals or up to f concurrent node
+   departures, where f is configurable.
+
+3.5.3.  Tori (CAN)
+
+   Ratnasamy, Francis, et al. developed the Content-Addressable Network
+   (CAN), another early DHT widely referenced alongside Tapestry,
+   Pastry, and Chord [8, 334].  It is arranged as a virtual
+   d-dimensional Cartesian coordinate space on a d-torus.  Each node is
+   responsible for a zone in this coordinate space.  The designers used
+   a heuristic thought to be important for large, churning P2P networks:
+   keep the number of neighbours independent of system size.
+   Consequently, its design differs significantly from Pastry, Tapestry,
+   and Chord.  Whereas they have O(log n) neighbours per node and O(log
+   n) hops per lookup, CAN has O(d) neighbours and O(dn^(1/d)) hop
+   count.  When CAN's system-wide parameter d is set to log(n), CAN
+   converges to their profile.  If the number of nodes grows, a major
+   rearrangement of the CAN network may be required [151].  The CAN
+   designers considered building on PRR, but opted for the simple, low-
+   state-per-node CAN algorithm instead.  They had reasoned that a PRR-
+   based design would not perform well under churn, given node
+
+
+
+Risson & Moors               Informational                     [Page 28]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   departures and arrivals would affect a logarithmic number of nodes
+   [8].
+
+   There have been preliminary assessments of CAN's resilience.  When a
+   node leaves the CAN in an orderly fashion, it passes its own Virtual
+   ID (VID), its neighbours' VIDs and IP addresses, and its key/value
+   pairs to a takeover node.  If a node leaves abruptly, its neighbours
+   send recovery messages towards the designated takeover node.  CAN
+   ensures the recovery messages reach the takeover node, even if nodes
+   die simultaneously, by maintaining a VID chain with Chord's
+   stabilization algorithm.  Some initial 'proof of concept' resilience
+   simulations were run using the Network Simulator (NS) [335] for up to
+   a few hundred nodes.  Average hop counts and lookup failure
+   probabilities were plotted against the total number of nodes for
+   various node failure rates [8].  The CAN team documented several open
+   research questions pertaining to state/hop count trade-offs,
+   resilience, load, locality, and heterogeneous peers [44, 334].
+
+3.5.4.  Butterflies (Viceroy)
+
+   Viceroy approximates a butterfly network [46].  It generally has
+   constant degree like CAN.  Like Chord, Tapestry, and Pastry, it has
+   logarithmic diameter.  It improves on these systems, inasmuch as its
+   diameter is better than CAN and its degree is better than Chord,
+   Tapestry, and Pastry.  As with most DHTs, it utilizes Consistent
+   Hashing.  When a peer joins the Viceroy network, it takes a random
+   but permanent 'identity' and selects its 'level' within the network.
+   Each peer maintains general ring pointers ('predecessor' and
+   'successor'), level ring pointers ('nextonlevel' and 'prevonlevel'),
+   and butterfly pointers ('left', 'right', and 'up').  When a peer
+   departs, it normally passes its key pairs to a successor, and
+   notifies other peers to find a replacement peer.
+
+   The Viceroy paper scoped out the issue of robustness.  It explicitly
+   assumed that peers do not fail [46].  It assumed that join and leave
+   operations do not overlap, so as to avoid the complication of
+   concurrency mechanisms like locking.  Kaashoek and Karger were
+   somewhat critical of Viceroy's complexity [37].  They also pointed to
+   its fault-tolerance blind spot.  Li and Plaxton suggested that such
+   constant-degree algorithms deserve further consideration [47].  They
+   offered several pros and cons.  The limited degree may increase the
+   risk of a network partition, or inhibit use of local neighbours (for
+   the simple reason that there are less of them).  On the other hand,
+   it may be easier to reason about the correctness of fixed-degree
+   networks.  One of the Viceroy authors has since proposed constant-
+   degree peers in a two-tier, locality-aware DHT [310] -- the lower
+   degree maintained by each lower-tier peer purportedly improves
+   network adaptability.  Another Viceroy author has since explored an
+
+
+
+Risson & Moors               Informational                     [Page 29]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   alternative bounded-degree graph for P2P, namely the de Bruijn graph
+   [336].
+
+3.5.5.  de Bruijn (D2B, Koorde, Distance Halving, ODRI)
+
+   De Bruijn graphs have had numerous refinements since their inception
+   [337, 338].  Schlumberger was the first to use them for networking
+   [339].  Two research teams independently devised the 'generalized' de
+   Bruijn graph that accommodates a flexible number of nodes in the
+   system [340, 341].  Rowley and Bose studied fault-tolerant rings
+   overlaid on the de Bruijn graph [342].  Lee, Liu, et al. devised a
+   two-level de Bruijn hierarchy, whereby clusters of local nodes are
+   interconnected by a second-tier ring [343].
+
+   Many of the algorithms discussed previously are 'greedy' in that each
+   time a query is forwarded, it moves closer to the destination.
+   Unfortunately, greedy algorithms are generally suboptimal -- for a
+   given degree, the routing distance is longer than necessary [344].
+   Unlike these earlier P2P designs, de Bruijn graphs of degree k
+   achieve an asymptotically optimal diameter log n, where n is the
+   number of nodes in the system and k can be varied to improve
+   resilience.  If there are O(log n) neighbours per node, the de Bruijn
+   hop count is O(log n/log log n).  To illustrate de Bruijn's practical
+   advantage, consider a network with one million nodes of degree 20:
+   Chord has a diameter of 20, while de Bruijn has a diameter of 5 [36].
+   In 2003, there were a quick succession of de Bruijn proposals -- D2B
+   [345], Koorde [37], Distance Halving [132, 336], and the Optimal
+   Diameter Routing Infrastructure (ODRI) [36].
+
+   Fraigniaud and Gauron began the D2B design by laying out an informal
+   problem statement: keys should be evenly distributed; lookup latency
+   should be small; traffic load should be evenly distributed; updates
+   of routing tables and redistribution of keys should be fast when
+   nodes join or leave the network.  They defined a node's "congestion"
+   to be the probability that a lookup will traverse it.  Apart from its
+   optimal de Bruijn diameter, they highlighted D2B's merits: a constant
+   expected update time when nodes join and leave (O(log n) with high
+   probability (w.h.p.)); the expected node congestion is O((log n)/n)
+   (O(((log n)^2)/n) w.h.p.) [345].  D2B's resilience was discussed only
+   in passing.
+
+   Koorde extends Chord to attain the optimal de Bruijn degree/diameter
+   trade-off above [37].  Unlike D2B, Koorde does not constrain the
+   selection of node identifiers.  Also unlike D2B, it caters to
+   concurrent joins, by extension of Chord's functionality.  Kaashoek
+   and Karger investigated Koorde's resilience to a rather harsh failure
+   scenario: "in order for a network to stay connected when all nodes
+   fail with probability of 1/2, some nodes must have degree
+
+
+
+Risson & Moors               Informational                     [Page 30]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   omega(log n)" [37].  They sketched a mechanism to increase Koorde's
+   degree for this more stringent fault tolerance, losing de Bruijn's
+   constant degree advantage.  Similarly, to achieve a constant-factor
+   load balance, Koorde would have to sacrifice its degree optimality.
+   They suggested that the ability to trade the degree, and hence the
+   maintenance overhead, against the expected hop count may be important
+   for churning systems.  They also identified an open problem: find a
+   load-balanced, degree optimal DHT.  Datta, Girdzijauskas, et al.
+   showed that for arbitrary key distributions, de Bruijn graphs fail to
+   meet the dual goals of load balancing and search efficiency [346].
+   They posed the question, "(Is there) a constant routing table sized
+   DHT which meets the conflicting goals of storage load balancing and
+   search efficiency for an arbitrary and changing key distribution?"
+
+   Distance Halving was also inspired by de Bruijn [336] and shares its
+   optimal diameter.  Naor and Wieder argued for a two-step
+   "continuous-discrete" approach for its design.  The correctness of
+   its algorithms is proven in a continuous setting.  The algorithms are
+   then mapped to a discrete space.  The source x and target y are
+   points on the continuous interval [0,1).  Data items are hashed to
+   this same interval.  <str> is a string that determines how messages
+   leave any point on the ring: if bit t of the string is 0, the left
+   leg is taken; if it is 1, the right leg is taken.  <str> increases by
+   one bit each hop, giving a sequence by which to step around the ring.
+   A lookup has two phases.  In the first, the lookup message containing
+   the source, target, and the random string hops toward the midpoint of
+   the source and target.  On each hop, the distance between <str>(x)
+   and <str>(y) is halved, by virtue of the specific 'left' and 'right'
+   functions.  In the second phase, the message steps 'backward' from
+   the midpoint to the target, removing the last bit in <str> at each
+   hop. 'Join' and 'leave' algorithms were outlined but there was no
+   consideration of recovery times or message load on churn.  Using the
+   Distance Halving properties, the authors devised a caching scheme to
+   relieve congestion in a large P2P network.  They have also modified
+   the algorithm to be more robust in the presence of random faults
+   [132].
+
+   Solid comparisons of DHT resilience are scarce, but Loguinov, Kumar,
+   et al. give just that in their ODRI paper [36].  They compare Chord,
+   CAN, and de Bruijn in terms of routing performance, graph expansion
+   and clustering.  At the outset, they give the optimal diameter (the
+   maximum hop count between any two nodes in the graph) and average hop
+   count for graphs of fixed degree.  De Bruijn graphs converge to both
+   optima, and outperform Chord and CAN on both counts.  These optima
+   impact both delay and aggregate lookup load.  They present two
+   clustering measures (edge expansion and node expansion), which are
+   interesting for resilience.  Unfortunately, after decades of de
+   Bruijn research, they have no exact solution.  De Bruijn was shown to
+
+
+
+Risson & Moors               Informational                     [Page 31]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   be superior in terms of path overlap - "de Bruijn automatically
+   selects backup paths that do not overlap with the best shortest path
+   or with each other" [36].
+
+3.5.6.  Skip Graphs
+
+   Skip Graphs have been pursued by two research camps [38, 41].  They
+   augment the earlier Skip Lists [347, 348].  Unlike earlier balanced
+   trees, the Skip List is probabilistic -- its insert and delete
+   operations do not require tree rearrangements and so are faster by a
+   constant factor.  The Skip List consists of layers of ordered linked
+   lists.  All nodes participate in the bottom layer 0 list.  Some of
+   these nodes participate in the layer 1 list with some fixed
+   probability.  A subset of layer 1 nodes participate in the layer 2
+   list, and so on.  A lookup can proceed quickly through the list by
+   traversing the sparse upper layers until it is close to, or at, the
+   target.  Unfortunately, nodes in the upper layers of a Skip List are
+   potential hot spots and single points of failure.  Unlike Skip Lists,
+   Skip Graphs provide multiple lists at each level for redundancy, and
+   every node participates in one of the lists at each level.
+
+   Each node in a Skip Graph has theta(log n) neighbours on average,
+   like some of the preceding DHTs.  The Skip Graph's primary edge over
+   the DHTs is its support for prefix and proximity search.  DHTs hash
+   objects to a random point in the graph.  Consequently, they give no
+   guarantees over where the data is stored.  Nor do they guarantee that
+   the path to the data will stay within the one administration as far
+   as possible [38].  Skip graphs, on the other hand, provide for
+   location-sensitive name searches.  For example, to find the document
+   docname on the node user.company.com, the Skip Graph might step
+   through its ordered lists for the prefix com.company.user [38].
+   Alternatively, to find an object with a numeric identifier, an
+   algorithm might search the lowest layer of the Skip Graph for the
+   first digit, the next layer for the next digit, in the same vein
+   until all digits are resolved.  Being ordered, Skip Graphs also
+   facilitate range searches.  In each of these examples, the Skip Graph
+   can be arranged such that the path to the target, as far as possible,
+   stays within an administrative boundary.  If one administration is
+   detached from the rest of the Skip Graph, routing can continue within
+   each of the partitions.  Mechanisms have been devised to merge
+   disconnected segments [157], though at this stage, segments are re-
+   merged one at a time.  A parallel merge algorithm has been flagged
+   for future work.
+
+   The advantages of Skip Graphs come at a cost.  To be able to provide
+   range queries and data placement flexibility, Skip Graph nodes
+   require many more pointers than their DHT counterparts.  An increased
+   number of pointers implies increased maintenance traffic.  Another
+
+
+
+Risson & Moors               Informational                     [Page 32]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   shortcoming of at least one of the early proposals was that no
+   algorithm was given to assign keys to machines.  Consequently, there
+   are no guarantees on system-wide load balancing or on the distance
+   between adjacent keys [100].  Aspnes, Kirsch, et al. have recently
+   devised a scheme to reduce the inter-machine pointer count from
+   O(mlogm), where m is the number of data elements, to O(nlog n), where
+   n is the number of nodes [100].  They proposed a two-layer scheme --
+   one layer for the Skip Graph itself and the second 'bucket layer'.
+   Each machine is responsible for a number of buckets and each bucket
+   elects a representative key.  Nodes locally adjust their load.  They
+   accept additional keys if they are below their threshold or disperse
+   keys to nearby nodes if they are above threshold.  There appear to be
+   numerous open issues: simulations have been done but analysis is
+   outstanding; mechanisms are required to handle the arrival and
+   departure of nodes; there were only brief hints as to how to handle
+   nodes with different capacities.
+
+4.  Semantic Index
+
+   Semantic indexes capture object relationships.  While the semantic-
+   free methods (DHTs) have firmer theoretic foundations and guarantee
+   that a key can be found if it exists, they do not capture the
+   relationships between the document name and its content or metadata
+   on their own.  Semantic P2P designs do.  However, since their design
+   is often driven by heuristics, they may not guarantee that scarce
+   items will be found.
+
+   So what might the semantically indexed P2Ps add to an already crowded
+   field of distributed information architectures?  At one extreme,
+   there are the distributed relational database management systems
+   (RDBMSs), with their strong consistency guarantees [284].  They
+   provide strong data independence, the flexibility of SQL queries, and
+   strong transactional semantics -- Atomicity, Consistency, Isolation
+   and Durability (ACID) [349].  They guarantee that the query response
+   is complete -- all matching results are returned.  The price is
+   performance.  They scale to perhaps 1000 nodes, as evidenced in
+   Mariposa [350, 351], or require query caching front ends to constrain
+   the load [284].  Database research has "arguably been cornered into
+   traditional, high-end, transactional applications" [72].  Then there
+   are distributed file systems, like the Network File System (NFS) or
+   the Serverless Network File Systems (xFS), with little data
+   independence, low-level file retrieval interfaces, and varied
+   consistency [284].  Today's eclectic mix of Content Distribution
+   Networks (CDNs) generally deload primary servers by redirecting Web
+   requests to a nearby replica.  Some intercept the HTTP requests at
+   the DNS level and then use consistent hashing to find a replica [23].
+   Since this same consistent hashing was a forerunner to the DHT
+
+
+
+
+Risson & Moors               Informational                     [Page 33]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   approaches above, CDNs are generally constrained to the same simple
+   key lookups.
+
+   The opportunity for semantically indexed P2Ps, then, is to provide:
+
+   a) graduated data independence, consistency, and query flexibility,
+      and
+
+   b) probabilistically complete query responses, across
+
+   c) very large numbers of low-cost, geographically distributed,
+      dynamic nodes.
+
+4.1.  Keyword Lookup
+
+   P2P keyword lookup is best understood by considering the structure of
+   the underlying index and the algorithms by which queries are routed
+   over that index.  Figure 3 summarizes the following paragraphs by
+   classifying the keyword query algorithms, index structures, and
+   metrics.  The research has largely focused on scalability, not
+   dependability.  There have been very few studies that quantify the
+   impact of network churn.  One exception is the work by Chawathe, et
+   al. on the Gia system [61].  Gia's combination of algorithms from
+   Figure 3 (receiver-based flow control, biased random walk, and one-
+   hop replication) gave 2-4 orders of magnitude improvement in query
+   success rates in churning networks.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 34]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   QUERY
+   Query routing
+     Flooding: Peers only index local files so queries must propagate
+       widely [4]
+     Policy-based: Choice of the next hop node: random; most/least
+       recently used; most files shared; most results [265, 352]
+     Random walks: Parallel [67] or biased random walks [61, 66]
+   Query forwarding
+     Iterative: Nodes perform iterative unicast searches of ultrapeers,
+       until the desired number of results is achieved.  See Gnutella
+       UDP Extension for Scalable Searches (GUESS) [265, 353]
+     Recursive
+   Query flow control
+     Receiver-controlled: Receivers grant query tokens to senders, so
+       as to avoid overload [61]
+     Reactive: sender throttles queries when it notices receivers are
+       discarding packets [61, 66]
+     Dynamic Time To Live: In the Dynamic Query Protocol, the sender
+       adjusts the time-to-live on each iteration based on the number
+       of results received, the number of connections left, and the
+       number of nodes already theoretically reached by the search [354]
+
+   INDEX
+   Distribution
+     Compression: Leaf nodes periodically send ultrapeers compressed
+       query routing tables, as in the Query Routing Protocol [260]
+     One hop replication: Nodes maintain an index of content on their
+       nearest neighbors [61, 352]
+   Partitioning
+     By document [210]
+     By keyword: Use an inverted list to find a matching document,
+       either locally or at another peer [21].  Partition by keyword
+       sets [355]
+     By document and keyword: Also called Multi-Level Partitioning [21]
+
+   METRIC
+   Query load: Queries per second per node/link [65, 265]
+   Degree: The number of links per node [66, 352].  Early P2P networks
+     approximated power-law networks, where the number of nodes with L
+     links is proportional to L^(-k), where k is a constant [65]
+   Query delay: Reported in terms of time and hop count [61, 66]
+   Query success rate: The "Collapse Point" is the per-node query rate
+     at which the query success rate drops below 90% [61].  See
+     also [61, 265, 352].
+
+                  Figure 3: Keyword Lookup in P2P Systems
+
+
+
+
+
+Risson & Moors               Informational                     [Page 35]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+4.1.1.  Gnutella Enhancements
+
+   Perhaps the most widely referenced P2P system for simple keyword
+   match is Gnutella [4].  Gnutella queries contain a string of
+   keywords.  Gnutella peers answer when they have files whose names
+   contain all the keywords.  As discussed in Section 2.1, early
+   versions of Gnutella did not forward the document index.  Queries
+   were flooded and peers searched their own local indexes for filename
+   matches.  An early review highlighted numerous areas for improvement
+   [65].  It was estimated that the query traffic alone from 50,000
+   early-generation Gnutella nodes would amount to 1.7% of the total
+   U.S. Internet backbone traffic at December 2000 levels.  It was
+   speculated that high-degree Gnutella nodes would impede
+   dependability.  An unnecessarily high percentage of Gnutella traffic
+   crossed Autonomous System (AS) boundaries -- a locality mechanism may
+   have found suitable nearby peers.
+
+   Fortunately, there have since been numerous enhancements within the
+   Gnutella Developer Forum.  At the time of writing, it has been
+   reported that Gnutella has almost 350,000 unique hosts, of which
+   nearly 90,000 accept incoming connections [356].  One of the main
+   improvements is that an index of filename keywords, called the Query
+   Routing Table (QRT), can now be forwarded from 'leaf peers' to its
+   'ultrapeers' [260].  Ultrapeers can then ensure that the leaves only
+   receive queries for which they have a match, dramatically reducing
+   the query traffic at the leaves.  Ultrapeers can have connections to
+   many leaf nodes (~10-100) and a small number of other ultrapeers
+   (<10) [260].  Originally, a leaf node's QRT was not forwarded by the
+   parent ultrapeer to other ultrapeers.  More recently, there has been
+   a proposal to distribute aggregated QRTs amongst ultrapeers [357].
+   To further limit traffic, QRTs are compressed by hashing, according
+   to the Query Routing Protocol (QRP) specification [281].  This same
+   specification claims QRP may reduce Gnutella traffic by orders of
+   magnitude, but cautions that simulation is required before mass
+   deployment.  A known shortcoming of QRP was that the extent of query
+   propagation was independent of the popularity of the search terms.
+   The Dynamic Query Protocol addressed this [358].  It required leaf
+   nodes to send single queries to high-degree ultrapeers that adjust
+   the queries' time-to-live (TTL) bounds according to the number of
+   received query results.  An earlier proposal, called the Gnutella UDP
+   Extension for Scalable Searches (GUESS) [353], similarly aimed to
+   reduce the number of queries for widely distributed files.  GUESS
+   reuses the non-forwarding idea (Section 2).  A GUESS peer repeatedly
+   queries single ultrapeers with a TTL of 1, with a small timeout on
+   each query to limit load.  It chooses the number of iterations and
+   selects ultrapeers so as to satisfy its search needs.  For
+   adaptability, a small number of experimental Gnutella nodes have
+
+
+
+
+Risson & Moors               Informational                     [Page 36]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   implemented eXtensible Markup Language (XML) schemas for richer
+   queries [359, 360].  None of the above Gnutella proposals explicitly
+   assess robustness.
+
+   The broader research community has recently been leveraging aspects
+   of the Gnutella design.  Lv, Ratnasamy, et al. exposed one assumption
+   implicit in some of the early DHT work -- that designs "such as
+   Gnutella are inherently not scalable, and therefore should be
+   abandoned" [66].  They argued that by making better use of the more
+   powerful peers, Gnutella's scalability issues could be alleviated.
+   Instead of its flooding mechanism, they used random walks.  Their
+   preliminary design to bias random walks towards high capacity nodes
+   did not go as far as the ultrapeer proposals in that the indexes did
+   not move to the high-capacity nodes.  Chawathe, Ratnasamy, et al.
+   chose to extend the Gnutella design with their Gia system, in
+   response to the perceived shortcomings of DHTs in Section 1.2 [61].
+   Compared to the early Gnutella designs, they incorporated several
+   novel features.  They devise a topology adaptation algorithm so that
+   most peers are attached to high-degree peers.  They use a random walk
+   search algorithm, in lieu of flooding, and bias the query load
+   towards higher-degree peers.  For 'one-hop replication', they require
+   all nodes to keep pointers to content on adjacent peers.  To
+   implement a receiver-controlled token-based flow control, a peer must
+   have a token from its neighbouring peer before it sends a query to
+   it.  Chawathe, Ratnasamy, et al. show by simulations that the
+   combination of these features provides a scalability improvement of
+   three to five orders of magnitude over Gnutella "while retaining
+   significant robustness".  The main robustness metrics they used were
+   the 'collapse point' query rate (the per-node query rate at which the
+   successful query rate falls below 90%) and the average hop count
+   immediately prior to collapse.  Their comparison with Gnutella did
+   not take into account the Gnutella enhancements above -- this was
+   left as future work.  Castro, Costa, and Rowstron argued that if
+   Gnutella were built on top of a structured overlay, then both the
+   query and overlay maintenance traffic could be reduced [259].  Yang,
+   Vinograd, et al. explore various policies for peer selection in the
+   GUESS protocol, since the issue is left open in the original proposal
+   [265].  For example, the peer initiating the query could choose peers
+   that have been "most recently used" or that have the "most files
+   shared".  Various policy pitfalls are identified.  For example, good
+   peers could be overloaded, victims of their own success.
+   Alternatively, malicious peers could encourage the querying peer to
+   try inactive peers.  They conclude that a "most results" policy gives
+   the best balance of robustness and efficiency.  Like Castro, Costa,
+   and Rowstron, they concentrated on the static network scenario.
+   Cholvi, Felber, et al. very briefly describe how similar "least
+   recently used" and "most often used" heuristics can be used by a peer
+   to select peer 'acquaintances' [352].  They were motivated by the
+
+
+
+Risson & Moors               Informational                     [Page 37]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   congestion associated with Gnutella's TTL-limited flooding.
+   Recognizing that the busiest peers can quickly become overloaded
+   central hubs for the entire network, they limit the number of
+   acquaintances for any given peer to 25.  They sketch a mechanism to
+   decrement a query's TTL multiple times when it traverses "interested
+   peers".  In summary, these Gnutella-related investigations are
+   characterized by a bias for high-degree peers and very short directed
+   query paths, a disdain for flooding, and concern about excessive load
+   on the 'better' peers.  Generally, the robustness analysis for
+   dynamic networks (content updates and node arrivals/departures)
+   remains open.
+
+4.1.2.  Partition-by-Document, Partition-by-Keyword
+
+   One aspect of P2P keyword search systems has received particular
+   attention: should the index be partitioned by document or by keyword?
+   The issue affects scalability.  To be partitioned by document, each
+   node has a local index of documents for which it is responsible.
+   Gnutella is a prime example.  Queries are generally flooded in
+   systems partitioned by document.  On the other hand, a peer may
+   assume responsibility for a set of keywords.  The peer uses an
+   inverted list to find a matching document, either locally or at
+   another peer.  If the query contains several keywords, inverted lists
+   may need to be retrieved from several different peers to find the
+   intersection [21].  The initial assessment by Li, Loo, et al. was
+   that the partition-by-document approach was superior [210].  For one
+   scenario of a full-text Web search, they estimated the communications
+   costs to be about six times higher than the feasible budget.
+   However, wanting to exploit prior work on inverted list intersection,
+   they studied the partition-by-keyword strategy.  They proposed
+   several optimizations that put the communication costs for a
+   partition-by-keyword system within an order of magnitude of
+   feasibility.  There had been a couple of prior papers that suggested
+   partitioned-by-keyword designs incorporate DHTs to map keywords to
+   peers [355, 361].  In Gnawali's Keyword-set Search System (KSS), the
+   index is partitioned by sets of keywords [355].  Terpstra, Behnel, et
+   al. point out that by keeping keyword pairs or triples, the number of
+   lists per document in KSS is squared or tripled [362].  Shi,
+   Guangwen, et al. interpreted the approximations of Li, Loo, et al. to
+   mean that neither approach is feasible on its own [21].  Their
+   Multi-Level Partitioning (MLP) scheme incorporates both partitioning
+   approaches.  They arrange nodes into a group hierarchy, with all
+   nodes in the single 'level 0' group, and with the same nodes sub-
+   divided into k logical subgroups on 'level 1'.  The subgroups are
+   again divided, level by level, until level l.  The inverted index is
+   partitioned by document between groups and by keyword within groups.
+   MLP avoids the query flooding normally associated with systems
+   partitioned by document, since a small number of nodes in each group
+
+
+
+Risson & Moors               Informational                     [Page 38]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   process the query.  It reduces the bandwidth overheads associated
+   with inverted list intersection in systems partitioned solely by
+   keyword, since groups can calculate the intersection independently
+   over the documents for which they are responsible.  MLP was overlaid
+   on SkipNet, per Section 3.5.6 [38].  Some initial analyses of
+   communications costs and query latencies were provided.
+
+4.1.3.  Partial Search, Exhaustive Search
+
+   Much of the research above addresses partial keyword search.
+   Daswani, et al. highlighted the open problem of efficient,
+   comprehensive keyword search [25].  How can exhaustive searches be
+   achieved without flooding queries to every peer in the network?
+   Terpstra, Behnel et al. couched the keyword search problem in
+   rendezvous terms: dynamic keyword queries need to 'meet' with static
+   document lists [362].  Their Bitzipper scheme is partitioned by
+   document.  They improved on full flooding by putting document
+   metadata on 2sqrt(n) nodes and forwarding queries through only
+   6sqrt(n) nodes.  They reported that Bitzipper nodes need only 1/166th
+   of the bandwidth of full-flooding Gnutella nodes for an exhaustive
+   search.  An initial comparison of query load was given.  There was
+   little consideration of either static or dynamic resilience; that is,
+   of nodes failing, of documents continually changing, or of nodes
+   continually joining and leaving the network.
+
+4.2.  Information Retrieval
+
+   The field of Information Retrieval (IR) has matured considerably
+   since its inception in the 1950s [363].  A taxonomy for IR models has
+   been formalized [262].  It consists of four elements: a
+   representation of documents in a collection; a representation of user
+   queries; a framework describing relationships between document
+   representations and queries; and a ranking function that quantifies
+   an ordering amongst documents for a particular query.  Three main
+   issues motivate current IR research -- information relevance, query
+   response time, and user interaction with IR systems.  The dominant IR
+   trends for searching large text collections are also threefold [262].
+   The size of collections is increasing dramatically.  More complicated
+   search mechanisms are being found to exploit document structure, to
+   accommodate heterogeneous document collections, and to deal with
+   document errors.  Compression is in favour -- it may be quicker to
+   search compact text or retrieve it from external devices.  In a
+   distributed IR system, query processing has four parts.  Firstly,
+   particular collections are targeted for the search.  Secondly,
+   queries are sent to the targeted collections.  Queries are then
+   evaluated at the individual collections.  Finally, results from the
+   collections are collated.
+
+
+
+
+Risson & Moors               Informational                     [Page 39]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   So how do P2P networks differ from distributed IR systems?  Bawa,
+   Manku, et al. presented four differences [62].  They suggested that a
+   P2P network is typically larger, with tens or hundreds of thousands
+   of nodes.  It is usually more dynamic, with node lifetimes measured
+   in hours.  They suggested that a P2P network is usually homogeneous,
+   with a common resource description language.  It lacks the
+   centralized "mediators" found in many IR systems that assume
+   responsibility for selecting collections, for rewriting queries, and
+   for merging ranked results.  These distinctions are generally aligned
+   with the peer characteristics in Section 1.  One might add that P2P
+   nodes display more symmetry -- peers are often both information
+   consumers and producers.  Daswani, Garcia-Molina, et al. pointed out
+   that, while there are IR techniques for ranked keyword search at
+   moderate scale, research is required so that ranking mechanisms are
+   efficient at the larger scale targeted by P2P designs [25].  Joseph
+   and Hoshiai surveyed several P2P systems using metadata techniques
+   from the IR toolkit [60].  They described an assortment of IR
+   techniques and P2P systems, including various metadata formats,
+   retrieval models, bloom filters, DHTs, and trust issues.
+
+   In the ensuing paragraphs, we survey P2P work that has incorporated
+   information retrieval models, particularly the Vector Model and the
+   Latent Semantic Indexing Model.  We omit the P2P work based on
+   Bayesian models.  Some have pointed to such work [60], but made no
+   explicit mention of the model [364].  One early paper on P2P
+   content-based image retrieval also leveraged the Bayesian model
+   [365].  For the former two models, we briefly describe the design,
+   then try to highlight robustness aspects.  On robustness, we are
+   again stymied for lack of prior work.  Indeed, a search across all
+   proceedings of the Annual ACM Conference on Research and Development
+   in Information Retrieval for the words "reliable", "available",
+   "dependable", or "adaptable" did not return any results at the time
+   of writing.  In contrast, a standard text on distributed database
+   management systems [366] contains a whole chapter on reliability.  IR
+   research concentrates on performance measures.  Common performance
+   measures include recall, the fraction of the relevant documents that
+   has been retrieved and precision, the fraction of the retrieved
+   documents that is relevant [262].  Ideally, an IR system would have
+   high recall and high precision.  Unfortunately techniques favouring
+   one often disadvantage the other [363].
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 40]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+4.2.1.  Vector Model (PlanetP, FASD, eSearch)
+
+   The vector model [367] represents both documents and queries as term
+   vectors, where a term could be a word or a phrase.  If a document or
+   query has a term, the weight of the corresponding dimension of the
+   vector is non-zero.  The similarity of the document and query vectors
+   gives an indication of how well a document matches a particular
+   query.
+
+   The weighting calculation is critical across the retrieval models.
+   Amongst the numerous proposals for the probabilistic and vector
+   models, there are some commonly recurring weighting factors [363].
+   One is term frequency.  The more a term is repeated in a document,
+   the more important the term is.  Another is inverse document
+   frequency.  Terms common to many documents give less information
+   about the content of a document.  Then there is document length.
+   Larger documents can bias term frequencies, so weightings are
+   sometimes normalized against document length.  The expression "TFIDF
+   weighting" refers to the collection of weighting calculations that
+   incorporate term frequency and inverse document frequency, not just
+   to one.  Two weighting calculations have been particularly dominant
+   -- Okapi [368] and pivoted normalization [369].  A distributed
+   version of Google's Pagerank algorithm has also been devised for a
+   P2P environment [370].  It allows incremental, ongoing Pagerank
+   calculations while documents are inserted and deleted.
+
+   A couple of early P2P systems leveraged the vector model.  Building
+   on the vector model, PlanetP divided the ranking problem into two
+   steps [215].  In the first, peers are ranked for the probability that
+   they have matching documents.  In the second, higher-priority peers
+   are contacted and the matching documents are ranked.  An Inverse Peer
+   Frequency, analogous to the Inverse Document Frequency, is used to
+   rank relevant peers.  To further constrain the query traffic, PlanetP
+   contacts only the first group of m peers to retrieve a relevant set
+   of documents.  In this way, it repeatedly contacts groups of m peers
+   until the top k document rankings are stable.  While the PlanetP
+   designers first quantified recall and precision, they also considered
+   reliability.  Each PlanetP peer has a global index with a list of all
+   other peers, their IP addresses, and their Bloom filters.  This large
+   volume of shared information needs to be maintained.  Klampanos and
+   Jose saw this as PlanetP's primary shortcoming [371].  Each Bloom
+   filter summarized the set of terms in the local index of each peer.
+   The time to propagate changes, be they new documents or peer
+   arrivals/departures, was studied by simulation for up to 1000 peers.
+   The reported propagation times were in the hundreds of seconds.
+   Design workarounds were required for PlanetP to be viable across
+   slower dial-up modem connections.  For future work, the authors were
+
+
+
+
+Risson & Moors               Informational                     [Page 41]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   considering some sort of hierarchy to scale to larger numbers of
+   peers.
+
+   A second early system using the vector model is the Fault-tolerant,
+   Adaptive, Scalable Distributed (FASD) search engine [283], which
+   extended the Freenet design (Section 2.3) for richer queries.  The
+   original Freenet design could find a document based on a globally
+   unique identifier.  Kronfol's design added the ability to search, for
+   example, for documents about "apples AND oranges NOT bananas".  It
+   uses a TFIDF weighting scheme to build a document's term vector.
+   Each peer calculates the similarity of the query vector and local
+   documents and forwards the query to the best downstream peer.  Once
+   the best downstream peer returns a result, the second-best peer is
+   tried, and so on.  Simulations with 1000 nodes gave an indication of
+   the query path lengths in various situations -- when routing queries
+   in a network with constant rates of node and document insertion, when
+   bootstrapping the network in a "worst-case" ring topology, or when
+   failing randomly and specifically selected peers.  Kronfol claimed
+   excellent average-case performance -- less than 20 hops to retrieve
+   the same top n results as a centralized search engine.  There were,
+   however, numerous cases where the worst-case path length was several
+   hundred hops in a network of only 1000 nodes.
+
+   In parallel, there have been some P2P designs based on the vector
+   model from the University of Rochester -- pSearch [9, 372] and
+   eSearch [373].  The early pSearch paper suggested a couple of
+   retrieval models, one of which was the Vector Space Model, to search
+   only the nodes likely to have matching documents.  To obtain
+   approximate global statistics for the TFIDF calculation, a spanning
+   tree was constructed across a subset of the peers.  For the m top
+   terms, the term-to-document index was inserted into a Content-
+   Addressable Network [334].  A variant that mapped terms to document
+   clusters was also suggested. eSearch is a hybrid of the partition-
+   by-document and partition-by-term approaches (Section 4.1.2) eSearch
+   nodes are primarily partitioned by term.  Each is responsible for the
+   inverted lists for some top terms.  For each document in the inverted
+   list, the node stores the complete term list.  To reduce the size of
+   the index, the complete term lists for a document are only kept on
+   nodes that are responsible for top terms in the document.  eSearch
+   uses the Okapi term weighting to select top terms.  It relies on the
+   Chord DHT [34] to associate terms with nodes storing the inverted
+   lists.  It also uses automatic query expansion.  This takes the
+   significant terms from the top document matches and automatically
+   adds them to the user's query to find additional relevant documents.
+   The eSearch performance was quantified in terms of search precision,
+   the number of retrieved documents, and various load-balancing
+   metrics.  Compared to the more common proposals for partitioning by
+
+
+
+
+Risson & Moors               Informational                     [Page 42]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   keywords, eSearch consumed 6.8 times the storage space to achieve
+   faster search times.
+
+4.2.2.  Latent Semantic Indexing (pSearch)
+
+   Another retrieval model used in P2P proposals is Latent Semantic
+   Indexing (LSI) [374].  Its key idea is to map both the document and
+   query vectors to a concept space with lower dimensions.  The starting
+   point is a t*N weighting matrix, where t is the total number of
+   indexed terms, N is the total number of documents, and the matrix
+   elements could be TFIDF rankings.  Using singular value
+   decomposition, this matrix is reduced to a smaller number of
+   dimensions, while retaining the more significant term-to-document
+   mappings.  Baeza-Yates and Ribeiro-Neto suggested that LSI's value is
+   a novel theoretic framework, but that its practical performance
+   advantage for real document collections had yet to be proven [262].
+   pSearch incorporated LSI [9].  By placing the indices for
+   semantically similar documents close in the network, Tang, Xu, et al.
+   touted significant bandwidth savings relative to the early full-
+   flooding variant of Gnutella [372].  They plotted the number of nodes
+   visited by a query.  They also explored the trade-off with accuracy,
+   the percentage match between the documents returned by the
+   distributed pSearch algorithm and those from a centralized LSI
+   baseline.  In a more recent update to the pSearch work, Tang,
+   Dwarkadas, et al. summarized LSI's shortcomings [375].  Firstly, for
+   large document collections, its retrieval quality is inherently
+   inferior to Okapi.  Secondly, singular value decomposition consumes
+   excessive memory and computation time.  Consequently, the authors
+   used Okapi for searching while retaining LSI for indexing.  With
+   Okapi, they selected the next node to be searched and selected
+   documents on searched nodes.  With LSI, they ensured that similar
+   documents are clustered near each other, thereby optimizing the
+   network search costs.  When retrieving a small number of top
+   documents, the precision of LSI+Okapi approached that of Okapi.
+   However, if retrieving a large number of documents, the LSI+Okapi
+   precision is inferior.  The authors want to improve this in future
+   work.
+
+4.2.3.  Small Worlds
+
+   The "small world" concept originally described how people are
+   interconnected by short chains of acquaintances [376].  Kleinberg was
+   struck by the algorithmic lesson of the small world, namely "that
+   individuals using local information are collectively very effective
+   at constructing short paths between two points in a social network"
+   [377].  Small world networks have a small diameter and a large
+   clustering coefficient (a large number of connections amongst
+   relevant nodes) [378].
+
+
+
+Risson & Moors               Informational                     [Page 43]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   The small world idea has had a limited impact on peer-to-peer
+   algorithms.  It has influenced only a few unstructured [62, 378-380]
+   and structured [344, 381] algorithms.  The most promising work on
+   "small worlds" in P2P networks are those concerned with the
+   information retrieval metrics, precision and recall [62, 378, 380].
+
+5.  Queries
+
+   Database research suggests directions for P2P research.  Hellerstein
+   observed that, while work on fast P2P indexes is well underway, P2P
+   query optimization remains a promising topic for future research
+   [23].  Kossman reviewed the state of the art of distributed query
+   processing, highlighting areas for future research: simulation and
+   query optimization for networks of tens of thousands of servers and
+   millions of clients; non-relational data types (e.g., XML, text, and
+   images); and partial query responses since on the Internet, "failure
+   is the rule rather than the exception" [19].  A primary motivation
+   for the P2P system, PIER, was to scale from the largest database
+   systems of a few hundred nodes to an Internet environment in which
+   there are over 160 million nodes [22].  Litwin and Sahri have also
+   considered ways to combine distributed hashing, more specifically the
+   Scalable Distributed Data Structures, with SQL databases, claiming to
+   be first to implement scalable distributed database partitioning
+   [382].  Motivated by the lack of transparent distribution in current
+   distributed databases, they measure query execution times for
+   Microsoft SQL servers aggregated by means of an SDDS layer.  One of
+   their starting assumptions was that it is too challenging to change
+   the SQL query optimizer.
+
+   Database research also suggests the approach to P2P research.
+   Researchers of database query optimization were divided between those
+   looking for optimal solutions in special cases and those using
+   heuristics to answer all queries [383].  Gribble, et al. cast query
+   optimization in terms of the data placement problem, which is to
+   "distribute data and work so the full query workload is answered with
+   lowest cost under the existing bandwidth and resource constraints"
+   [250].  They pointed out that even the static version of this problem
+   is NP-complete in P2P networks.  Consequently, research on massive,
+   dynamic P2P networks will likely progress using both strategies of
+   early database research - heuristics and special-case optimizations.
+
+   If P2P networks are going to be adaptable, if they are to support a
+   wide range of applications, then they need to accommodate many query
+   types [72].  Up to this point, we have reviewed queries for keys
+   (Section 3) and keywords (Sections 4.1. and 4.2).  Unfortunately, a
+   major shortcoming of the DHTs in Section 3.5 is that they primarily
+   support exact-match, single-key queries.  Skip Graphs support range
+   and prefix queries, but not aggregation queries.  Here we probe below
+
+
+
+Risson & Moors               Informational                     [Page 44]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   the language syntax to identify the open research issues associated
+   with more expressive P2P queries [25].  Triantafillou and Pitoura
+   observed the disparate P2P designs for different types of queries and
+   so outlined a unifying framework [76].  To classify queries, they
+   considered the number of relations (single or multiple), the number
+   of attributes (single or multiple), and the type of query operator.
+   They described numerous operators:  equality, range, join, and
+   "special functions".  The latter referred to aggregation (like sum,
+   count, average, minimum, and maximum), grouping and ordering.  The
+   following sections approximately fit their taxonomy -- range queries,
+   multi-attribute queries, join queries and aggregation queries.  There
+   has been some initial P2P work on other query types -- continuous
+   queries [20, 22, 73], recursive queries [22, 74], and adaptive
+   queries [23, 75].  For these, we defer to the primary references.
+
+5.1.  Range Queries
+
+   The support of efficient range predicates in P2P networks was
+   identified as an important open research issue by Huebsch, et al.
+   [22].  Range partitioning has been important in parallel databases to
+   improve performance, so that a transaction commonly needs data from
+   only one disk or node [22].  One type of range search, longest prefix
+   match, is important because of its prevalence in routing schemes for
+   voice and data networks alike.  In other applications, users may pose
+   broad, inexact queries, even though they require only a small number
+   of responses.  Consequently, techniques to locate similar ranges are
+   also important [77].  Various proposals for range searches over P2P
+   networks are summarized in Figure 4.  Since the Scalable Distributed
+   Data Structure (SDDS) has been an important influence on contemporary
+   Distributed Hash Tables (DHTs) [49-51], we also include ongoing work
+   on SDDS range searches.
+
+   PEER-TO-PEER (P2P)
+   Locality Sensitive Hashing (Chord) [77]
+   Prefix Hash Trees (unspecified DHT) [78, 79]
+   Space Filling Curves (CAN) [80]
+   Space Filling Curves (Chord) [81]
+   Quadtrees (Chord) [82]
+   Skip Graphs [38, 41, 83, 100]
+   Mercury [84]
+   P-Grid [85, 86]
+
+   SCALABLE DISTRIBUTED DATA STRUCTURES (SDDS)
+   RP*   [87, 88]
+
+       Figure 4: Solutions for Range Queries on P2P and SDDS Indexes
+
+
+
+
+
+Risson & Moors               Informational                     [Page 45]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   The papers on P2P range search can be divided into those that rely on
+   an underlying DHT (the first five entries in Figure 4) and those that
+   do not (the subsequent three entries).  Bharambe, Agrawal, et al.
+   argued that DHTs are inherently ill-suited to range queries [84].
+   The very feature that makes for their good load balancing properties,
+   randomized hash functions, works against range queries.  One possible
+   solution would be to hash ranges, but this can require a priori
+   partitioning.  If the partitions are too large, partitions risk
+   overload.  If they are too small, there may be too many hops.
+
+   Despite these potential shortcomings, there have been several range
+   query proposals based on DHTs.  If hashing ranges to nodes, it is
+   entirely possible that overlapping ranges map to different nodes.
+   Gupta, Agrawal, et al. rely on locality sensitive hashing to ensure
+   that, with high probability, similar ranges are mapped to the same
+   node [77].  They propose one particular family of locality sensitive
+   hash functions, called min-wise independent permutations.  The number
+   of partitions per node and the path length were plotted against the
+   total numbers of peers in the system.  For a network with 1000 nodes,
+   the hop count distribution was very similar to that of the exact-
+   matching Chord scheme.  Was it load-balanced?  For the same network
+   with 50,000 partitions, there were over two orders of magnitude
+   variation in the number of partitions at each node (first and
+   ninety-ninth percentiles).  The Prefix Hash Tree is a trie in which
+   prefixes are hashed onto any DHT.  The preliminary analysis suggests
+   efficient doubly logarithmic lookup, balanced load, and fault
+   resilience [78, 79].  Andrzejak and Xu were perhaps the first to
+   propose a mapping from ranges to DHTs [80].  They use one particular
+   Space Filling Curve, the Hilbert curve, over a Content Addressable
+   Network (CAN) construction (Section 3.5.3).  They maintain two
+   properties: nearby ranges map to nearby CAN zones; if a range is
+   split into two sub-ranges, then the zones of the sub-ranges partition
+   the zone of the primary range.  They plot path length and load proxy
+   measures (the total number of messages and nodes visited) for three
+   algorithms to propagate range queries: brute force, controlled
+   flooding, and directed controlled flooding.  Schmidt and Parashar
+   also advocated Space Filling Curves to achieve range queries over a
+   DHT [81].  However, they point out that, while Andrzejak and Xu use
+   an inverse Space Filling Curve to map a one-dimensional space to d-
+   dimensional zones, they map a d-dimensional space back to a one-
+   dimensional index.  Such a construction gives the ability to search
+   across multiple attributes (Section 5.2).  Tanin, Harwood, et al.
+   suggested quadtrees over Chord [82], and gave preliminary simulation
+   results for query response times.
+
+   Because DHTs are naturally constrained to exact-match, single-key
+   queries, researchers have considered other P2P indexes for range
+   searches.  Several were based on Skip Graphs [38, 41], which, unlike
+
+
+
+Risson & Moors               Informational                     [Page 46]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   the DHTs, do not necessitate randomizing hash functions and are
+   therefore capable of range searches.  Unfortunately, they are not
+   load balanced [83].  For example, in SkipNet [48], hashing was added
+   to balance the load -- the Skip Graph could support range searches or
+   load balancing, but not both.  One solution for load-balancing relies
+   on an increased number of 'virtual' servers [168] but, in their
+   search for a system that can both search for ranges and balance
+   loads, Bharambe, Agrawal, et al. rejected the idea [84].  The virtual
+   servers work assumed load imbalance stems from hashing; that is, by
+   skewed data insertions and deletions.  In some situations, the
+   imbalance is triggered by a skewed query load.  In such
+   circumstances, additional virtual servers can increase the number of
+   routing hops and increase the number of pointers that a Skip Graph
+   needs to maintain.  Ganesan, Bawa, et al. devised an alternate method
+   to balance load [83].  They proposed two Skip Graphs, one to index
+   the data itself and the other to track load at each node in the
+   system.  Each node is able to determine the load on its neighbours
+   and the most (least) loaded nodes in the system.  They devise two
+   algorithms: NBRADJUST balances load on neighbouring nodes; using
+   REORDER, empty nodes can take over some of the tuples on heavily
+   loaded nodes.  Their simulations focus on skewed storage load, rather
+   than on skewed query loads, but they surmise that the same approach
+   could be used for the latter.
+
+   Other proposals for range queries avoid both the DHT and the Skip
+   Graph.  Bharambe, Agrawal, et al. distinguish their Mercury design by
+   its support for multi-attribute range queries and its explicit load
+   balancing [84].  In Mercury, nodes are grouped into routing hubs,
+   each of which is responsible for various query attributes.  While it
+   does not use hashing, Mercury is loosely similar to the DHT
+   approaches: nodes within hubs are arranged into rings, like Chord
+   [34]; for efficient routing within hubs, k long-distance links are
+   used, like Symphony [381].  Range lookups require O(((log n)^2)/k)
+   hops.  Random sampling is used to estimate the average load on nodes
+   and to find the parts of the overlay that are lightly loaded.
+   Whereas Symphony assumed that nodes are responsible for ranges of
+   approximately equal size, Mercury's random sampling can determine the
+   location of the start of the range, even for non-uniform ranges [84].
+   P-Grid [42] does provide for range queries, by virtue of the key
+   ordering in its tree structures.  Ganesan, Bawa, et al. critiqued its
+   capabilities [83]: P-Grid assumes fixed-capacity nodes; there was no
+   formal characterization of imbalance ratios or balancing costs; every
+   P-Grid periodically contacts other nodes for load information.
+
+   The work on Scalable Distributed Data Structures (SDDSs) has
+   progressed in parallel with P2P work and has addressed range queries.
+   Like the DHTs above, the early SDDS Linear Hashing (LH*) schemes were
+   not order-preserving [52].  To facilitate range queries, Litwin,
+
+
+
+Risson & Moors               Informational                     [Page 47]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Niemat, et al. devised a Range Parititioning variant, RP* [87].
+   There are options to dispense with the index, to add indexes to
+   clients, and to add them to servers.  In the variant without an
+   index, every query is issued via multicasting.  The other variants
+   also use some multicasting.  The initial RP* paper suggested
+   scalability to thousands of sites, but a more recent RP* simulation
+   was capped at 140 servers [88].  In that work, Tsangou, Ndiaye, et
+   al. investigated TCP and UDP mechanisms by which servers could return
+   range query results to clients.  The primary metrics were search and
+   response times.  Amongst the commercial parallel database management
+   systems, they reported that the largest seems only to scale to 32
+   servers (SQL Server 2000).  For future work, they planned to explore
+   aggregation of query results, rather than establishing a connection
+   between the client and every single server with a response.
+
+   All in all, it seems there are numerous open research questions on
+   P2P range queries.  How realistic is the maintenance of global load
+   statistics considering the scale and dynamism of P2P networks?
+   Simulations at larger scales are required.  Proposals should take
+   into account both the storage load (insert and delete messages) and
+   the query load (lookup messages).  Simplifying assumptions need to be
+   attacked.  For example, how well do the above solutions work in
+   networks with heterogeneous nodes, where the maximum message loads
+   and index sizes are node-dependent?
+
+5.2.  Multi-Attribute Queries
+
+   There has been some work on multi-attribute P2P queries.  As late as
+   September 2003, it was suggested that there has not been an efficient
+   solution [76].
+
+   Again, an early significant work on multi-attribute queries over
+   aggregated commodity nodes germinated amongst SDDSs.  k-RP* [89] uses
+   the multi-dimensional binary search tree (or k-d tree, where k
+   indicates the number of dimensions of the search index) [384].  It
+   builds on the RP* work from the previous section and inherits their
+   capabilities for range search and partial match.  Like the other
+   SDDSs, k-RP* indexes can fit into RAM for very fast lookup.  For
+   future work, Litwin and Neimat suggested a) a formal analysis of the
+   range search termination algorithm and the k-d paging algorithm, b) a
+   comparison with other multi-attribute data structures (quad-trees and
+   R-trees) and c) exploration of query processing, concurrency control,
+   and transaction management for k-RP* files [89].  On the latter
+   point, others have considered transactions to be inconsequential to
+   the core problem of supporting more complex queries in P2P networks
+   [72].
+
+
+
+
+
+Risson & Moors               Informational                     [Page 48]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   In architecting their secure wide-area Service Discovery Service
+   (SDS), Hodes, Czerwinski, et al. considered three possible designs
+   for multi-criteria search -- Centralization, Mapping and Flooding
+   [90].  These correlate to the index classifications of Section 2 --
+   Central, Distributed, and Local.  They discounted the centralized,
+   Napster-like index for its risk of a single point of failure.  They
+   considered the hash-based mappings of Section 3, but concluded that
+   it would not be possible to adequately partition data.  A document
+   satisfying many criteria would be wastefully stored in many
+   partitions.  They rejected full flooding for its lack of scalability.
+   Instead, they devised a query filtering technique, reminiscent of
+   Gnutella's query routing protocol (Section 4.1).  Nodes push
+   proactive summaries of their data rather than waiting for a query.
+   Summaries are aggregated and stored throughout a server hierarchy, to
+   guide subsequent queries.  Some initial prototype measurements were
+   provided for total load on the system, but not for load distribution.
+   They put several issues forward for future work.  The indexing needs
+   to be flexible to change according to query and storage workloads.  A
+   mesh topology might improve on their hierarchic topology since query
+   misses would not propagate to root servers.  The choice is analogous
+   to BGP meshes and DNS trees.
+
+   More recently, Cai, Frank, et al. devised the Multi-Attribute
+   Addressable Network (MAAN) [91].  They built on Chord to provide both
+   multi-attribute and range queries, claiming to be the first to
+   service both query types in a structured P2P system.  Each MAAN node
+   has O(log n) neighbours, where N is the number of nodes.  MAAN
+   multi-attribute range queries require O(log n+N*Smin) hops, where
+   Smin is the minimum range selectivity across all attributes.
+   Selectivity is the ratio of the query range to the entire identifier
+   range.  The paper assumed that a locality preserving hash function
+   would ensure balanced load.  Per Section 5.1, the arguments by
+   Bharambe, Agrawal, et al. have highlighted the shortcomings of this
+   assumption [84].  MAAN required that the schema must be fixed and
+   known in advance -- adaptable schemas were recommended for subsequent
+   attention.  The authors also acknowledged that there is a selectivity
+   breakpoint at which full flooding becomes more efficient than their
+   scheme.  This begs for a query resolution algorithm that adapts to
+   the profile of queries.  Cai and Frank followed up with RDFPeers
+   [55].  They differentiate their work from other RDF proposals by a)
+   guaranteeing to find query results if they exist and b) removing the
+   requirement of prior definition of a fixed schema.  They hashed
+   <subject, predicate, object> triples onto the MAAN and reported
+   routing hop metrics for their implementation.  Load imbalance across
+   nodes was reduced to less than one order of magnitude, but the
+   specific measure was the number of triples stored per node - skewed
+   query loads were not considered.  They plan to improve load balancing
+   with the virtual servers of Section 5.1 [168].
+
+
+
+Risson & Moors               Informational                     [Page 49]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+5.3.  Join Queries
+
+   Two research teams have done some initial work on P2P join
+   operations.  Harren, Hellerstein, et al. initially described a
+   three-layer architecture -- storage, DHT and query processing.  They
+   implemented the join operation by modifying an existing Content
+   Addressable Network (CAN) simulator, reporting "significant hot-spots
+   in all dimensions: storage, processing, and routing" [72].  They
+   progressed their design more recently in the context of PIER, a
+   distributed query engine based on CAN [22, 385].  They implemented
+   two equi-join algorithms.  In their design, a key is constructed from
+   the "namespace" and the "resource ID".  There is a namespace for each
+   relation and the resource ID is the primary key for base tuples in
+   that relation.  Queries are multicast to all nodes in the two
+   namespaces (relations) to be joined.  Their first algorithm is a DHT
+   version of the symmetric hash join.  Each node in the two namespaces
+   finds the relevant tuples and hashes them to a new query namespace.
+   The resource ID in the new namespace is the concatenation of join
+   attributes.  In the second algorithm, called "fetch matches", one of
+   the relations is already hashed on the join attributes.  Each node in
+   the second namespace finds tuples matching the query and retrieves
+   the corresponding tuples from the first relation.  They leveraged two
+   other techniques, namely the symmetric semi-join rewrite and the
+   Bloom filter rewrite, to reduce the high bandwidth overheads of the
+   symmetric hash join.  For an overlay of 10,000 nodes, they simulated
+   the delay to retrieve tuples and the aggregate network bandwidth for
+   these four schemes.  The initial prototype was on a cluster of 64
+   PCs, but it has more recently been expanded to PlanetLab.
+
+   Triantafillou and Pitoura considered multicasting to large numbers of
+   peers to be inefficient [76].  They therefore allocated a limited
+   number of special peers, called range guards.  The domain of the join
+   attributes was divided, one partition per range guard.  Join queries
+   were sent only to range guards, where the query was executed.
+   Efficient selection of range guards and a quantitive evaluation of
+   their proposal were left for future work.
+
+5.4.  Aggregation Queries
+
+   Aggregation queries invariable rely on tree-structures to combine
+   results from a large number of nodes.  Examples of aggregation
+   queries are Count, Sum, Maximum, Minimum, Average, Median, and Top-K
+   [92, 386, 387].  Figure 5 summarizes the tree and query
+   characteristics that affect dependability.
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 50]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   Tree type: Doesn't use DHT [92], use internal DHT trees [95], use
+      independent trees on top of DHTs
+   Tree repair: Periodic [93], exceptional [32]
+   Tree count: One per key, one per overlay [56]
+   Tree flexibility: Static [92], dynamic
+
+   Query interface: install, update, probe [98]
+   Query distribution: multicast [98], gossip [92]
+   Query applications: leader election, voting, resource location,
+      object placement and error recovery [98, 388]
+   Query semantics
+      Consistency: Best-effort, eventual [92], snapshot / interval /
+         single-site validity [99]
+      Timeliness [388]
+      Lifetime: Continuous [97, 99], single-shot
+      No. attributes: Single, multiple
+   Query types: Count, sum, maximum, minimum, average, median, top k
+      [92, 386, 387]
+
+          Figure 5: Aggregation Trees and Queries in P2P Networks
+
+   Key: Astrolabe [92]; Cone [93]; Distributed Approximative System
+   Information Service (DASIS) [95]; Scalable Distributed Information
+
+   Management System (SDIMS) [98]; Self-Organized Metadata Overlay
+   (SOMO) [56]; Wildfire [99]; Willow [32]; Newscast [97]
+
+   The fundamental design choices for aggregation trees relate to how
+   the overlay uses DHTs, how it repairs itself when there are failures,
+   how many aggregation trees there are, and whether the tree is static
+   or dynamic (Figure 5).  Astrolabe is one of the most influential P2P
+   designs included in Figure 5, yet it makes no use of DHTs [92].
+   Other designs make use of the internal trees of Plaxton-like DHTs.
+   Others build independent tree structures on top of DHTs.  Most of the
+   designs repair the aggregation tree with periodic mechanisms similar
+   to those used in the DHTs themselves.  Willow is an exception [32].
+   It uses a Tree Maintenance Protocol to "zip" disjoint aggregation
+   trees together when there are major failures.  Yalagandula and Dahlin
+   found reconfigurations at the aggregation layer to be costly,
+   suggesting more research on techniques to reduce the cost and
+   frequency of such reconfigurations [98].  Many of the designs use
+   multiple aggregation trees, each rooted at the DHT node responsible
+   for the aggregation attribute.  On the other hand, the Self-Organized
+   Metadata Overlay [56] uses a single tree and is vulnerable to a
+   single point of failure at its root.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 51]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   At the time of writing, researchers have just begun exploring the
+   performance of queries in the presence of churn.  Most designs are
+   for best-effort queries.  Bawa, et al. devised a better consistency
+   model, called Single-Site Validity [99] to qualify the accuracy of
+   results when there is churn.  Its price was a five-fold increase in
+   the message load, when compared to an efficient but best-effort
+   Spanning Tree.  Gossip mechanisms are resilient to churn, but they
+   delay aggregation results and incur high message cost for aggregation
+   attributes with small read-to-write ratios.
+
+6.  Security Considerations
+
+   An initial list of references to research on P2P security is given in
+   Figure 1, Section 1.  This document addresses P2P search.  P2P
+   storage, security, and applications are recommended for further
+   investigation in Section 8.
+
+7.  Conclusions
+
+   Research on peer-to-peer networks can be divided into four categories
+   -- search, storage, security and applications.  This critical survey
+   has focused on search methods.  While P2P networks have been
+   classified by the existence of an index (structured or unstructured)
+   or the location of the index (local, centralized, and distributed),
+   this survey has shown that most have evolved to have some structure,
+   whether it is indexes at superpeers or indexes defined by DHT
+   algorithms.  As for location, the distributed index is most common.
+   The survey has characterized indexes as semantic and semantic-free.
+   It has also critiqued P2P work on major query types.  While much of
+   it addresses work from 2000 or later, we have traced important
+   building blocks from the 1990s.
+
+   The initial motivation in this survey was to answer the question,
+   "How robust are P2P search networks?"  The question is key to the
+   deployment of P2P technology.  Balakrishnan, Kaashoek, et al. argued
+   that the P2P architecture is appealing: the startup and growth
+   barriers are low; they can aggregate enormous storage and processing
+   resources; "the decentralized and distributed nature of P2P systems
+   gives them the potential to be robust to faults or intentional
+   attacks" [18].  If P2P is to be a disruptive technology in
+   applications other than casual file sharing, then robustness needs to
+   be practically verified [20].
+
+   The best comparative research on P2P dependability has been done in
+   the context of Distributed Hash Tables (DHTs) [291].  The entire body
+   of DHT research can be distilled to four main observations about
+   dependability (Section 3.2).  Firstly, static dependability
+   comparisons show that no O(log n) DHT geometry is significantly more
+
+
+
+Risson & Moors               Informational                     [Page 52]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   dependable than the other O(log n) geometries.  Secondly, dynamic
+   dependability comparisons show that DHT dependability is sensitive to
+   the underlying topology maintenance algorithms (Figure 2).  Thirdly,
+   most DHTs use O(log n) geometries to suit ephemeral nodes, whereas
+   the O(1) hop DHTs suit stable nodes - they deserve more research
+   attention.  Fourthly, although not yet a mature science, the study of
+   DHT dependability is helped by recent simulation tools that support
+   multiple DHTs [299].
+
+   We make the following four suggestions for future P2P research:
+
+   1) Complete the companion P2P surveys for storage, security, and
+      applications.  A rough outline has been suggested in Figure 1,
+      along with references.  The need for such surveys was highlighted
+      within the peer-to-peer research group of the Internet Research
+      Task Force (IRTF) [17].
+
+   2) P2P indexes are maturing.  P2P queries are embryonic.  Work on
+      more expressive queries over P2P indexes started to gain momentum
+      in 2003, but remains fraught with efficiency and load issues.
+
+   3) Isolate the low-level mechanisms affecting robustness.  There is
+      limited value in comparing robustness of DHT geometries (like
+      rings versus de Bruijn graphs), when robustness is highly
+      sensitive to underlying topology maintenance algorithms (Figure
+      2).
+
+   4) Build consensus on robustness metrics and their acceptable ranges.
+      This paper has teased out numerous measures that impinge on
+      robustness, for example, the median query path length for a
+      failure of x% of nodes, bisection width, path overlap, the number
+      of alternatives available for the next hop, lookup latency,
+      average live bandwidth (bytes/node/sec), successful routing rates,
+      the number of timeouts (caused by a finger pointing to a departed
+      node), lookup failure rates (caused by nodes that temporarily
+      point to the wrong successor during churn), and clustering
+      measures (edge expansion and node expansion).  Application-level
+      robustness metrics need to drive a consistent assessment of the
+      underlying search mechanics.
+
+8.  Acknowledgments
+
+   This document was adapted from a paper in Elsevier's Computer
+   Networks:
+
+      J. Risson & T. Moors, Survey of Research towards Robust Peer-to-
+      Peer Networks: Search Methods, Computer Networks 51(7)2007.
+
+
+
+
+Risson & Moors               Informational                     [Page 53]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   We thank Bill Yeager, Ali Ghodsi, and several anonymous reviewers for
+   thorough comments that significantly improved the quality of earlier
+   versions of this document.
+
+9.  References
+
+9.1.  Informative References
+
+   [1]   M. Roussopoulos, M. Baker, D. Rosenthal, T. Guili, P. Maniatis,
+         and J. Mogul, 2 P2P of Not 2 P2P?, The 3rd Int'l Workshop on
+         Peer-to-Peer Systems, February 26-27 2004.
+
+   [2]   A. Rowstron and P. Druschel, Pastry:  Scalable, distributed
+         object location and routing for large-scale peer-to-peer
+         systems, IFIP/ACM Middleware 2001, Nov 2001.
+
+   [3]   B. Yeager and B. Bhattacharjee, Peer-to-Peer Research Group
+         Charter, http://www.irtf.org/charters/p2prg.html (2003)
+
+   [4]   T. Klingberg and R. Manfredi, Gnutella 0.6, (2002)
+
+   [5]   I. Clarke, A Distributed Decentralised Information Storage and
+         Retrieval System, Undergraduate Thesis, 1999.
+
+   [6]   B. Zhao, J. Kubiatowicz, and A. Joseph, Tapestry:  an
+         infrastructure for fault-tolerant wide-area location and
+         routing, Report No. UCB/CSD-01-1141 2001.
+
+   [7]   I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Kaashoek,
+         F. Dabek, and H. Balakrishnan, Chord:  A scalable peer-to-peer
+         lookup service for internet applications, Proc.  ACM SIGCOMM
+         2001 2001, pp. 149-160.
+
+   [8]   S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker,
+         A scalable content-addressable network, Proc. of the conf. on
+         Applications, technologies, architectures and protocols for
+         computer communications, August 27-31 2001, pp. 161-172.
+
+   [9]   C. Tang, Z. Xu, and M. Mahalingam, pSearch: information
+         retrieval in structured overlays, First Workshop on Hot Topics
+         in Networks. Also Computer Communication Review, Volume 33,
+         Number 1, January 2003, Oct 28-29 2002.
+
+   [10]  W. Nejdl, S. Decker, and W. Siberski, Edutella Project, RDF-
+         based Metadata Infrastructure for P2P Applications,
+         http://edutella.jxta.org/ (2003)
+
+
+
+
+
+Risson & Moors               Informational                     [Page 54]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [11]  K. Aberer and M. Hauswirth, Peer-to-peer information systems:
+         concepts and models, state-of-the-art, and future systems, ACM
+         SIGSOFT Software Engineering Notes, Proc. 8th European software
+         engineering conference held jointly with 9th ACM SIGSOFT
+         international symposium on foundations of software engineering
+         26 (5) (2001)
+
+   [12]  L. Zhou and R. van Renesse, P6P: a peer-to-peer approach to
+         internet infrastructure, The 3rd Int'l Workshop on Peer-to-Peer
+         Systems, February 26-27 2004.
+
+   [13]  Citeseer, Citeseer Scientific Literature Digital Library,
+         http://citeseer.ist.psu.edu/ (2004)
+
+   [14]  D. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne,
+         B. Richard, S. Rollins, and Z. Xu, Peer-to-Peer Computing, HP
+         Technical Report, HPL-2002-57 2002.
+
+   [15]  K. Aberer and M. Hauswirth, An overview on peer-to-peer
+         information systems, Workshop on Distributed Data and
+         Structures WDAS-2002 2002.
+
+   [16]  F. DePaoli and L. Mariani, Dependability in Peer-to-Peer
+         Systems, IEEE Internet Computing 8 (4) (2004) 54-61.
+
+   [17]  B. Yeager, Proposed research tracks, Email to the Internet
+         Research Task Force IRTF P2P Research Group, Nov 10 2003.
+
+   [18]  H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, and I.
+         Stoica, Looking up data in P2P systems, Communications of the
+         ACM 46 (2) (2003) 43-48.
+
+   [19]  D. Kossmann, The state of the art in distributed query
+         processing, ACM Computing Surveys 32 (4) (2000) 422-469.
+
+   [20]  B. Gedik and L. Liu, Reliable peer-to-peer information
+         monitoring through replication, Proc. 22nd Int'l Symp. on
+         Reliable Distributed Systems, 6-8 Oct 2003, pp. 56-65.
+
+   [21]  S.-M. Shi, Y. Guangwen, D. Wang, J. Yu, S. Qu, and M. Chen,
+         Making peer-to-peer keyword searching feasible using multi-
+         level partitioning, The 3rd Int'l Workshop on Peer-to-Peer
+         Systems, February 26-27 2004.
+
+   [22]  R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S.
+         Shenker, and I. Stoica, Querying the Internet with PIER, Proc.
+         29th Int'l Conf. on Very Large Databases VLDB'03, September
+         2003.
+
+
+
+Risson & Moors               Informational                     [Page 55]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [23]  J. M. Hellerstein, Toward network data independence, ACM SIGMOD
+         Record 32 (3) (2003) 34-40.
+
+   [24]  K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker,
+         and I. Stoica, The impact of DHT routing geometry on resilience
+         and proximity, Proc. 2003 conference on Applications,
+         Technologies, Architectures and Protocols for Computer
+         Communications 2003, pp. 381-394.
+
+   [25]  N. Daswani, H. Garcia-Molina, and B. Yang, Open Problems in
+         Data- sharing Peer-to-peer Systems, The 9th Int'l Conf. on
+         Database Theory (ICDT 2003), Siena, Italy, 8-10 January (2003)
+
+   [26]  B. Cooper and H. Garcia-Molina, Studying search networks with
+         SIL, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03,
+         20- 21 February 2003.
+
+   [27]  M. Bawa, Q. Sun, P. Vinograd, B. Yang, B. Cooper, A. Crespo, N.
+         Daswani, P. Ganesan, H. Garcia-Molina, S. Kamvar, S. Marti, and
+         M. Schlossed, Peer-to-peer research at Stanford, ACM SIGMOD
+         Record 32 (3) (2003) 23-28.
+
+   [28]  B. Yang and H. Garcia-Molina, Improving search in peer-to-peer
+         networks, Proc. 22nd IEEE Int'l Conf. on Distributed Computing
+         Systems, July 2002.
+
+   [29]  B. Yang and H. Garcia-Molina, Efficient search in peer-to-peer
+         networks, Proc. 22nd Int'l Conf. on Distributed Computing
+         Systems, July 2-5 2002.
+
+   [30]  C. Plaxton, R. Rajaraman, and A. Richa, Accessing nearby copies
+         of replicated objects in a distributed environment, ACM Symp.
+         on Parallel Algorithms and Architectures (1997)
+
+   [31]  B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J.
+         Kubiatowicz, Tapestry: A Resilient Global-Scale overlay for
+         Service Deployment, IEEE Journal on Selected Areas in
+         Communications 22 (1) (2004) 41-53.
+
+   [32]  R. van Renesse and A. Bozdog, Willow: DHT, aggregation and
+         publish/subscribe in one protocol, The 3rd Int'l Workshop on
+         Peer-to-Peer Systems, February 26-27 2004.
+
+   [33]  P. Ganesan, G. Krishna, and H. Garcia-Molina, Canon in G Major:
+         Designing DHTs with Hierarchical Structure, Proc. Int'l Conf.
+         on Distributed Computing Systems ICDCS 2004 2004.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 56]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [34]  I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Kaashoek,
+         F. Dabek, and H. Balakrishnan, Chord:  a scalable peer-to-peer
+         lookup protocol for Internet applications, IEEE/ACM Trans. on
+         Networking 11 (1) (2003) 17-32.
+
+   [35]  S. Rhea, T. Roscoe, and J. Kubiatowicz, Structured Peer-to-Peer
+         Overlays Need Application-Driven Benchmarks, Proc. 2nd Int'l
+         Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
+
+   [36]  D. Loguinov, A. Kumar, and S. Ganesh, Graph-theoretic analysis
+         of structured peer-to-peer systems:  routing distances and
+         fault resilience, Proc. 2003 conference on Applications,
+         Technologies, Architectures and Protocols for Computer
+         Communications, August 25-29 2003, pp. 395-406.
+
+   [37]  F. Kaashoek and D. Karger, Koorde:  A simple degree-optimal
+         hash table, Second Int'l Workshop on Peer-to-Peer Systems
+         IPTPS'03, 20-21 February 2003.
+
+   [38]  N. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman,
+         SkipNet: A Scalable Overlay Network with Practical Locality
+         Properties, Proc. Fourth USENIX Symp. on Internet Technologies
+         and Systems USITS'03, March 2003.
+
+   [39]  I. Gupta, K. Birman, P. Linga, A. Demers, and R. Van Renesse,
+         Kelips:  Building an efficient and stable P2P DHT through
+         increased memory and background overhead, Second Int'l Workshop
+         on Peer-to-Peer Systems IPTPS 03, Feb 20-21 2003.
+
+   [40]  J. Cates, Robust and Efficient Data Management for a
+         Distributed Hash Table, Master's Thesis, May 2003.
+
+   [41]  J. Aspnes and G. Shah, Skip graphs, Proc. 14th annual ACM-SIAM
+         symposium on discrete algorithms (2003) 384-393.
+
+   [42]  K. Aberer, P. Cudre-Mauroux, A. Datta, Z. Despotovic, M.
+         Hauswirth, M. Punceva, and R. Schmidt, P-Grid:  a self-
+         organizing structured P2P system, ACM SIGMOD Record 32 (3)
+         (2003) 29-33.
+
+   [43]  B. Zhao, Y. Duan, L. Huang, A. Joseph, and J. Kubiatowicz,
+         Brocade: landmark routing on overlay networks, First Int'l
+         Workshop on Peer-to-Peer Systems IPTPS'02, March 2002.
+
+   [44]  S. Ratnasamy, S. Shenker, and I. Stoica, Routing algorithms for
+         DHTs:  some open questions, Proc. First Int'l Workshop on Peer
+         to Peer Systems, IPTPS 2002, March 2002.
+
+
+
+
+Risson & Moors               Informational                     [Page 57]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [45]  P. Maymounkov and D. Mazieres, Kademlia:  A peer-to-peer
+         information system based on the XOR metric, Proc. First Int'l
+         Workshop on Peer to Peer Systems, IPTPS 2002, March 7-8 2002.
+
+   [46]  D. Malkhi, M. Naor, and D. Ratajczak, Viceroy:  a scalable and
+         dynamic emulation of the butterfly, Proc. 21st annual symposium
+         on principles of distributed computing PODC, July 21-24 2002,
+         pp. 183-192.
+
+   [47]  X. Li and C. Plaxton, On name resolution in peer to peer
+         networks, Proc. ACM SIGACT Annual Workshop on Principles of
+         Mobile Computing POMC'02 2002, pp. 82-89.
+
+   [48]  N. Harvey, J. Dunagan, M. B. Jones, S. Saroiu, M. Theimer, and
+         A. Wolman, SkipNet:  A Scalable overlay Network with Practical
+         Locality Properties, Microsoft Research Technical Report MSR-
+         TR- 2002-92 (2002)
+
+   [49]  D. Karger, E. Lehman, T. Leighton, R. Panigraphy, M. Levin, and
+         D. Lewin, Consistent hashing and random trees:  distributed
+         caching protocols for relieving hot spots on the World Wide
+         Web, ACM Symp. on Theory of Computing (1997)
+
+   [50]  W. Litwin, M. Neimat, and D. Schneider, LH* - a scalable,
+         distributed data structure, ACM Trans. on Database Systems
+         (TODS) 21 (4) (1996) 480-525.
+
+   [51]  R. Devine, Design and Implementation of DDH: A Distributed
+         Dynamic Hashing Algorithm, Proc.  4th Int'l Conf. on
+         Foundations of Data Organizations and Algorithms 1993.
+
+   [52]  W. Litwin, M.-A. Niemat, and D. Schneider, LH* - Linear Hashing
+         for Distributed Files, Proc.  ACM Int'l Conf. on Mngt. of Data
+         SIGMOD, May 1993, pp. 327-336.
+
+   [53]  C. Tempich, S. Staab, and A. Wranik, Remindin': semantic query
+         routing in peer-to-peer networks, Proc. 13th conference on
+         World Wide Web, New York, NY, USA, May 17-20 (2004) 640-649.
+
+   [54]  B. T. Loo, R. Huebsch, I. Stoica, and J. M. Hellerstein, The
+         case for a hybrid P2P search infrastructure, The 3rd Int'l
+         Workshop on Peer-to-Peer Systems, February 26-27 2004.
+
+   [55]  M. Cai and M. Frank, RDFPeers: a scalable distributed RDF
+         repository based on a structured peer-to-peer network, Proc.
+         13th conference on World Wide Web, May 17-20 2004, pp. 650-657.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 58]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [56]  Z. Zhang, S.-M. Shi, and J. Zhu, SOMO: Self-organized metadata
+         overlay for resource management in P2P DHTs, Second Int'l
+         Workshop on Peer-to-Peer Systems IPTPS'03, Feb 20-21 2003.
+
+   [57]  B. Yang and H. Garcia-Molina, Designing a super-peer network,
+         Proc. 19th Int'l Conf. on Data Engineering ICDE, March 2003.
+
+   [58]  I. Tatarinov, P. Mork, Z. Ives, J. Madhavan, A. Halevy, D.
+         Suciu, N. Dalvi, X. Dong, Y. Kadiyska, and G. Miklau, The
+         Piazza peer data management project, ACM SIGMOD Record 32 (3)
+         (2003) 47-52.
+
+   [59]  W. Nejdl, W. Siberski, and M. Sintek, Design Issues and
+         Challenges for RDF- and schema-based peer-to-peer systems, ACM
+         SIGMOD Record 32 (3) (2003) 41-46.
+
+   [60]  S. Joseph and T. Hoshiai, Decentralized Meta-Data Strategies:
+         Effective Peer-to-Peer Search, IEICE Trans. Commun. E86-B (6
+         June) (2003) 1740-1753.
+
+   [61]  Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S.
+         Shenker, Making gnutella-like P2P systems scalable, Proc. 2003
+         conference on Applications, Technologies, Architectures and
+         Protocols for Computer Communications, August 25-29 2003, pp.
+         407-418.
+
+   [62]  M. Bawa, G. S. Manku, and P. Raghavan, SETS: search enhanced by
+         topic segmentation, Proc. 26th annual international ACM SIGIR
+         conference on Research and Development in Information Retrieval
+         2003, pp. 306-313.
+
+   [63]  H. Sunaga, M. Takemoto, and T. Iwata, Advanced peer to peer
+         network platform for various services - SIONet Semantic
+         Information Oriented Network, Proc. Second Int'l Conf. on Peer
+         to Peer Computing, Sept 5-7 2002, pp. 169-170.
+
+   [64]  M. Schlosser, M. Sintek, S. Decker, and W. Nejdl, HyperCuP -
+         Hypercubes, Ontologies and P2P Networks, Springer Lecture Notes
+         on Computer Science, Agents and Peer-to-Peer Systems Vol. 2530
+         (2002)
+
+   [65]  M. Ripeanu, A. Iamnitchi, and P. Foster, Mapping the Gnutella
+         network, IEEE Internet Computing 6 (1) (2002) 50-57.
+
+   [66]  Q. Lv, S. Ratnasamy, and S. Shenker, Can Heterogeneity Make
+         Gnutella Scalable?, Proc. 1st Int'l Workshop on Peer-to-Peer
+         Systems IPTPS2002, March 7-8 2002.
+
+
+
+
+Risson & Moors               Informational                     [Page 59]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [67]  Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, Search and
+         replication in unstructured peer to peer networks, Proc. 16th
+         international conference on supercomputing, June 22-26 2002,
+         pp. 84-95.
+
+   [68]  V. Kalogaraki, D. Gunopulos, and D. Zeinalipour-Yasti, XML
+         schemas:  integration and translation:  A local search
+         mechanism for peer to peer networks, Proc. 11th ACM
+         international conference on Information and Knowledge
+         management 2002, pp. 300- 307.
+
+   [69]  O. Babaoglu, H. Meling, and Montresor, Anthill:  a framework
+         for the development of agent-based peer-to-peer systems, Proc.
+         IEEE Int'l Conf. on Distributed Computer systems 2002, pp. 15-
+         22.
+
+   [70]  M. Jovanovic, Modeling large-scale peer-to-peer networks and a
+         case study of Gnutella, Master's Thesis 2001.
+
+   [71]  I. Clarke, O. Sandberg, B. Wiley, and T. Hong, Freenet:  A
+         Distributed Anonymous Information Storage and Retrieval System.
+         Springer, New York, USA, 2001.
+
+   [72]  J. Harren, J. Hellerstein, R. Huebsch, B. Loo, S. Shenker, and
+         I. Stoica, Complex queries in DHT-based peer-to-peer networks,
+         Proc. First Int'l Workshop on Peer to Peer Systems IPTPS 2002,
+         March 2002.
+
+   [73]  B. Gedik and L. Liu, PeerCQ: A Decentralized and Self-
+         Configuring Peer-to-Peer Information Monitoring System, Proc.
+         23rd Int'l Conf. on Distributed Computing Systems ICDCS2003,
+         May 19-22 2003.
+
+   [74]  B. T. Loo, R. Huebsch, J. M. Hellerstein, T. Roscoe, and I.
+         Stoica, Analyzing P2P Overlays with Recursive Queries,
+         Technical Report, CSD-04-1301, January 14 2004.
+
+   [75]  R. Avnur and J. Hellerstein, Eddies: continuously adaptive
+         query processing, Proc. 2000 ACM SIGMOD international
+         conference on Management of Data 2000, pp. 261-272.
+
+   [76]  P. Triantafillou and T. Pitoura, Towards a unifying framework
+         for complex query processing over structured peer-to-peer data
+         networks, Proc. First Int'l Workshop on Databases, Information
+         Systems and Peer-to-Peer Computing DBISP2P, Sept 7-8 2003, pp.
+         169-183.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 60]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [77]  A. Gupta, D. Agrawal, and A. E. Abbadi, Approximate range
+         selection queries in peer-to-peer systems, Proc. First Biennial
+         Conf. on Innovative Data Systems Research CIDR 2003 2003.
+
+   [78]  S. Ratnasamy, P. Francis, and M. Handley, Range queries in
+         DHTs, Technical Report IRB-TR-03-009, July 2003.
+
+   [79]  S. Ramabhadran, S. Ratnasamy, J. Hellerstein, and S. Shenker,
+         Brief announcement: prefix hash tree, Proc. 23rd Annual ACM
+         SIGACT-SIGOPS Symp. on Principles of Distributed Computing,
+         PODC 2004, July 25-28 2004, pp. 368-368.
+
+   [80]  A. Andrzejak and Z. Xu, Scalable, efficient range queries for
+         grid information services, Proc. Second IEEE Int'l Conf. on
+         Peer to Peer Computing, September 2002.
+
+   [81]  C. Schmidt and M. Parashar, Enabling flexible queries with
+         guarantees in P2P systems, IEEE Internet Computing 8 (3) (2004)
+         19-26.
+
+   [82]  E. Tanin, A. Harwood, and H. Samet, Indexing distributed
+         complex data for complex queries, Proc. National Conf. on
+         Digital Government Research 2004, pp. 81-90.
+
+   [83]  P. Ganesan, M. Bawa, and H. Garcia-Molina, Online Balancing of
+         Range-Partitioned Data with Applications to Peer-to-Peer
+         Systems, Proc. 30th Int'l Conf. on Very Large Data Bases VLDB
+         2004, 29 August - 3 September 2004.
+
+   [84]  A. Bharambe, M. Agrawal, and S. Seshan, Mercury: Supporting
+         Scalable Multi-Attribute Range Queries, SIGCOMM'04, Aug 30-Sept
+         3 2004.
+
+   [85]  K. Aberer, Scalable Data Access in P2P Systems Using Unbalanced
+         Search Trees, Workshop on Distributed Data and Structures WDAS-
+         2002 2002.
+
+   [86]  K. Aberer, A. Datta, and M. Hauswirth, The Quest for Balancing
+         Peer Load in Structured Peer-to-Peer Systems, Technical Report
+         IC/2003/32 2003.
+
+   [87]  W. Litwin, M.-A. Neimat, and D. Schneider, RP*: a family of
+         order-preserving scalable distributed data structures, Proc.
+         20th Int'l Conf. on Very Large Data Bases VLDB'94, September
+         12-15 1994.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 61]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [88]  M. Tsangou, S. Ndiaye, M. Seck, and W. Litwin, Range queries to
+         scalable distributed data structure RP*, Proc. Fifth Workshop
+         on Distributed Data and Structures, WDAS 2003, June 2003.
+
+   [89]  W. Litwin and M.-A. Neimat, k-RP*s: a scalable distributed data
+         structure for high-performance multi-attributed access, Proc.
+         Fourth Int'l Conf. on Parallel and Distributed Information
+         Systems (1996) 120-131.
+
+   [90]  T. Hodes, S. Czerwinski, B. Zhao, A. Joseph, and R. Katz, An
+         architecture for secure wide-area service discovery, Wireless
+         Networks 8 (2/3) (2002) 213-230.
+
+   [91]  M. Cai, M. Frank, J. Chen, and P. Szekely, MAAN: A Multi-
+         Attribute Addressable Network for Grid Information Services,
+         Proc. Int'l Workshop on Grid Computing, November 2003.
+
+   [92]  R. van Renesse, K. P. Birman, and W. Vogels, Astrolabe:  A
+         robust and scalable technology for distribute system
+         monitoring, management and data mining, ACM Trans. on Computer
+         Systems 21 (2) (2003) 164-206.
+
+   [93]  R. Bhagwan, G. Varghese, and G. Voelker, Cone: Augmenting DHTs
+         to support distributed resource discovery, Technical Report,
+         CS2003- 0755, July 2003.
+
+   [94]  K. Albrecht, R. Arnold, and R. Wattenhofer, Join and Leave in
+         Peer-to-Peer Systems: The DASIS Approach, Technical Report 427,
+         Department of Computer Science, November 2003.
+
+   [95]  K. Albrecht, R. Arnold, and R. Wattenhofer, Aggregating
+         information in peer-to-peer systems for improved join and
+         leave, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing,
+         25-27 August 2004.
+
+   [96]  A. Montresor, M. Jelasity, and O. Babaoglu, Robust aggregation
+         protocol for large-scale overlay networks, Technical Report
+         UBLCS-2003-16, December 2003.
+
+   [97]  M. Jelasity, W. Kowalczyk, and M. van Steen, An Approach to
+         Aggregation in Large and Fully Distributed Peer-to-Peer Overlay
+         Networks, Proc. 12th Euromicro Conf. on Parallel, Distributted
+         and Network based Processing PDP 2004, February 2004.
+
+   [98]  P. Yalagandula and M. Dahlin, A scalable distributed
+         information management system, SIGCOMM'04, Aug 30-Sept 3 2004.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 62]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [99]  M. Bawa, A. Gionis, H. Garcia-Molina, and R. Motwani, The price
+         of validity in dynamic networks, Proc. 2004 ACM SIGMOD Int'l
+         Conf. on the management of data 2004, pp. 515-526.
+
+   [100] J. Aspnes, J. Kirsch, and A. Krishnamurthy, Load Balancing and
+         Locality in Range-Queriable Data Structures, Proc. 23rd Annual
+         ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing
+         PODC 2004, July 25-28 2004.
+
+   [101] G. On, J. Schmitt, and R. Steinmetz, The effectiveness of
+         realistic replication strategies on quality of availability for
+         peer-to-peer systems, Proc. Third Int'l IEEE Conf. on Peer-to-
+         Peer Computing, Sept 1-3 2003, pp. 57-64.
+
+   [102] D. Geels and J. Kubiatowicz, Replica management should be a
+         game, Proc. SIGOPS European Workshop, September 2003.
+
+   [103] E. Cohen and S. Shenker, Replication strategies in unstructured
+         peer to peer networks, Proc. 2002 conference on applications,
+         technologies, architectures and protocols for computer
+         communications 2002, pp. 177-190.
+
+   [104] E. Cohen and S. Shenker, P2P and multicast:  replication
+         strategies in unstructured peer to peer networks, Proc. 2002
+         conference on applications, technologies, architectures and
+         protocols for computer communications 2002, pp. 177-190.
+
+   [105] H. Weatherspoon and J. Kubiatowicz, Erasure coding vs
+         replication:  a quantative comparison, Proc. First Int'l
+         Workshop on Peer to Peer Systems IPTPS'02, March 2002.
+
+   [106] D. Lomet, Replicated indexes for distributed data, Proc. Fourth
+         Int'l Conf. on Parallel and Distributed Information Systems,
+         December 18-20 1996, pp. 108-119.
+
+   [107] V. Gopalakrishnan, B. Silaghi, B. Bhattacharjee, and P.
+         Keleher, Adaptive Replication in Peer-to-Peer Systems, Proc.
+         24th Int'l Conf. on Distributed Computing Systems ICDCS 2004,
+         March 23-26 2004.
+
+   [108] S.-D. Lin, Q. Lian, M. Chen, and Z. Zhang, A practical
+         distributed mutual exclusion protocol in dynamic peer-to-peer
+         systems, The 3rd Int'l Workshop on Peer-to-Peer Systems,
+         February 26-27 2004.
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 63]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [109] A. Adya, R. Wattenhofer, W. Bolosky, M. Castro, G. Cermak, R.
+         Chaiken, J. Douceur, J. Howell, J. Lorch, and M. Thiemer,
+         Farsite: federated, available and reliable storage for an
+         incompletely trusted environment, ACM SIGOPS Operating Systems
+         Review, Special issue on Decentralized storage systems (2002)
+         1- 14.
+
+   [110] A. Rowstron and P. Druschel, Storage management and caching in
+         PAST, a large-scale, persistent peer-to-peer storage utility,
+         Proceedings ACM SOSP'01, October 2001, pp. 188-201.
+
+   [111] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H.
+         Weatherspoon, and J. Kubiatowicz, Maintenance-Free Global Data
+         Storage, IEEE Internet Computing 5 (5) (2001) 40-49.
+
+   [112] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D.
+         Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C.
+         Wells, and B. Zhao, Oceanstore:  An Architecture for global-
+         scale persistent storage, Proc. Ninth Int'l Conf. on
+         Architecture Support for Programming Languages and Operating
+         Systems ASPLOS 2000, November 2000, pp. 190-201.
+
+   [113] K. Birman, The Surprising Power of Epidemic Communication,
+         Springer-Verlag Heidelberg Lecture Notes in Computer Science
+         Volume 2584/2003 (2003) 97-102.
+
+   [114] P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola,
+         Introducing reliability in content-based publish-subscribe
+         through epidemic algorithms, Proc. 2nd international workshop
+         on Distributed event-based systems 2003, pp. 1-8.
+
+   [115] P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola, Epidemic
+         Algorithms for Reliable Content-Based Publish-Subscribe:  An
+         Evaluation, The 24th Int'l Conf. on Distributed Computing
+         Systems (ICDCS-2004), Mar 23-26, Tokyo University of
+         Technology, Hachioji, Tokyo, Japan (2004)
+
+   [116] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S.
+         Shenker, H. Sturgis, D. Swinehart, and D. Terry, Epidemic
+         algorithms for replicated data management, Proc. Sixth ACM
+         Symp. on Principles of Distributed Computing 1987, pp. 1-12.
+
+   [117] P. Eugster, R. Guerraoiu, A. Kermarrec, and L. Massoulie,
+         Epidemic information dissemination in distributed systems, IEEE
+         Computer 37 (5) (2004) 60-67.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 64]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [118] W. Vogels, R. v. Renesse, and K. Birman, The power of
+         epidemics: robust communication for large-scale distributed
+         systems, ACM SIGCOMM  Computer Communication Review 33 (1)
+         (2003) 131-135.
+
+   [119] S. Voulgaris and M. van Steen, An epidemic protocol for
+         managing routing tables in very large peer to peer networks,
+         Proc. 14th IFIP/IEEE Workshop on Distributed Systems:
+         Operations and Management, October 2003.
+
+   [120] I. Gupta, On the design of distributed protocols from
+         differential equations, Proc. 23rd Annual ACM SIGACT-SIGOPS
+         Symp. on Principles of Distributed Computing PODC 2004, July
+         25-28 2004, pp. 216-225.
+
+   [121] I. Gupta, K. Birman, and R. van Renesse, Fighting fire with
+         fire: using randomized gossip to combat stochastic scalability
+         limits, Cornell University Dept of Computer Science Technical
+         Report, March 2001.
+
+   [122] K. Birman and I. Gupta, Building Scalable Solutions to
+         Distributed Computing Problems using Probabilistic Components,
+         Submitted to the Int'l Conf. on Dependable Systems and Networks
+         DSN-2004, Dependable Computing and Computing Symp. DCCS, June
+         28- July 1 2004.
+
+   [123] A. Ganesh, A.-M. Kermarrec, and L. Massoulie, Peer-to-peer
+         membership management for gossip-based protocols, IEEE Trans.
+         on Computers 52 (2) (2003) 139-149.
+
+   [124] N. Bailey, Epidemic Theory of Infectious Diseases and its
+         Applications, Second Edition ed. Hafner Press, 1975.
+
+   [125] P. Eugster, R. Guerraoiu, S. Handurukande, P. Kouznetsov, and
+         A.- M. Kermarrec, Lightweight probabilistic broadcast, ACM
+         Trans. on Computer Systems 21 (4) (2003) 341-374.
+
+   [126] H. Weatherspoon and J. Kubiatowicz, Efficient heartbeats and
+         repair of softstate in decentralized object location and
+         routing systems, Proc. SIGOPS European Workshop, September
+         2002.
+
+   [127] G. Koloniari and E. Pitoura, Content-based Routing of Path
+         Queries in Peer-to-Peer Systems, Proc. 9th Int'l Conf. on
+         Extending DataBase Technology EDBT, March 14-18 2004.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 65]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [128] A. Mohan and V. Kalogaraki, Speculative routing and update
+         propagation: a kundali centric approach, IEEE Int'l Conf. on
+         Communications ICC'03, May 2002.
+
+   [129] G. Koloniari, Y. Petrakis, and E. Pitoura, Content-Based
+         Overlay Networks for XML Peers Based on Multi-Level Bloom
+         Filters, Proc. First Int'l Workshop on Databases, Information
+         Systems and Peer-to-Peer Computing DBISP2P, Sept 7-8 2003, pp.
+         232-247.
+
+   [130] G. Koloniari and E. Pitoura, Bloom-Based Filters for
+         Hierarchical Data, Proc. 5th Workshop on Distributed Data and
+         Structures (WDAS) (2003)
+
+   [131] B. Bloom, Space/time trade-offs in hash coding with allowable
+         errors, Communications of the ACM 13 (7) (1970) 422-426.
+
+   [132] M. Naor and U. Wieder, A Simple Fault Tolerant Distributed Hash
+         Table, Second Int'l Workshop on Peer-to-Peer Systems (IPTPS
+         03), Berkeley, CA, USA, 20-21 February (2003)
+
+   [133] P. Maymounkov and D. Mazieres, Rateless codes and big
+         downloads, Second Int'l Workshop on Peer-to-Peer Systems,
+         IPTPS'03, February 20-21 2003.
+
+   [134] M. Krohn, M. Freedman, and D. Mazieres, On-the-fly verification
+         of rateless erasure codes for efficient content distribution,
+         Proc. IEEE Symp. on Security and Privacy, May 2004.
+
+   [135] J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, Informed
+         content delivery across adaptive overlay networks, Proc. 2002
+         conference on applications, technologies, architectures and
+         protocols for computer communications 2002, pp. 47-60.
+
+   [136] J. Plank, S. Atchley, Y. Ding, and M. Beck, Algorithms for High
+         Performance, Wide-Area Distributed File Downloads, Parallel
+         Processing Letters 13 (2) (2003) 207-223.
+
+   [137] M. Castro, P. Rodrigues, and B. Liskov, BASE:  Using
+         abstraction to improve fault tolerance, ACM Trans. on Computer
+         Systems 21 (3) (2003) 236-269.
+
+   [138] R. Rodrigues, B. Liskov, and L. Shrira, The design of a robust
+         peer-to-peer system, 10th ACM SIGOPS European Workshop, Sep
+         2002.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 66]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [139] H. Weatherspoon, T. Moscovitz, and J. Kubiatowicz,
+         Introspective failure analysis: avoiding correlated failures in
+         peer-to-peer systems, Proc.  Int'l Workshop on Reliable Peer-
+         to-Peer Distributed Systems, Oct 2002.
+
+   [140] F. Dabek, R. Cox, F. Kaashoek, and R. Morris, Vivaldi: A
+         Decentralized Network Coordinate System, SIGCOMM'04, Aug 30-
+         Sept 3 2004.
+
+   [141] E.-K. Lua, J. Crowcroft, and M. Pias, Highways: proximity
+         clustering for massively scaleable peer-to-peer network
+         routing, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer
+         Computing, August 25-27 2004.
+
+   [142] F. Fessant, S. Handurukande, A.-M. Kermarrec, and L. Massoulie,
+         Clustering in Peer-to-Peer File Sharing Workloads, The 3rd
+         Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
+
+   [143] T. S. E. Ng and H. Zhang, Predicting internet network distance
+         with coordinates-based approaches, IEEE Infocom 2002, The 21st
+         Annual Joint Conf. of the IEEE Computer and Communication
+         Societies, June 23-27 2002.
+
+   [144] K. Hildrum, R. Krauthgamer, and J. Kubiatowicz, Object Location
+         in Realistic Networks, Proc. Sixteenth ACM Symp. on Parallel
+         Algorithms and Architectures (SPAA 2004), June 2004, pp. 25-35.
+
+   [145] P. Keleher, S. Bhattacharjee, and B. Silaghi, Are Virtualized
+         Overlay Networks Too Much of a Good Thing?, First Int'l
+         Workshop on Peer-to-Peer Systems IPTPS, March 2002.
+
+   [146] A. Mislove and P. Druschel, Providing administrative control
+         and autonomy in structured peer-to-peer overlays, The 3rd Int'l
+         Workshop on Peer-to-Peer Systems, June 9-12 2004.
+
+   [147] D. Karger and M. Ruhl, Diminished Chord: A Protocol for
+         Heterogeneous SubGroup Formation in Peer-to-Peer Networks, The
+         3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27
+         2004.
+
+   [148] B. Awerbuch and C. Scheideler, Consistent, order-preserving
+         data management in distributed storage systems, Proc. Sixteenth
+         ACM Symp. on Parallel Algorithms and Architectures SPAA 2004,
+         June 27-30 2004, pp. 44-53.
+
+   [149] M. Freedman and D. Mazieres, Sloppy Hashing and Self-Organizing
+         Clusters, Proc. 2nd Int'l Workshop on Peer-to-Peer Systems
+         IPTPS
+
+
+
+Risson & Moors               Informational                     [Page 67]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [150] F. Dabek, J. Li, E. Sit, J. Robertson, F. Kaashoek, and R.
+         Morris, Designing a DHT for low latency and high throughput,
+         Proc. First Symp. on Networked Systems Design and
+         Implementation (NSDI'04), San Francisco, California, March
+         29-31 (2004) 85-98.
+
+   [151] M. Ruhl, Efficient algorithms for new computational models,
+         Doctoral Dissertation, September 2003.
+
+   [152] K. Sollins, Designing for scale and differentiation, Proc. ACM
+         SIGCOMM workshop on Future Directions in network architecture,
+         August 25-27 2003.
+
+   [153] L. Massoulie, A. Kermarrec, and A. Ganesh, Network awareness
+         and failure resilience in self-organizing overlay networks,
+         Proc. 22nd Int'l Symp. on Reliable Distributed Systems,
+         SRDS'03, Oct 6-8 2003, pp. 47-55.
+
+   [154] R. Cox, F. Dabek, F. Kaashoek, J. Li, and R. Morris,
+         Practical,distributed network coordinates, ACM SIGCOMM Computer
+         Communication Review 34 (1) (2004) 113-118.
+
+   [155] K. Hildrum, J. Kubiatowicz, S. Rao, and B. Zhao, Distributed
+         object location in a dynamic network, Proc. 14th annual ACM
+         symposium on parallel algorithms and architectures 2002, pp.
+         41- 52.
+
+   [156] X. Zhang, Q. Zhang, G. Song, and W. Zhu, A Construction of
+         Locality-Aware Overlay Network: mOverlay and its Performance,
+         IEEE Journal on Selected Areas in Communications 22 (1) (2004)
+         18-28.
+
+   [157] N. Harvey, M. B. Jones, M. Theimer, and A. Wolman, Efficient
+         recovery from organization disconnects in Skipnet, Second Int'l
+         Workshop on Peer-to-Peer Systems IPTPS'03, Feb 20-21 2003.
+
+   [158] M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti,
+         Lighthouses for scalable distributed location, Second Int'l
+         Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
+
+   [159] K. Gummadi, S. Saroui, S. Gribble, and D. King, Estimating
+         latency between arbitrary internet end hosts, Proc.  SIGCOMM
+         IMW 2002, November 2002.
+
+   [160] Y. Liu, X. Liu, L. Xiao, L. Ni, and X. Zhang, Location-aware
+         topology matching in P2P systems, Proc.  IEEE Infocomm, Mar
+         7-11 2004.
+
+
+
+
+Risson & Moors               Informational                     [Page 68]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [161] G. S. Manku, Balanced binary trees for ID management and load
+         balance in distributed hash tables, Proc. 23rd Annual ACM
+         SIGACT-SIGOPS Symp. on Principles of Distributed Computing,
+         PODC 2004, July 25-28 2004, pp. 197-205.
+
+   [162] J. Gao and P. Steenkiste, Design and Evaluation of a
+         Distributed Scalable Content Delivery System, IEEE Journal on
+         Selected Areas in Communications 22 (1) (2004) 54-66.
+
+   [163] X. Wang, Y. Zhang, X. Li, and D. Loguinov, On zone-balancing of
+         peer-to-peer networks: analysis of random node join, Proc.
+         joint international conference on measurement and modeling of
+         computer systems, June 2004.
+
+   [164] D. Karger and M. Ruhl, Simple efficient load balancing
+         algorithms for peer-to-peer systems, Proc. Sixteenth ACM Symp.
+         on Parallel Algorithms and Architectures SPAA 2004, June 27-30
+         2004.
+
+   [165] D. Karger and M. Ruhl, Simple efficient load balancing
+         algorithms for peer-to-peer systems, The 3rd Int'l Workshop on
+         Peer-to-Peer Systems, February 26-27 2004.
+
+   [166] M. Adler, E. Halperin, R. Karp, and V. Vazirani, A stochastic
+         process on the hypercube with applications to peer-to-peer
+         networks, Proc. 35th ACM symposium on Theory of Computing 2003,
+         pp. 575-584.
+
+   [167] C. Baquero and N. Lopes, Towards peer to peer content indexing,
+         ACM SIGOPS Operating Systems Review 37 (4) (2003) 90-96.
+
+   [168] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica,
+         Load balancing in structured P2P systems, Proc. 2nd Int'l
+         Workshop on Peer-to-Peer Systems, IPTPS'03, February 20-21
+         2003.
+
+   [169] J. Byers, J. Considine, and M. Mitzenmacher, Simple Load
+         Balancing for Distributed Hash Tables, Second Int'l Workshop on
+         Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
+
+   [170] P. Castro, J. Lee, and A. Misra, CLASH: A Protocol for
+         Internet- Scale Utility-Oriented Distributed Computing, Proc.
+         24th Int'l Conf. on Distributed Computing Systems ICDCS 2004,
+         March 23-26 2004.
+
+   [171] A. Stavrou, D. Rubenstein, and S. Sahu, A Lightwight, Robust
+         P2P System to Handle Flash Crowds, IEEE Journal on Selected
+         Areas in Communications 22 (1) (2004) 6-17.
+
+
+
+Risson & Moors               Informational                     [Page 69]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [172] A. Selcuk, E. Uzun, and M. R. Pariente, A reputation-based
+         trust management system for P2P networks, Fourth Int'l Workshop
+         on Global and Peer-to-Peer Computing, April 20-21 2004.
+
+   [173] T. Papaioannou and G. Stamoulis, Effective use of reputation in
+         peer-to-peer environments, Fourth Int'l Workshop on Global and
+         Peer-to-Peer Computing, April 20-21 2004.
+
+   [174] M. Blaze, J. Feigenbaum, and J. Lacy, Trust and Reputation in
+         P2P networks,
+         http://www.neurogrid.net/twiki/bin/view/Main/ReputationAndTrust
+         (2003)
+
+   [175] E. Damiani, D. C. di Vimercati, S. Paraboschi, P. Samarati, and
+         F. Violante, A reputation-based approach for choosing reliable
+         resources in peer to peer networks, Proc. 9th conference on
+         computer and communications security 2002, pp. 207-216.
+
+   [176] S. Marti, P. Ganesan, and H. Garcia-Molina, DHT routing using
+         social links, The 3rd Int'l Workshop on Peer-to-Peer Systems,
+         February 26-27 2004.
+
+   [177] G. Caronni and M. Waldvogel, Establishing trust in distributed
+         storage providers, Proc. Third Int'l IEEE Conf. on Peer-to-Peer
+         Computing, 1-3 Sept 2003, pp. 128-133.
+
+   [178] B. Sieka, A. Kshemkalyani, and M. Singhal, On the security of
+         polling protocols in peer-to-peer systems, Proc. Fourth IEEE
+         Int'l Conf. on Peer-to-Peer Computing, 25-27 August 2004.
+
+   [179] M. Feldman, K. Lai, I. Stoica, and J. Chuang, Robust Incentive
+         Techniques for Peer-to-Peer Networks, ACM E-Commerce Conf.
+         EC'04, May 2004.
+
+   [180] K. Anagnostakis and M. Greenwald, Exchange-based Incentive
+         Mechanism for Peer-to-Peer File Sharing, Proc. 24th Int'l Conf.
+         on Distributed Computing Systems ICDCS 2004, March 23-26 2004.
+
+   [181] J. Schneidman and D. Parkes, Rationality and self-Interest in
+         peer to peer networks, Second Int'l Workshop on Peer-to-Peer
+         Systems IPTPS'03, February 20-21 2003.
+
+   [182] C. Buragohain, D. Agrawal, and S. Subhash, A game theoretic
+         framework for incentives in P2P systems, Proc. Third Int'l IEEE
+         Conf. on Peer-to-Peer Computing, 1-3 Sept 2003, pp. 48-56.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 70]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [183] W. Josephson, E. Sirer, and F. Schneider, Peer-to-Peer
+         Authentication with a Distributed Single Sign-On Service, The
+         3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27
+         2004.
+
+   [184] A. Fiat and J. Saia, Censorship resistant peer to peer content
+         addressable networks, Proc. 13th annual ACM-SIAM symposium on
+         discrete algorithms 2002, pp. 94-103.
+
+   [185] N. Daswani and H. Garcia-Molina, Query-flood DoS attacks in
+         gnutella, Proc. 9th ACM Conf. on Computer and Communications
+         Security 2002, pp. 181-192.
+
+   [186] A. Singh and L. Liu, TrustMe: anonymous management of trust
+         relationships in decentralized P2P systems, Proc. Third Int'l
+         IEEE Conf. on Peer-to-Peer Computing, Sept 1-3 2003.
+
+   [187] A. Serjantov, Anonymizing censorship resistant systems, Proc.
+         Second Int'l Conf. on Peer to Peer Computing, March 2002.
+
+   [188] S. Hazel and B. Wiley, Achord: A Variant of the Chord Lookup
+         Service for Use in Censorship Resistant Peer-to-Peer Publishing
+         Systems, Proc. Second Int'l Conf. on Peer to Peer Computing,
+         March 2002.
+
+   [189] M. Freedman and R. Morris, Tarzan: a peer-to-peer anonymizing
+         network layer, Proc. 9th ACM Conf. on Computer and
+         Communications Security (2002) 193-206.
+
+   [190] M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica, Free-
+         Riding and Whitewashing in Peer-to-Peer Systems, 3rd Annual
+         Workshop on Economics and Information Security WEIS04, May
+         2004.
+
+   [191] L. Ramaswamy and L. Liu, FreeRiding: a new challenge for peer-
+         to-peer file sharing systems, Proc. 2003 Hawaii Int'l Conf. on
+         System Sciences, P2P Track, HICSS2003, January 6-9 2003.
+
+   [192] T.-W. Ngan, D. Wallach, and P. Druschel, Enforcing fair sharing
+         of peer-to-peer resources, Second Int'l Workshop on Peer-to-
+         Peer Systems, IPTPS'03, 20-21 February 2003.
+
+   [193] L. Cox and B. D. Noble, Samsara: honor among thieves in peer-
+         to-peer storage, Proc. nineteenth ACM symposium on Operating
+         System Principles 2003, pp. 120-132.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 71]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [194] M. Surridge and C. Upstill, Grid security: lessons for peer-to-
+         peer systems, Proc. Third Int'l IEEE Conf. on Peer-to-Peer
+         Computing, Sept 1-3 2003, pp. 2-6.
+
+   [195] E. Sit and R. Morris, Security considerations for peer-to-peer
+         distributed hash tables, First Int'l Workshop on Peer-to-Peer
+         Systems, March 2002.
+
+   [196] C. O'Donnel and V. Vaikuntanathan, Information leak in the
+         Chord lookup protocol, Proc. Fourth IEEE Int'l Conf. on Peer-
+         to-Peer Computing, 25-27 August 2004.
+
+   [197] K. Berket, A. Essiari, and A. Muratas, PKI-Based Security for
+         Peer-to-Peer Information Sharing, Proc. Fourth IEEE Int'l Conf.
+         on Peer-to-Peer Computing, 25-27 August 2004.
+
+   [198] B. Karp, S. Ratnasamy, S. Rhea, and S. Shenker, Spurring
+         adoption of DHTs with OpenHash, a public DHT service, The 3rd
+         Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
+
+   [199] J. Considine, M. Walfish, and D. G. Andersen, A pragmatic
+         approach to DHT adoption, Technical Report,, December 2003.
+
+   [200] G. Li, Peer to Peer Networks in Action, IEEE Internet Computing
+         6 (1) (2002) 37-39.
+
+   [201] A. Mislove, A. Post, C. Reis, P. Willmann, P. Druschel, D.
+         Wallach, X. Bonnaire, P. Sens, J.-M. Busca, and L. Arantes-
+         Bezerra, POST:  A Secure, Resilient, Cooperative Messaging
+         System, 9th Workshop on Hot Topics in Operating Systems, HotOS,
+         May 2003.
+
+   [202] S. Saroiu, P. Gummadi, and S. Gribble, A measurement study of
+         peer-to-peer file sharing systems, Proc.  Multimedia Computing
+         and Networking 2002 MMCN'02, January 2002.
+
+   [203] A. Muthitacharoen, R. Morris, T. Gil, and B. Chen, Ivy: a
+         read/write peer-to-peer file system, ACM SIGOPS Operating
+         Systems Review, Special issue on Decentralized storage systems,
+         December 2002, pp. 31-44.
+
+   [204] A. Muthitacharoen, R. Morris, T. Gil, and B. Chen, A read/write
+         peer-to-peer file system, Proc. 5th Symp. on Operating System
+         Design and Implementation (OSDI 2002), Boston, MA, December
+         (2002)
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 72]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [205] F. Annexstein, K. Berman, M. Jovanovic, and K. Ponnavaikko,
+         Indexing techniques for file sharing in scalable peer to peer
+         networks, 11th IEEE Int'l Conf. on Computer Communications and
+         Networks (2002) 10-15.
+
+   [206] G. Kan and Y. Faybishenko, Introduction to Gnougat, First Int'l
+         Conf. on Peer-to-Peer Computing 2001 2001, pp. 4-12.
+
+   [207] R. Gold and D. Tidhar, Towards a content-based aggregation
+         network, Proc. First Int'l Conf. on Peer to Peer Compuuting
+         2001, pp. 62-68.
+
+   [208] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica,
+         Wide-area cooperative storage with CFS, Proc. 18th ACM
+         symposium on Operating System Principles 2001, pp. 202-215.
+
+   [209] M. Freedman, E. Freudenthal, and D. Mazieres, Democratizing
+         content publication with coral, Proc. First Symp. on Networked
+         Systems Design and Implementation NSDI'04, March 29-31 2004,
+         pp. 239-252.
+
+   [210] J. Li, B. T. Loo, J. Hellerstein, F. Kaashoek, D. Karger, and
+         R. Morris, On the Feasibility of Peer-to-Peer Web Indexing and
+         Search, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03,
+         20-21 February 2003.
+
+   [211] S. Iyer, A. Rowstron, and P. Druschel, Squirrel: a
+         decentralized peer-to-peer web cache, Proc. 21st annual
+         symposium on principles of distributed computing 2002, pp.
+         213-222.
+
+   [212] M. Bawa, R. Bayardo, S. Rajagopalan, and E. Shekita, Make it
+         fresh, make it quick: searching a network of personal
+         webservers, Proc. 12th international conference on World Wide
+         Web 2003, pp. 577-586.
+
+   [213] B. T. Loo, S. Krishnamurthy, and O. Cooper, Distributed web
+         crawling over DHTs, Technical Report, CSD-04-1305, February 9
+         2004.
+
+   [214] M. Junginger and Y. Lee, A self-organizing publish/subscribe
+         middleware for dynamic peer-to-peer networks, IEEE Network 18
+         (1) (2004) 38-43.
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 73]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [215] F. Cuenca-Acuna, C. Peery, R. Martin, and T. Nguyen, PlanetP:
+         Using Gossiping to Build Content Addressable Peer-to-Peer
+         Information Sharing Communities, Proc. 12th international
+         symposium on High Performance Distributed Computing (HPDC),
+         June 2002.
+
+   [216] M. Walfish, H. Balakrishnan, and S. Shenker, Untangling the web
+         from DNS, Proc. First Symp. on Networked Systems Design and
+         Implementation NSDI'04, March 29-31 2004, pp. 225-238.
+
+   [217] B. Awerbuch and C. Scheideler, Robust distributed name service,
+         The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27
+         2004.
+
+   [218] A. Iamnitchi, Resource Discovery in Large Resource-Sharing
+         Environments, Doctoral Dissertation 2003.
+
+   [219] R. Cox, A. Muthitacharoen, and R. Morris, Serving DNS using a
+         Peer-to-Peer Lookup Service, First Int'l Workshop on Peer-to-
+         Peer Systems (IPTPS), March 2002.
+
+   [220] A. Chander, S. Dawson, P. Lincoln, and D. Stringer-Calvert,
+         NEVRLATE:  scalable resource discovery, Second IEEE/ACM Int'l
+         Symp. on Cluster Computing and the Grid CCGRID2002 2002, pp.
+         56-65.
+
+   [221] M. Balazinska, H. Balakrishnan, and D. Karger, INS/Twine:  A
+         scalable Peer-to-Peer architecture for Intentional Resource
+         Discovery, Proc. First Int'l Conf. on Pervasive Computing
+         (IEEE) (2002)
+
+   [222] J. Kangasharju, K. Ross, and D. Turner, Secure and resilient
+         peer-to-peer E-mail: design and implementation, Proc. Third
+         Int'l IEEE Conf. on Peer-to-Peer Computing, 1-3 Sept 2003.
+
+   [223] V. Lo, D. Zappala, D. Zhou, Y. Liu, and S. Zhao, Cluster
+         computing on the fly: P2P scheduling of idle cycles in the
+         internet, The 3rd Int'l Workshop on Peer-to-Peer Systems,
+         February 26-27 2004.
+
+   [224] A. Iamnitchi, I. Foster, and D. Nurmi, A peer-to-peer approach
+         to resource discovery in grid environments, IEEE High
+         Performance Distributed Computing 2002.
+
+   [225] I. Foster and A. Iamnitchi, On Death, Taxes and the Convergence
+         of Peer-to-Peer and Grid Computing, Second Int'l Workshop on
+         Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
+
+
+
+
+Risson & Moors               Informational                     [Page 74]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [226] W. Hoschek, Peer-to-Peer Grid Databases for Web Service
+         Discovery, Concurrency - Practice and Experience (2002) 1-7.
+
+   [227] K. Aberer, A. Datta, and M. Hauswirth, A decentralized public
+         key infrastructure for customer-to-customer e-commerce, Int'l
+         Journal of Business Process Integration and Management (2004)
+
+   [228] S. Ajmani, D. Clarke, C.-H. Moh, and S. Richman, ConChord:
+         Cooperative SDSI Certificate Storage and Name Resolution, First
+         Int'l Workshop on Peer-to-Peer Systems IPTPS, March 2002.
+
+   [229] E. Sit, F. Dabek, and J. Robertson, UsenetDHT: a low overhead
+         Usenet server, The 3rd Int'l Workshop on Peer-to-Peer Systems,
+         February 26-27 2004.
+
+   [230] H.-Y. Hsieh and R. Sivakumar, On transport layer support for
+         peer-to-peer networks, The 3rd Int'l Workshop on Peer-to-Peer
+         Systems, February 26-27 2004.
+
+   [231] I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana,
+         Internet indirection infrastructure, Proc. 2002 conference on
+         applications, technologies, architectures and protocols for
+         computer communications, August 19-23 2002, pp. 73-86.
+
+   [232] E. Halepovic and R. Deters, Building a P2P forum system with
+         JXTA, Proc. Second IEEE Int'l Conf. on Peer to Peer Computing
+         P2P'02, September 5-7 2002.
+
+   [233] M. Wawrzoniak, L. Peterson, and T. Roscoe, Sophia: an
+         Information Plane for networked systems, ACM SIGCOMM Computer
+         Communication Review 34 (1) (2004) 15-20.
+
+   [234] D. Tran, K. Hua, and T. Do, A Peer-to-Peer Architecture for
+         Media Streaming, IEEE Journal on Selected Areas in
+         Communications 22 (1) (2004) 121-133.
+
+   [235] V. Padmanabhan, H. Wang, and P. Chou, Supporting heterogeneity
+         and congestion control in peer-to-peer multicast streaming, The
+         3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27
+         2004.
+
+   [236] A. Nicolosi and D. Mazieres, Secure acknowledgment of multicast
+         messages in open peer-to-peer networks, The 3rd Int'l Workshop
+         on Peer-to-Peer Systems, February 26-27 2004.
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 75]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [237] R. Zhang and C. Hu, Borg: a hybrid protocol for scalable
+         application-level multicast in peer-to-peer networks, Proc.
+         13th international workshop on network and operating systems
+         for digital audio and video 2003, pp. 172-179.
+
+   [238] M. Sasabe, N. Wakamiya, M. Murata, and H. Miyahara, Scalable
+         and continuous media streaming on peer-to-peer networks, Proc.
+         Third Int'l IEEE Conf. on Peer-to-Peer Computing, Sept 1-3
+         2003, pp. 92-99.
+
+   [239] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava,
+         PROMISE: peer-to-peer media streaming using CollectCast, Proc.
+         eleventh ACM international conference on multimedia 2003, pp.
+         45-54.
+
+   [240] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron,
+         and A. Singh, SplitStream:  high-bandwidth multicast in
+         cooperative environments, Proc. 19th ACM symposium on operating
+         systems principles 2003, pp. 298-313.
+
+   [241] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron,
+         SCRIBE: a large-scale and decentralized application-level
+         multicast infrastructure, IEEE Journal on Selected Areas in
+         Communications 20 (8) (2002)
+
+   [242] S. Zhuang, B. Zhao, A. Joseph, R. Katz, and J. Kubiatowicz,
+         Bayeux: an architecture for scalable and fault-tolerant wide-
+         area data dissemination, Proc. 11th ACM international workshop
+         on network and operating systems support for digital audio and
+         video, Jan 2001.
+
+   [243] R. Lienhart, M. Holliman, Y.-K. Chen, I. Kozintsev, and M.
+         Yeung, Improving media services on P2P networks, IEEE Internet
+         Computing 6 (1) (2002) 58-67.
+
+   [244] S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L.
+         Yin, and F. Yu, Data Centric Storage in Sensornets with GHT, a
+         geographic hash table, Mobile Networks and Applications 8 (4)
+         (2003) 427-442.
+
+   [245] M. Demirbas and H. Ferhatosmanoglu, Peer-to-peer spatial
+         queries in sensor networks, Proc. Third Int'l IEEE Conf. on
+         Peer-to-Peer Computing, 1-3 Sept 2003, pp. 32-39.
+
+   [246] S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan,
+         and S. Shenker, GHT:  a geographic hash table for data-centric
+         storage, Proc. First ACM Int'l Workshop on Wireless Sensor
+         Networks and Applications (Mobicom) 2002, pp. 78-87.
+
+
+
+Risson & Moors               Informational                     [Page 76]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [247] J. Hellerstein and W. Wang, Optimization of In-Network Data
+         Reduction, Proc. First Workshop on Data Management for Sensor
+         Networks DMSN 2004, August 30th 2004.
+
+   [248] J. Li, J. Stribling, T. Gil, R. Morris, and F. Kaashoek,
+         Comparing the performance of distributed hash tables under
+         churn, The 3rd Int'l Workshop on Peer-to-Peer Systems, February
+         26-27 2004.
+
+   [249] S. Shenker, The data-centric revolution in networking, Keynote
+         Speech, 29th Int'l Conf. on Very Large Data Bases, September
+         9-12 2003.
+
+   [250] S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu, What
+         can databases do for P2P?, Proc.  Fourth Int'l Workshop on
+         Databases and the Web, WebDB2001, May 24-25 2001.
+
+   [251] D. Clark, The design philosophy of the DARPA internet
+         protocols, ACM SIGCOMM Computer Communication Review, Symp.
+         proceedings on communications architectures and protocols 18
+         (4) (1988)
+
+   [252] J.-C. Laprie, Dependable Computing and Fault Tolerance:
+         Concepts and Terminology, Twenty-Fifth Int'l Symp. on Fault-
+         Tolerant Computing, Highlights from Twenty-Five Years 1995, pp.
+         2-13.
+
+   [253] D. Clark, J. Wroclawski, K. Sollins, and R. Braden, Tussle in
+         cyberspace:  defining tomorrow's internet, Conf. on
+         Applications, Technologies, Architectures and Protocols for
+         Computer Communications 2002, pp. 347-356.
+
+   [254] L. O. Alima, A. Ghodsi, and S. Haridi, "A framework for
+         structured peer-to-peer overlay networks," in Global computing,
+         vol. 3267, Lecture Notes in Computer Science: Springer Berlin /
+         Heidelberg, 2005, pp. 223-249.
+
+   [255] Clip2, The Gnutella Protocol Specification,
+         http://www.clip2.com (2000)
+
+   [256] Napster, http://www.napster.com (1999)
+
+   [257] J. Mishchke and B. Stiller, A methodology for the design of
+         distributed search in P2P middleware, IEEE Network 18 (1)
+         (2004) 30-37.
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 77]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [258] J. Li and K. Sollins, Implementing aggregation and broadcast
+         over distributed hash tables.  Full report,
+         http://krs.lcs.mit.edu/regions/docs.html (November) (2003)
+
+   [259] M. Castro, M. Costa, and A. Rowstron, Should we build Gnutella
+         on a structured overlay?, ACM SIGCOMM Computer Communication
+         Review 34 (1) (2004) 131-136.
+
+   [260] A. Singla and C. Rohrs, Ultrapeers: Another Step Towards
+         Gnutella Scalability,
+         http://groups.yahoo.com/group/the_gdf/files/Proposals/
+         Working%20Proposals/Ultrapeer/ Version 1.0, 26 November (2002)
+
+   [261] B. Cooper and H. Garcia-Molina, Ad hoc, Self-Supervising Peer-
+         to-Peer Search Networks, Technical Report,
+         http://www.cc.gatech.edu/~cooperb/odin/ 2003.
+
+   [262] R. Baeza-Yates and B. Ribeiro-Neto, Modern Information
+         Retrieval.  Addison Wesley, Essex, England, 1999.
+
+   [263] S. Sen and J. Wang, Analyzing peer-to-peer traffic across large
+         networks, IEEE/ACM Trans. on Networking 12 (2) (2004) 219-232.
+
+   [264] H. Balakrishnan, S. Shenker, and M. Walfish, Semantic-Free
+         Referencing in Linked Distributed Systems, Second Int'l
+         Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
+
+   [265] B. Yang, P. Vinograd, and H. Garcia-Molina, Evaluating GUESS
+         and non-forwarding peer-to-peer search, The 24th Int'l Conf. on
+         Distributed Computing Systems ICDCS'04, Mar 23-26 2004.
+
+   [266] A. Gupta, B. Liskov, and R. Rodrigues, One Hop Lookups for
+         Peer-to-Peer Overlays, 9th Workshop on Hot Topics in Operating
+         Systems (HotOS), 18-21 May 2003.
+
+   [267] A. Gupta, B. Liskov, and R. Rodrigues, Efficient routing for
+         peer-to-peer overlays, First symp. on Networked Systems Design
+         and Implementation (NSDI), Mar 29-31 2004, pp. 113-126.
+
+   [268] A. Mizrak, Y. Cheng, V. Kumar, and S. Savage, Structured
+         superpeers: leveraging heterogeneity to provide constant-time
+         lookup, IEEE Workshop on Internet Applications, June 23-24
+         2003.
+
+   [269] L. Adamic, R. Lukose, A. Puniyani, and B. Huberman, Search in
+         power-law networks, Physical review E, The American Physical
+         Society 64 (046135) (2001)
+
+
+
+
+Risson & Moors               Informational                     [Page 78]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [270] F. Banaei-Kashani and C. Shahabi, Criticality-based analysis
+         and design of unstructured peer-to-peer networks as "complex
+         systems", Proc. 3rd IEEE/ACM Int'l Symp. on Cluster Computing
+         and the Grid 2003, pp. 351-358.
+
+   [271] KaZaa, KaZaa Media Desktop, www.kazaa.com (2001)
+
+   [272] S. Sen and J. Wang, Analyzing peer-to-peer traffic across large
+         networks, Proc. second ACM SIGCOMM workshop on Internet
+         measurement, November 06-08 2002, pp. 137-150.
+
+   [273] DirectConnect, http:www.neo-modus.com (2001)
+
+   [274] S. Saroiu, K. Gummadi, R. Dunn, S. Gribble, and H. Levy, An
+         analysis of Internet content delivery systems, ACM SIGOPS
+         Operating Systems Review 36 (2002) 315-327.
+
+   [275] A. Loo, The Future or Peer-to-Peer Computing, Communications of
+         the ACM 46 (9) (2003) 56-61.
+
+   [276] B. Yang and H. Garcia-Molina, Comparing Hybrid Peer-to-Peer
+         Systems (extended), 27th Int'l Conf. on Very Large Data Bases,
+         September 11-14 2001.
+
+   [277] D. Scholl, OpenNap Home Page, http://opennap.sourceforge.net/
+         (2001)
+
+   [278] S. Ghemawat, H. Gobioff, and S.-T. Leung, The Google file
+         system, Proc. 19th ACM symposium on operating systems
+         principles 2003, pp. 29-43.
+
+   [279] I. Clarke, S. Miller, T. Hong, O. Sandberg, and B. Wiley,
+         Protecting Free Expression Online with Freenet, IEEE Internet
+         Computing 6 (1) (2002)
+
+   [280] J. Mache, M. Gilbert, J. Guchereau, J. Lesh, F. Ramli, and M.
+         Wilkinson, Request algorithms in Freenet-style peer-to-peer
+         systems, Proc. Second IEEE Int'l Conf. on Peer to Peer
+         Computing P2P'02, September 5-7 2002.
+
+   [281] C. Rohrs, Query Routing for the Gnutella Networks,
+         http://www.limewire.com/developer/query_routing/
+         keyword%20routing.htm Version 1.0 (2002)
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 79]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [282] I. Clarke, Freenet's Next Generation Routing Protocol,
+         http://freenetproject.org/index.php?page=ngrouting, 20th July
+         2003.
+
+   [283] A. Z. Kronfol, FASD: A fault-tolerant, adaptive scalable
+         distributed search engine, Master's Thesis
+         http://www.cs.princeton.edu/~akronfol/fasd/ 2002.
+
+   [284] S. Gribble, E. Brewer, J. M. Hellerstein, and D. Culler,
+         Scalable, Distributed Data Structures for Internet Service
+         Construction, Proc. 4th Symp. on Operating Systems Design and
+         Implementation OSDI 2000, October 2000.
+
+   [285] K. Aberer, Efficient Search in Unbalanced, Randomized Peer-to-
+         Peer Search Trees, EPFL Technical Report IC/2002/79 (2002)
+
+   [286] R. Honicky and E. Miller, A fast algorithm for online placement
+         and reorganization of replicated data, Proc. 17th Int'l
+         Parallel and Distributed Processing Symp., April 2003.
+
+   [287] G. S. Manku, Routing networks for distributed hash tables,
+         Proc. 22nd annual ACM Symp. on Principles of Distributed
+         Computing, PODC 2003, July 13-16 2003, pp. 133-142.
+
+   [288] D. Lewin, Consistent hashing and random trees: algorithms for
+         caching in distributed networks, Master's Thesis, Department of
+         Electrical Engineering and Computer Science, Massachusetts
+         Institute of Technology (1998)
+
+   [289] S. Lei and A. Grama, Extended consistent hashing: a framework
+         for distributed servers, Proc. 24th Int'l Conf. on Distributed
+         Computing Systems ICDCS 2004, March 23-26 2004.
+
+   [290] W. Litwin, Re: Chord & LH*, Email to Ion Stoica, March 23
+         2004a.
+
+   [291] J. Li, J. Stribling, R. Morris, F. Kaashoek, and T. Gil, A
+         performance vs. cost framework for evaluating DHT design
+         tradeoffs under churn, Proc. IEEE Infocom, Mar 13-17 2005.
+
+   [292] S. Zhuang, D. Geels, I. Stoica, and R. Katz, On failure
+         detection algorithms in overlay networks, Proc. IEEE Infocomm,
+         Mar 13-17 2005.
+
+   [293] X. Li, J. Misra, and C. G. Plaxton, Active and Concurrent
+         Topology Maintenance, The 18th Annual Conf. on Distributed
+         Computing (DISC 2004), Trippenhuis, Amsterdam, the Netherlands,
+         October 4 - October 7 (2004)
+
+
+
+Risson & Moors               Informational                     [Page 80]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [294] K. Aberer, L. O. Alima, A. Ghodsi, S. Girdzijauskas, M.
+         Hauswirth, and S. Haridi, The essence of P2P: a reference
+         architecture for overlay networks, Proc. of the 5th
+         international conference on peer-to-peer computing, Aug 31-Sep
+         2 2005.
+
+   [295] C. Tang, M. Buco, R. Chang, S. Dwarkadas, L. Luan, E. So, and
+         C. Ward, Low traffic overlay networks with large routing
+         tables, Proc. of ACM Sigmetrics Int'l Conf. on Measurement and
+         Modeling of Comp. Sys., Jun 6-10 2005, pp. 14-25.
+
+   [296] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, Handling
+         churn in a DHT, Proc. of the USENIX Annual Technical
+         Conference, June 2004.
+
+   [297] C. Blake and R. Rodrigues, High Availability, Scalable Storage,
+         Dynamic Peer Networks:  Pick Two, 9th Workshop on Hot Topics in
+         Operating Systems (HotOS), Lihue, Hawaii, 18-21 May (2003)
+
+   [298] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S.
+         Shenker, I. Stoica, and H. Yu, OpenDHT: a public DHT service
+         and its uses, Proc. of the conf. on Applications, technologies,
+         architectures and protocols for computer communications, Aug
+         22-26 2005, pp. 73-84.
+
+   [299] T. Gil, F. Kaashoek, J. Li, R. Morris, and J. Stribling,
+         p2psim, a simulator for peer-to-peer protocols,
+         http://www.pdos.lcs.mit.edu/p2psim/ (2003)
+
+   [300] K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao,
+         Distributed object location in a dynamic network, Theory of
+         Computing Systems (2004)
+
+   [301] N. Lynch, D. Malkhi, and D. Ratajczak, Atomic data access in
+         distributed hash tables, Proc. Int'l Peer-to-Peer Symp., March
+         7-8 2002.
+
+   [302] S. Gilbert, N. Lynch, and A. Shvartsman, RAMBO II: Rapidly
+         Reconfigurable Atomic Memory for Dynamic Networks, Technical
+         Report, MIT-CSAIL-TR-890 2004.
+
+   [303] N. Lynch and I. Stoica, MultiChord: A resilient namespace
+         management algorithm, Technical Memo MIT-LCS-TR-936 2004.
+
+   [304] J. Risson, K. Robinson, and T. Moors, Fault tolerant active
+         rings for structured peer-to-peer overlays, Proc. of the 30th
+         Annual IEEE Conf. on Local Computer Networks, Nov 15-17 2005,
+         pp. 18-25.
+
+
+
+Risson & Moors               Informational                     [Page 81]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [305] B. Awerbuch and C. Scheideler, Peer-to-peer systems for prefix
+         search, Proc. 22nd annual ACM Symp. on Principles of
+         Distributed Computing 2003, pp. 123-132.
+
+   [306] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica,
+         Towards a common API for structured P2P overlays, Proc. Second
+         Int'l Workshop on Peer to Peer Systems IPTPS 2003, February
+         2003.
+
+   [307] N. Feamster and H. Balakrishnan, Towards a logic for wide-area
+         Internet routing, Proc. ACM SIGCOMM workshop on Future
+         Directions in Network Architecture, August 25-27 2003, pp.
+         289-300.
+
+   [308] B. Ahlgren, M. Brunner, L. Eggert, R. Hancock, and S. Schmid,
+         Invariants: a new design methodology for network architectures,
+         Proc. ACM SIGCOMM workshop on Future Direction in Network
+         Architecture, August 30 2004, pp. 65-70.
+
+   [309] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction
+         to Algorithms, 2nd Edition. MIT Press, McGraw-Hill, Cambridge,
+         London, England, 2003.
+
+   [310] I. Abraham, D. Malkhi, and O. Dubzinski, LAND:Stretch
+         (1+epsilon) Locality Aware Networks for DHTs, Proc. ACM-SIAM
+         Symp. on Discrete Algorithms SODA-04 2004.
+
+   [311] S. Jain, R. Mahajan, and D. Wetherall, A study of the
+         performance potential of DHT-based overlays, Proc. of the 4th
+         Usenix symposium on internet technologies and systems (USITS),
+         Mar 2003.
+
+   [312] J. Risson, A. Harwood, and T. Moors, Stable high-capacity one-
+         hop distributed hash tables, Proc. of the IEEE Symposium on
+         Computers and Communications (ISCC'06), Jun 26-29 2006.
+
+   [313] V. Ramasubramanian and E. Sirer, Beehive: O(1) Lookup
+         Performance for Power-Law Query Distributions in Peer-to-Peer
+         Overlays, Proc. First Symp. on Networked Systems Design and
+         Implementation (NSDI'04), San Francisco, California, March
+         29-31 (2004) 99-112.
+
+   [314] I. Abraham, A. Badola, D. Bickson, D. Malkhi, S. Maloo, and S.
+         Ron, Practical locality-awareness for large scale information
+         sharing, Proc. 4th International Workshop on Peer-to-Peer
+         Systems, Feb 24-25 2005.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 82]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [315] B. Leong, B. Liskov, and E. Demaine, Epichord: parallelizing
+         the Chord lookup algorithm with reactive routing state
+         management, Proc. of the 12th International Conference on
+         Networks, Nov 2004.
+
+   [316] J. Li, J. Stribling, R. Morris, and F. Kaashoek, Bandwidth-
+         efficient management of DHT routing tables, Proc. 2nd Symposium
+         on Networked Systems Design and Implementation, May 2-4 2005.
+
+   [317] S. Rhea, B.-G. Chun, J. Kubiatowicz, and S. Shenker, Fixing the
+         embarrassing slowness of OpenDHT on PlanetLab, Proc. of the
+         Second USENIX Workshop on Real, Large Distributed Systems, Dec
+         13 2005.
+
+   [318] M. Costa, M. Castro, A. Rowstron, and P. Key, PIC: Practical
+         Internet coordinates for distance estimation, Proc. of the 24th
+         international conference on distributed computing systems, Mar
+         2004.
+
+   [319] M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M.
+         Theimer, H. Wang, and A. Wolman, An evaluation of scalable
+         application- level multicast built using peer-to-peer overlays,
+         Proc. of the 22nd Annual Joint Conf. of the IEEE Comp. and
+         Comm. Soc. (INFOCOM), 30 Mar - 3 Apr 2003, pp. 1510-1520.
+
+   [320] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker,
+         Application-level multicast using content-addressable networks,
+         Proc. of the Third International Workshop on Networked Group
+         Communication, Nov 7-9 2001.
+
+   [321] S. El-Ansary, L. Alima, P. Brand, and S. Haridi, Efficient
+         broadcast in structured P2P networks, Second Int'l Workshop on
+         Peer-to-Peer Systems (IPTPS 03), Berkeley, CA, USA, 20-21
+         February (2003)
+
+   [322] J. Li, K. Sollins, and D.-Y. Lim, Implementing aggregation and
+         broadcast over Distributed Hash Tables, ACM Computer
+         Communication Reviews 35 (1) (2005) 81-92.
+
+   [323] V. Pai, K. Tamilmani, V. Sambamurthy, K. Kumar, and A. Mohr,
+         Chainsaw: eliminating trees from overlay multicast, Proc. 4th
+         Int'l Workshop on Peer-to-Peer Systems, February 24-25 2005.
+
+   [324] K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, and M. Budiu,
+         Bimodal Multicast, ACM Trans. on Computer Systems 17 (2) (1999)
+         41-88.
+
+
+
+
+
+Risson & Moors               Informational                     [Page 83]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [325] Z. Zhang, S. Chen, Y. Ling, and R. Chow, Resilient capacity-
+         aware multicasting based on overlay networks, Proc. of the 25th
+         IEEE Int'l Conf. on Distributed Computing Systems, 6-10 June
+         2005, pp. 565-574.
+
+   [326] A. Bharambe, S. Rao, V. Padmanabhan, S. Seshan, and H. Zhang,
+         The impact of heterogeneous bandwidth constraints on DHT-based
+         multicast protocols, Proc. 4th Int'l Workshop on Peer-to-Peer
+         Systems, February 24-25 2005.
+
+   [327] A. Ghodsi, L. O. Alima, S. El-Ansary, P. Brand, and S. Haridi,
+         Self-correcting broadcast in distributed hash tables, Proc. of
+         the 15th IASTED International Conf. on Parallel and Distributed
+         Computing and Systems, Nov 2003.
+
+   [328] R. Mahajan, M. Castro, and A. Rowstron, Controlling the cost of
+         reliability in peer-to-peer overlays, Second Int'l Workshop on
+         Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
+
+   [329] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, Handling
+         churn in a DHT, Report No. UCB/CSD-03-1299, University of
+         California, also Proc. USENIX Annual Technical Conference, June
+         2003.
+
+   [330] M. Castro, M. Costa, and A. Rowstron, Performance and
+         dependability of structured peer-to-peer overlays, Microsoft
+         Research Technical Report MSR-TR-2003-94, December. Also 2004
+         Int'l Conf. on Dependable Systems and Networks, June 28-July 1
+         2003.
+
+   [331] D. Liben-Nowell, H. Balakrishnan, and D. Karger, Analysis of
+         the evolution of peer-to-peer systems, Annual ACM Symp. on
+         Principles of Distributed Computing 2002, pp. 233-242.
+
+   [332] L. Alima, S. El-Ansary, P. Brand, and S. Haridi, DKS(N,k,f): a
+         family of low communication, scalable and fault-tolerant
+         infrastructures for P2P applications, Proc. 3rd IEEE/ACM Int'l
+         Symp. on Cluster Computing and the Grid (2003) 344-350.
+
+   [333] D. Karger and M. Ruhl, Finding nearest neighbours in growth-
+         restricted metrics, Proc. 34th annual ACM symposium on Theory
+         of computing 2002, pp. 741-750.
+
+   [334] S. Ratnasamy, A Scalable Content-Addressable Network, Doctoral
+         Dissertation 2002.
+
+   [335] S. McCanne and S. Floyd, The LBNL/UCB Network Simulator.
+
+
+
+
+Risson & Moors               Informational                     [Page 84]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [336] M. Naor and U. Wieder, Novel architectures for P2P
+         applications: the continuous-discrete approach, Proc. fifteenth
+         annual ACM Symp. on Parallel Algorithms and Architectures, SPAA
+         2003, June 7-9 2003, pp. 50-59.
+
+   [337] N. D. de Bruijn, A combinatorial problem, Koninklijke
+         Netherlands: Academe Van Wetenschappen 49 (1946) 758-764.
+
+   [338] J.-W. Mao, "The Coloring and Routing Problems on de Bruijn
+         Interconnection Networks," in Doctoral Dissertation, National
+         Sun Yat-sen University, 2003.
+
+   [339] M. L. Schlumberger, De Bruijn communication networks, Doctoral
+         Dissertation 1974.
+
+   [340] M. Imase and M. Itoh, Design to minimize diameter on building-
+         block network, IEEE Trans. on Computers C-30 (6) (1981) 439-
+         442.
+
+   [341] S. M. Reddy, D. K. Pradhan, and J. G. Kuhl, Direct graphs with
+         minimal and maximal connectivity, Technical Report, School of
+         Engineering, Oakland University (1980)
+
+   [342] R. A. Rowley and B. Bose, Fault-tolerant ring embedding in de
+         Bruijn networks, IEEE Trans. on Computers 42 (12) (1993) 1480-
+         1486.
+
+   [343] K. Y. Lee, G. Liu, and H. F. Jordan, Hierarchical networks for
+         optical communications, Journal of Parallel and Distributed
+         Computing 60 (2000) 1-16.
+
+   [344] M. Naor and U. Wieder, Know thy neighbor's neighbor:  better
+         routing for skip-graphs and small worlds, The 3rd Int'l
+         Workshop on Peer-to-Peer Systems, February 26-27 2004.
+
+   [345] P. Fraigniaud and P. Gauron, The content-addressable networks
+         D2B, Technical Report 1349, Laboratoire de Recherche en
+         Informatique, January 2003.
+
+   [346] A. Datta, S. Girdzijauskas, and K. Aberer, On de Bruijn routing
+         in distributed hash tables: there and back again, Proc. Fourth
+         IEEE Int'l Conf. on Peer-to-Peer Computing, , 25-27 August
+         2004.
+
+   [347] W. Pugh, Skip lists: a probabilistic alternative to balanced
+         trees, Proc. Workshop on Algorithms and Data Structures, August
+         17-19 1989, pp. 437-449.
+
+
+
+
+Risson & Moors               Informational                     [Page 85]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [348] W. Pugh, Skip lists: a probabilistic alternative to balanced
+         trees, Communications of the ACM 33 (6) (1990) 668-676.
+
+   [349] J. Gray, The transaction concept: Virtues and limitations,
+         Proc. VLDB, September 1981.
+
+   [350] B. T. Loo, J. M. Hellerstein, R. Huebsch, S. Shenker, and I.
+         Stoica, Enhancing P2P file-sharing with internet-scale query
+         processor, Proc. 30th Int'l Conf. on Very Large Data Bases VLDB
+         2004, 29 August-3 September 2004.
+
+   [351] M. Stonebraker, P. Aoki, W. Litwin, A. Pfeffer, A. Sah, J.
+         Sidell, C. Staelin, and A. Yu, Mariposa: a wide-area
+         distributed database system, THE VLDB Journal - The Int'l
+         Journal of Very Large Data Bases (5) (1996) 48-63.
+
+   [352] V. Cholvi, P. Felber, and E. Biersack, Efficient Search in
+         Unstructured Peer-to-Peer Networks, Proc. Symp. on Parallel
+         Algorithms and Architectures, July 2004.
+
+   [353] S. Daswani and A. Fisk, Gnutella UDP Extension for Scalable
+         Searches (GUESS) v0.1,
+         http://www.limewire.org/fisheye/viewrep/~raw,r=1.2/limecvs/
+         core/guess_01.html (2002)
+
+   [354] A. Fisk, Gnutella Dynamic Query Protocol v0.1, Gnutella
+         Developer Forum (2003)
+
+   [355] O. Gnawali, A Keyword Set Search System for Peer-to-Peer
+         Networks, Master's Thesis 2002.
+
+   [356] Limewire, Limewire Host Count,
+         http://www.limewire.com/english/content/netsize.shtml (2004)
+
+   [357] A. Fisk, Gnutella Ultrapeer Query Routing,
+         http://groups.yahoo.com/group/the_gdf/files/Proposals/
+         Working%20Proposals/search/Ultrapeer%20QRP/ v0.1 (2003)
+
+   [358] A. Fisk, Gnutella Dynamic Query Protocol,
+         http://groups.yahoo.com/group/the_gdf/files/Proposals/
+         Working%20Proposals/search/Dynamic%20Querying/ v0.1 (2003)
+
+   [359] S. Thadani, Meta Data searches on the Gnutella Network
+         (addendum), http://www.limewire.com/developer/MetaProposal2.htm
+         (2001)
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 86]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [360] S. Thadani, Meta Information Searches on the Gnutella Networks,
+         http://www.limewire.com/developer/metainfo_searches.html (2001)
+
+   [361] P. Reynolds and A. Vahdat, Efficient peer-to-peer keyword
+         searching, ACM/IFP/USENIX Int'l Middleware Conference,
+         Middleware 2003, June 16-20 2003.
+
+   [362] W. Terpstra, S. Behnel, L. Fiege, J. Kangasharju, and A.
+         Buchmann, Bit Zipper Rendezvous, optimal data placement for
+         general P2P queries, Proc. First Int'l Workshop on Peer-to-Peer
+         Computing and Databases, March 14 2004.
+
+   [363] A. Singhal, Modern Information Retrieval: A Brief Overview,
+         IEEE Data Engineering Bulletin 24 (4) (2001) 35-43.
+
+   [364] E. Cohen, A. Fiat, and H. Kaplan, Associative Search in Peer to
+         Peer Networks: Harnessing Latent Semantics, IEEE Infocom 2003,
+         The 22nd Annual Joint Conf. of the IEEE Computer and
+         Communications Societies, March 30-April 3 2003.
+
+   [365] W. Muller and A. Henrich, Fast retrieval of high-dimensional
+         feature vectors in P2P networks using compact peer data
+         summaries, Proc. 5th ACM SIGMM international workshop on
+         Multimedia Information Retrieval, November 7 2003, pp. 79-86.
+
+   [366] M. T. Ozsu and P. Valduriez, Principles of Distributed Database
+         Systems, 2nd edition ed. Prentice Hall, 1999.
+
+   [367] G. Salton, A. Wong, and C. S. Yang, A vector space model for
+         automatic indexing, Communications of the ACM 18 (11) (1975)
+         613- 620.
+
+   [368] S. E. Robertson, S. Walker, and M. Beaulieu, Okapi at TREC-7:
+         automatic ad hoc, filtering, VLC and filtering tracks, Proc.
+         Seventh Text REtrieval Conference, TREC-7, NIST Special
+         Publication 500-242, July 1999, pp. 253-264.
+
+   [369] A. Singhal, J. Choi, D. Hindle, D. Lewis, and F. Pereira, AT&T
+         at TREC-7, Proc. Seventh Text REtrieval Conf. TREC-7, July
+         1999, pp. 253-264.
+
+   [370] K. Sankaralingam, S. Sethumadhavan, and J. Browne, Distributed
+         Pagerank for P2P Systems, Proc. 12th international symposium on
+         High Performance Distributed Computing HPDC, June 22-24 2003.
+
+   [371] I. Klampanos and J. Jose, An architecture for information
+         retrieval over semi-collaborated peer-to-peer networks, Proc.
+         2004 ACM symposium on applied computing 2004, pp. 1078-1083.
+
+
+
+Risson & Moors               Informational                     [Page 87]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [372] C. Tang, Z. Xu, and S. Dwarkadas, Peer-to-peer information
+         retrieval using self-organizing semantic overlay networks,
+         Proc. 2003 conference on Applications, Technologies,
+         Architectures and Protocols for Computer Communications, August
+         25-29 2003, pp. 175-186.
+
+   [373] C. Tang and S. Dwarkadas, Hybrid global-local indexing for
+         efficient peer-to-peer information retrieval, Proc. First Symp.
+         on Networked Systems Design and Implementation NSDI'04, March
+         29-31 2004, pp. 211-224.
+
+   [374] G. W. Furnas, S. Deerwester, S. T. Dumais, T. K. Landauer, R.
+         A. Harshman, L. A. Streeter, and K. E. Lochbaum, Information
+         retrieval using a singular value decomposition model of latent
+         semantic structure, Proc. 11th Annual Int'l ACM SIGIR Conf. on
+         Research and Development in Information Retrieval 1988, pp.
+         465-480.
+
+   [375] C. Tang, S. Dwarkadas, and Z. Xu, On scaling latent semantic
+         indexing for large peer-to-peer systems, The 27th Annual Int'l
+         ACM SIGIR Conf. SIGIR'04, ACM Special Interest Group on
+         Information Retrieval, July 2004.
+
+   [376] S. Milgram, The small world problem, Psychology Today 1 (61)
+         (1967)
+
+   [377] J. Kleinberg, The small-world phenonemon: An algorithmic
+         perspective, Proc. 32nd ACM Symp. on Theory of Computing (2000)
+
+   [378] Y. Petrakis and E. Pitoura, "On constructing small worlds in
+         unstructured peer-to-peer systems," in Current trends in
+         database technology (Proc. First Int'l Workshop on Peer-to-Peer
+         Computing and Databases, Heraklion, Crete, Greece, March 14),
+         vol. 3268, Lecture Notes in Computer Science: Springer, 2004,
+         pp. 415-424.
+
+   [379] A. Iamnitchi, M. Ripeanu, and I. Foster, Locating Data in
+         (Small World?) P2P Scientific Collaborations, First Int'l
+         Workshop on Peer-to-Peer Systems (IPTPS), Cambridge, MA, March
+         (2002)
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 88]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+   [380] Y. Ren, C. Sha, W. Qian, A. Zhou, B. Ooi, and K. Tan, Explore
+         the "small world phenomena" in pure P2P information sharing
+         systems, Proc. 3rd IEEE/ACM Int'l Symp. on Cluster Computing
+         and the Grid (2003) 232-239.
+
+   [381] G. S. Manku, M. Bawa, and P. Raghavan, Symphony:  Distributed
+         Hashing in a Small World, Proc. 4th USENIX Symp. on Internet
+         Technologies and Systems, March 26-28 2003.
+
+   [382] W. Litwin and S. Sahri, Implementing SD-SQL Server: a Scalable
+         Distributed Database System, CERIA Research Rerpot 2004-04-02,
+         April 2004.
+
+   [383] M. Jarke and J. Koch, Query Optimization in Database Systems,
+         ACM Computing Surveys 16 (2) (1984) 111-152.
+
+   [384] J. L. Bentley, Multidimensional binary search trees used for
+         associative searching, Communications of the ACM 18 (9) (1975)
+         509-517.
+
+   [385] B. Chun, I. Stoica, J. Hellerstein, R. Huebsch, S. Jeffery, B.
+         T. Loo, S. Mardanbeigi, T. Roscoe, S. Rhea, and S. Schenker,
+         Querying at Internet Scale, Proc. 2004 ACM SIGMOD international
+         conference on management of data, demonstration session 2004,
+         pp. 935-936.
+
+   [386] P. Cao and Z. Wang, Efficient top-K query calculation in
+         distributed networks, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp.
+         on Principles of Distributed Computing PODC 2004, July 25-28
+         2004, pp. 206-215.
+
+   [387] D. Psaltoulis, I. Kostoulas, I. Gupta, K. Birman, and A.
+         Demers, Practical algorithms for size estimation in large and
+         dynamic groups, Proc. Twenty-Third Annual ACM SIGACT-SIGOPS
+         Symp. on Principles of Distributed Computing, PODC 2004, July
+         25-28 2004.
+
+   [388] R. van Renesse, The importance of aggregation, Springer-Verlag
+         Lecture Notes in Computer Science  "Future Directions in
+         Distributed Computing".  A. Schiper, A. A. Shvartsman, H.
+         Weatherspoon, and B. Y. Zhao, editors. Springer-Verlag,
+         Heidelberg volume 2584 (2003)
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 89]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+Author's Addresses
+
+   John Risson
+   School of Elec Eng and Telecommunications
+   University of New South Wales
+   Sydney NSW 2052 Australia
+
+   EMail: jr@tuffit.com
+
+
+   Tim Moors
+   School of Elec Eng and Telecommunications
+   University of New South Wales
+   Sydney NSW 2052 Australia
+
+   EMail: t.moors@unsw.edu.au
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 90]
+
+RFC 4981            Survey of Research on P2P Search      September 2007
+
+
+Full Copyright Statement
+
+   Copyright (C) The IETF Trust (2007).
+
+   This document is subject to the rights, licenses and restrictions
+   contained in BCP 78, and except as set forth therein, the authors
+   retain all their rights.
+
+   This document and the information contained herein are provided on an
+   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
+   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
+   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
+   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
+   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
+   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+Intellectual Property
+
+   The IETF takes no position regarding the validity or scope of any
+   Intellectual Property Rights or other rights that might be claimed to
+   pertain to the implementation or use of the technology described in
+   this document or the extent to which any license under such rights
+   might or might not be available; nor does it represent that it has
+   made any independent effort to identify any such rights.  Information
+   on the procedures with respect to rights in RFC documents can be
+   found in BCP 78 and BCP 79.
+
+   Copies of IPR disclosures made to the IETF Secretariat and any
+   assurances of licenses to be made available, or the result of an
+   attempt made to obtain a general license or permission for the use of
+   such proprietary rights by implementers or users of this
+   specification can be obtained from the IETF on-line IPR repository at
+   http://www.ietf.org/ipr.
+
+   The IETF invites any interested party to bring to its attention any
+   copyrights, patents or patent applications, or other proprietary
+   rights that may cover technology that may be required to implement
+   this standard.  Please address the information to the IETF at
+   ietf-ipr@ietf.org.
+
+
+
+
+
+
+
+
+
+
+
+
+Risson & Moors               Informational                     [Page 91]
+