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

   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

   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].

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.

   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

   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].

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

   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].

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

   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

      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

   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

   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

   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

   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

   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

   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

   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

   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.