Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications
Ion Stoica†, Robert Morris‡, David Liben-Nowell‡, David R. Karger‡, M. Frans Kaashoek‡, Frank Dabek‡, Hari Balakrishnan‡
Abstract— I. INTRODUCTION
A fundamental problem that confronts peer-to-peer tem. applications is the efficient location of the node that stores a A Chord node requires information about O(logN) other desired data item. This paper presents Chord, a distributed
Peer-to-peer systems and applications are distributed systems the strength of the algorithm. We also report some initial results without any centralizedcontrol or hierarchical organization, in on how the Chord routing protocol can be extended to take into which each node runs software with equivalent functionality. account the physical network topology. Readers interested in an A review of the features of recent peer-to-peer applications application of Chord and how Chord behaves on a small Internet yields a long list: redundant storage, permanence, selection of testbed are referred to Dabek et al. [9]. The results reported by nearby servers, anonymity, search,https://.comauthentication, and hierar- Dabek et al. are consistent with the simulation results presented chical naming. Despite this rich set of features, the core oper- in this paper. ation in most peer-to-peer systems is efficient location of data The rest of this paper is structured as follows. Section II comitems. The contribution of this paper is a scalable protocol for pares Chord to related work. Section III presents the system lookup in a
dynamic peer-to-peer system with frequent node ar- model that motivates the Chord protocol. Section IV presents rivals and departures. Add the Chord protocol and proves several of its properties. Sec-
The Chord protocol supports just one operation: given a key, tion V presents simulations supportingour claims about Chord’s
lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis and simulations show that Chord is scalable: communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
it maps the key onto a node. Depending on the application using Chord, that node might be responsible for storing a value associated with the key. Chord uses consistent hashing [12] to assign keys to Chord nodes. Consistent hashing tends to balance load, since each node receives roughly the same number of keys, and requires relatively little movement of keys when nodes join and leave the system.
Previous work on consistent hashing assumes that each node is aware of most of the other nodes in the system, an approach that does not scale well to large numbers of nodes. In contrast, each Chord node needs “routing” information about only a few other nodes. Because the routing table is distributed, a Chord node communicates with other nodes in order to perform a lookup. In the steady state, in an N-node system, each node maintains informationabout only O(logN) other nodes, and resolves all lookups via O(logN) messages to other nodes. Chord maintains its routinginformationas nodesjoin and leave the sys-
The contributions of this paper are the Chord algorithm, the proof of its correctness, and simulation results demonstrating
This research was sponsored by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval
Warfare Systems Center, San Diego, under contract N66001001-8933. performance. Finally, we summarize our
contributions in Section VII.
II. RELATED WORK
Three features that distinguish Chord from many other peertopeer lookup protocols are its simplicity, provable correctness, and provable performance.
data item. A Chord-based application would store and find each value at the node to which the value’s key maps. provide search shortcuts [25]. The Globe system handles high
2
load on the logical rootAssignment Project Exam Helpby partitioning
objects among multi-
ple physical root servers using hash-like techniques. Chord per- III. SYSTEM MODEL
forms this hash function well enough that it can achieve scala- Chord simplifies the design of peer-to-peer systems and apbility without also involving any hierarchy, though Chord does plications based on it by addressing these difficult problems:
acts as a distributed hash function,
The distributeddata location protocoldevelopedby Plaxton et spreading keys evenly over the nodes; this provides a deal. [21] is perhaps the closest algorithm to the Chord protocol. gree of natural load balance.
The Tapestry lookup protocol [26], used in OceanStore [13], is • Decentralization: Chord is fully distributed: no node is a variant
important than any other. This improves robustness that queries make no more than a logarithmic number of hops and makes Chord
To clarify comparisons with related work, we will assume in this section a Chord-based application that maps keys onto values. A value can be an address, a document, or an arbitrary finding named hosts or services, while Chord can also be used to find data objects that are not tied to particular machines.
DNS provides a lookup service, with host names as keys and IP addresses (and otherhost information)as values. Chord could providethe same service by hashing each host name to a key [7]. Chord-based DNS would require no special servers, while ordinary DNS relies on a set of special root servers. DNS requires manual management of the routing information (NS records) that allows clients to navigate the name server hierarchy; Chord automatically maintains the correctness of the appropriate for loosely-organized peer-
The Freenet peer-to-peer storage system [5], [6], like Chord, is decentralized and symmetric and automatically adapts when hosts leave and join. Freenet does not assign responsibility for documents to specific servers; instead, its lookups take the form of searches for cached copies. This allows Freenet to provide a degree of anonymity, but prevents it from guaranteeing retrieval of existing documents or from providinglow bounds on retrieval costs. Chord does not provide anonymity, but its lookup operation runs in predictable time and always results in success or definitive failure.
The Ohaha system uses a consistent hashing-like algorithm map documents to nodes, and Freenet-style query routing [20]. world-wide search tree, much like DNS. Information about an object is stored in a particular leaf domain, and pointer caches
[15]. GLS relies on real-world geographic location information
analogous routing information. DNS only works well when host names are structured to reflect administrative boundaries; Chord imposes no naming structure. DNS is specialized to the task of
to route its queries; Chord maps its nodes to an artificial onedimensional space within which routing is carried out by an
As a result, it shares some of the weaknesses of Freenet. Archival Intermemory uses an off-line computed tree to map logical addresses to machines that store the data [4].
The Globe system [2] has a wide-area location service to map object identifiers to the locations of moving objects. Globe arranges the Internet as a hierarchy of geographical, topological, or administrative domains, effectively constructing a static and that keys are well-balanced. The Plaxton protocol’s main advantage over Chord is that it ensures, subject to assumptions about network topology, that queries never travel further in network distance than the node where the key is stored. Chord, on the other hand, is substantially less complicated and handles concurrent node joins and failures well. Pastry [23] is a algorithm similar to Grid’s.
Napster [18] and Gnutella [11] provide a lookup operation to find data in a distributed set of peers. They search based on usersupplied keywords, while Chord looks up data with unique identifiers. Use of keyword search presents difficulties in both systems. Napster uses a central index, resulting in a single point of failure. Gnutella floods each query over the whole system, so its communication and processing costs are high in large systems.
Chord has been used as a basis for a number of subsequent research projects. The Chord File System (CFS) stores files and meta-data in a peer-to-peer system, using Chord to locate storage blocks [9]. New analysis techniques have shown that Chord’s stabilization algorithms (with minor modifications) maintain good lookup performance despite continuous failure and joining of nodes [16]. Chord has been evaluated as a tool to serve DNS [7] and to maintain a distributed public key database for secure name resolution [1].
prefixbased lookup protocol that has properties similar to Chord. Like Tapestry, Pastry takes into account network topology to reduce the routing latency. However, Pastry achieves this at the cost of a more elaborated join protocol which initializes the routing table of the new node by using the information from nodes along the path traversed by the join message.
CAN uses a d-dimensional Cartesian coordinate space (for some fixed d) to implement a distributed hash table that maps keys onto values [22]. Each node maintains O(d) state, and the lookup cost is O(dN1/d). Thus, in contrast to Chord, the state maintained by a CAN node does not depend on the network size N, but the lookupcost increases faster than logN. If d = logN, CAN lookup times and storage needs match Chord’s. However, CAN is not designed to vary d as N (and thus logN) varies, so this match will only occur for the “right” N corresponding to 3
the fixed d. CAN requires an additional maintenance protocol to periodically remap the identifier space onto nodes. Chord also has the advantage that its correctness is robust in the face of partially incorrect routing information.
to-peer applications.
• Scalability: The cost of a Chord lookup grows as the log of the number of nodes, so even very large systems are feasible. No parametertuning is requiredto achieve this scaling.
• Availability: Chord automatically adjusts its internal tables to reflect newly joined nodes as well as node failures, ensuring that, barring major failures in the underlying network, the node responsible for a key can always be found. This is true even if the system is in a continuous state of change.
• Flexible naming: Chord places no constraints on the structure of the keys it looks up: the Chord key-space is flat. This gives applications a large amount of flexibility in how they map their own names to Chord keys.
The Chord software takes the form of a library to be linked with the applications that use it. The application interacts with Chord in two main ways. First, the Chord library provides a lookup(key) function that yields the IP address of the node responsible for the key. Second, the Chord software on each node notifies the application of changes in the set of keys that the node is responsible for. This allows the application software to, for example, move corresponding values to their new homes when a new node joins.
The application using Chord is responsible for providing any desired authentication, caching, replication, and user-friendly
Fig. 1. Structure of an example Chord-based distributed storage system.
naming of data. Chord’s flat key-space eases the implementation of these features. For example, an application could authenticate data by storing it under a Chord key derived from a cryptographic hash of the data. Similarly, an application could replicate data by storing it under two distinct Chord keys derived from the data’s application-level identifier.
the node responsible for storing a block, and then communicates with the block storage server on that node to read or write the block.
IV. THE CHORD PROTOCOL
planned departure) of existing nodes. In this paper we assume transitive (if A can route to B and B can route to C, then A can that communication in the underlying network is both route to C).
symmetric (if A can route to B, then B can route to A), and
A. Overview Chord assigns keys to nodes with consistent hashing [12], [14],
which has several desirable properties. With high probabilitythe At its heart, Chord provides fast distributed computation of a hash function mapping keys to nodes responsible for them. ity.
If someone wishes their data to be always available, but use to insert and retrieve data blocks identified with unique
hash function balances load (all nodes receive roughly the same
The following are examples of applications for which Chord number of keys). Also with high probability, when an Nth node can provide a good foundation: joins (or leaves) the network, only a O(1/N) fractionof the keys
Cooperative mirroring, in which multiple providers of are moved to a different location—this is clearly the minimum content cooperate to store and serve each others’ data. The
participants might,for
example, be a set of software develnecessary to maintain a balanced load.
Chord improves the scalability of consistent hashing by opment projects, each of which makes periodic releases. avoiding the requirement that every node know about every Spreading the total load evenly over all participants’ hosts other node. A Chord node needs only a small amount of “rout- lowers the total cost of the system, since each participant
ing” information about other nodes. Because this information is distributed, a node resolves the hash function by communicating
need providecapacity only forthe average load, not for that
participant’s peak load. Dabek et al. describe a realization with other nodes. In an N-node network, each node maintains of this idea that uses Chordto map data blocksonto servers; information about only O(logN) other nodes, and a lookup re- the application interacts with Chord achieve load balance, quires O(logN) messages. data
replication, and latency-basedAdd server selection [9].
Time-shared storage for nodes with intermittent connectiv-
This section describes the Chord protocol. The Chord protocol specifies how to find the locations of keys, how new nodes join the system, and how to recover from the failure (or their server is only occasionally available, they can offer to store others’ data while they are connected, in return for having their data stored elsewhere when they are disconnected. The data’s name can serve as a key to identify the (live) Chord node responsible for storing the data item at any given time. Many of the same issues arise as in the cooperative mirroring application, though the focus here is on availability rather than load balance. keys. The distributed hash table takes care of storing, caching, and replication of blocks. The distributed hash table uses Chord to identify
B. Consistent Hashing
5
Distributed indexes to support Gnutella- or Napster-like use the term “key” to refer to both the original key and its image keyword search. A key in this application could be derived under the hash function, as the meaning will be clear from from the desired keywords, while values could be lists of context. Similarly, the term “node” will refer to both the node machines offering documents with those keywords. and its identifier under the hash function. The identifier length
Large-scale combinatorial search, such as code breaking. In m must be large enough to make the probability of two nodes or this case keys are candidate solutions to the problem (such keys hashing to the same identifier negligible. as cryptographic keys); Chord maps these keys to the
Consistent hashing assigns keys to nodes as follows.
machines responsible for testing them as solutions.
Identifiers are ordered on an identifier circle modulo 2m. Key k
generalpurpose distributed hash table that multiple applications
− 1, then successor(k) is the first node clockwise from k. In the remainder of this paper, we will also refer to the identifier circle Of course, once the random hash function has been chosen, as the Chord ring. an adversary can select a badly distributed set of keys for that
Figure 2 shows a Chord ring with m = 6. The Chord ring has hash function. In our application, an adversary can generate a
to join with identifier 26, it would capture the key with identifier cessor pointers until they encounter a pair of nodes that straddle 24 from the node with identifier 32. the desired identifier; the second in the pair is the node the query The following resultsare proven in the papers that introduced maps to.
consistent hashing [12], [14]: Figure 3(a) shows pseudocode that implements simple key
Theorem IV.1: For any set of N nodes and K keys, with high lookup. Remote calls and variable references are preceded by probability: the remote node identifier, while local variable references and
1. Each node is responsible forat most keys procedure calls omit the local node. Thus n.foo() denotes a re-
2. When an (N + 1)st node joins or leaves the network, re- mote procedure call of procedure foo on node n, while n.bar, sponsibility for O(K/N) keys changes hands (and only to without parentheses, is an RPC to fetch a variable bar from or from the joining or leaving node). node n. The notation (a,b] denotes the segment of the Chord
When consistent hashing is implementedAdd as described above, ring obtained by moving clockwise from (but not
The consistent hash function assigns each node and key an mbit identifier using SHA-1 [10] as a base hash function. A node’s identifier is chosen by hashing the node’s IP address, while a key identifier is produced by hashing the key. We will including) a
the theorem proves a bound of. The consistent 10 nodes and stores five keys. The successor of identifier 10 is node 14, so key 10 would be located at node 14. Similarly, keys 24 and 30 would be located at node 32, key 38 at node 38, and key 54 at node 56.
Fig. 2. An identifier circle (ring) consisting of 10 nodes storing five keys.
hashing paper shows that can be reduced to an arbitrarily small constant by having each node run Ω(logN) virtual nodes, each with its own identifier. In the remainder of this paper, we will analyze all bounds in terms of work per virtual node. Thus, if each real node runs v virtual nodes, all bounds should be multiplied by v.
The phrase “with high probability” bears some discussion. A simple interpretation is that the nodes and keys are randomly chosen, which is plausible in a non-adversarial model of the until reaching (and including) b. large set of keys and insert into the Chord ring only those keys that map to a particular node, thus creating a badly distributed set of keys. As with standard hashing, however, we expect that a non-adversarialset of keys can be analyzed as if it were random.
Using this assumption, we state many of our results below as “high probability” results.
C. Simple Key Location
This section describes a simple but slow Chord lookup algorithm. Succeeding sections will describe how to extend the basic algorithm to increase efficiency, and how to maintain the correctness of Chord’s routing information.
Lookups could be implemented on a Chord ring with little per-node state. Each node need only know how to contact its current successor node on the identifier circle. Queries for a given identifier could be passed around the circle via these suc-
world. The probability distribution is then over random choices D. Scalable Key Location of keys and nodes, and says that such a random choice is
The lookup scheme presented in the previous section uses a
unlikely to produce an unbalanced distribution. A similar model numberof messages linear in the numberof nodes. To accelerate
is applied to analyze standard hashing. Standard hash functions lookups, Chord maintains additional routing information. This
distribute data well when the set of keys being hashed is additional information is not essential for correctness, which is random. When keys are not random,such a result cannotbe achieved as long as each node knows its correct successor. guaranteed— indeed, for any hash function, there exists some
As before, let m be the number of bits in the key/node
key set that is terribly distributed by the hash function (e.g., the identifiers. Each node n maintains a routing table with up to m
set of keys that all map to a single hash bucket). In practice, such entries (we will see that in fact only O(logn) are distinct), called
potential bad sets are considered unlikely to arise. Techniques the finger table. The ith entry in the table at node n contains the
have also been developed [3] to introduce randomness in the identity of the first node s that succeeds n by at least 2i−1 on the
hash function; given any set of keys, we can choose a hash identifier circle, i.e., s = successor(n+2i−1), where 1 ≤ i ≤ m
function at random so that the keys are well distributed with
(and all arithmetic is modulo 2m). We call node s the ith finger
high probability over the choice of hash function. A similar of node n, and denote it by n.finger[i] (see Table I). A finger
technique can be applied to consistent hashing; thus the “high table entry includes both the Chord identifier and the IP address
probability’ claim in the theorem above. Rather than select a
(and port number) of the relevant node. Note that the first finger
random hash funcFigure 3(b) shows an example in which node of n is the immediate successor of n on the circle; for 8 performs a lookup for key 54. Node 8 invokes find successor convenience we often refer to the first finger as the successor. for key 54 which eventually returns the successor of that key, node 56. The query visits every node on the circle between Notation Definition nodes 8 and 56. The result returns along the reverse of the path followed by the query.
(a)
(b)
Fig. 3. (a) Simple (but slow) pseudocode to find the successor node of an identifier id. Remote procedure calls and variable lookups are preceded by the remote node. (b) The path taken by a query from node 8 for key 54, using the pseudocode in Figure
3(a).
N1 N1 N32 N32
(a) (b)
Fig. 4. (a) The finger table entries for node 8. (b) The path a query for key 54 starting at node 8, using the algorithm in Figure 5.
// ask node n to find the successor of id Add n.find successor(id) if (id (n,successor])
TABLE I The example in Figure 4(a) shows the finger table of node 8.
Definition of variables for node n, using m-bit identifiers. The first finger of node 8 points to node 14, as node 14 is the first
node that succeeds (8+20) mod 26 = 9. Similarly, the last
finger[k] first node on circle that succeeds (n + 2k−1) mod 2m, 1 ≤ k ≤ m
successor the next node on the identifier circle; finger[1].node
predecessor the previous node on the identifier circle
finger of node 8 points to node 42, as node 42 is the first node that succeeds (8 + 25) mod 26 = 40.
This scheme has two important characteristics. First, each node stores information about only a small number of other nodes, and knows more about nodes closely following it on the identifier circle than about nodes farther away. Second, a node’s finger table generally does not contain enough information to directly determine the successor of an arbitrary key k. For example, node 8 in Figure 4(a) cannot determine the successor of key 34 by itself, as this successor (node 38) does not appear in node 8’s finger table.
Figure 5 shows the pseudocode of the find successor opera- return successor;
closest precedingnode(id);
return n0.find successor(id);
// search the local table for the highest predecessor of id n.closest precedingnode(id) for i = m downto 1 if
(finger[i] (n,id)) return finger[i];
return n;
Fig. 5. Scalable key lookup using the finger table.
tion, extended to use finger tables. If id falls between n and its successor, find successor is finished and node n returns its successor. Otherwise, n searches its finger table for the node n0 whose ID most immediately precedes id, and then invokes find successor at n0. The reason behind this choice of n0 is that the closer n0 is to id, the more it will know about the identifier circle in the region of id.
As an example, consider the Chord circle in Figure 4(b), and suppose node 8 wants to find the successor of key 54. Since the largest finger of node 8 that precedes 54 is node 42, node 8 will ask node 42 to resolve the query. In turn, node 42 will determine the largest finger in its finger table that precedes 54, i.e., node 51. Finally, node 51 will discover that its own successor, node 56, succeeds key 54, and thus will return node 56 to node 8.
Since each node has finger entries at power of two intervals around the identifier circle, each node can forward a query at least halfway along the remaining distance between the node and the target identifier. From this intuition follows a theorem:
Theorem IV.2: With high probability, the number of nodes that must be contacted to find a successor in an N-node network is O(logN).
Proof: Suppose that node n wishes to resolve a query for the successor of k. Let p be the node that immediately precedes k. We analyze the number of query steps to reach p.
Recall that if n =6 p, then n forwards its query to the closest predecessor of k in its finger table. Consider the i such that node p is in the interval [n+2i−1, n+2i). Since this interval is not empty (it contains p), node n will contact its ith finger, the first node f in this interval. The distance (number of identifiers) between n and f is at least 2i−1. But f and p are both in the interval [n + 2i−1,n + 2i), which means the distance between them is at most 2i−1. This means f is closer to p than to n, or equivalently, that the distance from f to p is at most half the distance from n to p. // create a new Chord ring. n.create() predecessor = nil; successor = n;
// join a Chord ring containing node n0. n.join(n0) predecessor
= nil; successor
= n0.find successor(n);
// called periodically. verifies n’s immediate // successor, and tells the successor about n. n.stabilize() x = successor.predecessor; if (x (n,successor)) successor = x; successor.notify(n);
// n0 thinks it might be our predecessor. n.notify(n0) if
(predecessor is nil or n0
(predecessor,n)) predecessor = n0; // called periodically. refreshes finger table entries.
// next stores the index of the next finger to fix. In order to ensure that lookups execute correctly as the set of If the distance between the node handling the query and the if (next > m) predecessor p halves in
each step, and is at most 2m initially, fingernext[next= 1];= find successor(n + 2next−1);
then within m steps theAssignment Project Exam Helpdistance will be
one, meaning we have arrived at p. // called periodically. checks whether predecessor has failed.
n.check predecessor()
In fact, as discussed above,we assume that nodeand key iden-
if (predecessor has failed) tifiers are random. In this case, the number of forwardings nec- predecessor = nil; essary will be
After 2logN forwardings, the distance between the current query node and the key k will be reduced to at most 2m/N2. The probability
Fig. 6. Pseudocode for stabilization.
that any other node is in this interval is at most 1/N, which is negligible. Thus, the next forwardingAdd
node.known Chord node, or n.create() to create a new Chord net-
n.fix fingers() next = next + 1;
In the section reporting our experimental results (Section V), we will observe (and justify) that the average lookup time is N.
Although the finger table contains room for m entries, in fact only O(logN) fingers need be stored. As we just argued in the above proof, no node is likely to be within distance 2m/N2 of any other node. Thus, the ith finger of the node, for any i ≤ m − 2logN, will be equal to the node’s immediate successor with high probability and need not be stored separately.
E. Dynamic Operations and Failures
In practice, Chord needs to deal with nodes joining the system and with nodes that fail or leave voluntarily. This section describes how Chord handles these situations.
E.1 Node Joins and Stabilization
Figure 6 shows the pseudocode for joins and stabilization. When node n first starts, it calls n.join(n0), where n0 is any work. The join() function asks n0 to find the immediate successor of n. By itself, join() does not make the rest of the network aware of n.
Every node runs stabilize() periodically to learn about newly joined nodes. Each time node n runs stabilize(), it asks its successor for the successor’s predecessor p, and decides whether p should be n’s successor instead. This would be the case if nodep recently joined the system. In addition, stabilize() notifies node n’s successor of n’s existence, giving the successor the chance to change its predecessor to n. The successor does this only if it knows of no closer predecessor than n.
Each node periodically calls fix fingers to make sure its finger table entries are correct; this is how new nodes initialize their finger tables, and it is how existing nodes incorporate new nodes into their finger tables. Each node also runs check predecessor periodically, to clear the node’s predecessor pointer if concurrent with the join are not disrupted. Figure 7 illustrates the join procedure, when n’s ID is 26, and the IDs of ns and np are 21 and
32, respectively.
predecessor is reached. Eventually fix fingers() will adjust Theorem IV.4: If we take a stable network with N nodes with finger table entries, eliminating the need for these linear scans. correctfinger pointers, andanotherset of up to N nodesjoins the
The following result, proved in [24], shows that the network, and all successor pointers (but perhaps not all finger inconsistent state caused by concurrent joins is transient. pointers) are correct, then lookups will still take O(logN) time
in the face of concurrentAssignment Project Exam Helpjoins and lost
and reordered messages. rounds of stabilization happen between any N node joins.
This stabilization protocol by itself won’t correct a Chord system that has split into multiple disjoint cycles, or a single cy- E.3 Failure and Replication cle that loops multiple times around the identifier space. These The correctness of the Chord protocol relies
of or- each node knows its successor. However, this invariant can be
dinary node joins. If produced, these cases can be detected and compromised if nodes fail. For example, in Figure 4, if nodes repaired by periodic sampling of the ring topology [24]. 14, 21, and 32 fail simultaneously, node 8 will not know that node38 is now its successor, since it has no finger pointingto 38.
As soon as the successor pointers are correct, calls to find
n.predecessor has failed; this allows it to accept a new predecessor in notify.
As a simple example, suppose node n joins the system, and its ID lies between nodes np and ns. In its call to join(), n acquires ns as its successor. Node ns, when notified by n, acquires n as its predecessor. When np next runs stabilize(), it asks ns for its predecessor (which is now n); np then acquires n as its successor. Finally, np notifies n, and n acquires np as its predecessor. At this point, all predecessor and successor pointers are correct. At each step in the process, ns is reachable from np using successor pointers; this means that lookups
pointers through the newly-joined nodes until the correct lead to incorrect lookups. Consider
Theorem IV.3: If any sequence of join operations is executed interleaved with stabilizations, then at some time after the last join the successor pointers will form a cycle on all the nodes in the network.
Now let us consider performance. Once stabilization has node fails during the find successor procedure, the lookup
Fig. 7. Example illustrating the join operation. Node 26 joins the system between nodes 21 and 32. The arcs represent the successor relationship. (a) Initial state:
node 21 points to node 32; (b) node 26 finds its successor (i.e., node 32) and points to it; (c) node 26 copies all keys less than 26 from node 32; (d) the stabilize procedure updates the successor of node 21 to node 26.
mance of Chord lookupsAssignment Project Exam Helpis likely to be
remove n from its successor list, and add ery node fails with probability 1/2, then with high probability the last node in n’s successor list to its own list. Similarly, node find successor returns the closest living successor to the query s will replace its predecessor with n’s predecessor. Here we askey. sume that n sends its predecessor to s, and the last node in its Proof: Before any nodes fail, each node was aware of its r successor list to p.
In other words, after some time each node is able to reach any other node in the network by following successor pointers.
Our stabilization scheme guarantees to add nodes to a Chord ring in a way that preserves reachability of existing nodes, even the target’s predecessor and the target. In that case the lookup will have to be forwarded through the intervening nodes, one at a time. But unless a tremendous number of nodes joins the system, the number of nodes between two old nodes is likely to be very small, so the impact on lookup is negligible. Formally, we can state the following result. We call a Chord ring stable if all its successor and finger pointers are correct.
Proof: The original set of fingers will, in O(logN) time, bring the query to the old predecessor of the correct node. With high probability, at most O(logN) new nodes will land between any two old nodes. So only O(logN) new nodes will need to be traversed along successor pointers to get from the old predecessor to the new predecessor.
More generally, as long as the time it takes to adjust fingers is less than the time it takes the network to double in size, lookups will continue to take O(logN) hops. We can achieve such adjustment by repeatedly carrying out lookups to update our fingers. It follows that lookups perform well so long as
Ω(log2 N)
To increase robustness, each Chord node maintains a successor list of size r, containing the node’s first r successors. If a node’s immediate successor does not respond, the node can
K30 K30
sor list for the most immediate predecessor of id. In addition, the pseudocode needs to be enhanced to handle node failures. If a substitute the second entry in its successor list. All r successors would have to simultaneously fail in order to disrupt the Chord ring, an event that can be made very improbable with modest values of r. Assuming each node fails independently with proceeds, after a timeout, by trying the next best predecessor among the nodes in the finger table and the successor list. The following results quantify the robustness of the Chord protocol, by showing that neither the success nor the perfor-
(a) (b)
list with its successor s by copying s’s successor list, removing K30
its r successors means that it can inform the higher layer software when successors come and go, and thus when the software should propagate data to new replicas.
E.4 Voluntary Node Departures
Since Chord is robust in the face of failures, a node voluntar- ily leaving the system could be treated as a node failure. How-
(c) (d)
probability p, the probability that all r successors fail simultaneously is only pr. Increasing r makes the system more robust.
Handling the successor list requires minor changes in the pseudocode in Figures 5 and 6. A modified version of the stabilize procedure in Figure 6 maintains the successor list. Successor lists are stabilized as follows: node n reconciles its
F. More Realistic Analysis its last entry, and prepending s to it. If node n notices that its successor has failed, it replaces it with the first live entry in its successor list and reconciles its successor list with its new successor. At that point, n can direct ordinary lookups for keys for which the failed node was the successor to the new successor. As time passes, fix fingers and stabilize will correct finger table entries and successor list entries pointing to the failed node.
A modified version of the closest preceding node procedure in Figure 5 searches not only the finger table but also the successors fail is (1/2)r, so with high probability every node is
aware of its immediate living successor. As was argued in the A. Protocol Simulator previous section, if the invariant that every node is aware of its
The Chord protocol can be implemented in an iterative or immediate successor holds, then all queries are routed properly, recursive style. In the iterative style, a node resolving a lookup since every node except the immediate predecessor of the query initiates all communication: it asks a series of nodes for has at least one better node to which it will forward the query. information from their finger tables, each time moving closer on Theorem IV.6: In a network that is initially stable, if every the node then fails with probability 1/2, then the expected time to execute find successor is O(logN).
The successor list mechanism also helps higher-layer software replicate data. A typical application using Chord might store replicas of the data associated with a key at the k nodes succeeding the key. The fact that a Chord node keeps track of Our analysis above gives some insight into the behavior of the Chord system, but is inadequate in practice. The theorems proven above assume that the Chord ring starts in a stable state and then experiences joins or failures. In practice, a Chord ring will never be in a stable state; instead, joins and departures will occur continuously, interleaved with the stabilization algorithm. The ring will not have time to stabilize before new changes happen. The Chord algorithms can be analyzed in this more general setting. Other work [16] shows that if the stabilization protocol is run at a certain rate (dependent on the rate at which nodes join and fail) then the Chord ring remains continuouslyin an “almost stable” state in which lookups are fast and correct.
V. SIMULATION RESULTS
In this section, we evaluate the Chord protocol by simulation.
The packet-level simulator uses the lookup algorithm in Figure 5, extended with the successor lists described in Section IV-E.3, and the stabilization algorithm in Figure 6.
a lookup fails, the node that initiated the lookup tries to make associating keys with virtual nodes, and mapping multiple virprogress using the nextclosest finger preceding the
target key. tual nodes (with unrelated identifiers) to each real node. This
A lookupis consideredto have succeeded if it reaches the cur- provides a more uniform coverage of the identifier space. For rent successor of the desired key. This is slightly optimistic: in a example, if we allocate logN randomly chosen virtual nodes to real system, there might be periods of time in which the real suc- each real node, with high probability each of the N bins will cessor
of a key has not yet acquiredthe data associated with the contain O(logN) virtual nodes [17]. key from the previous successor. However, this method allows To verify this hypothesis, we perform an experiment in which us to focus on Chord’s ability to perform lookups, rather than on we allocate r virtual nodes to each real node. In this case keys the higher-layer software’s ability to maintain consistency of its are associated with virtual nodes instead of real nodes. We conown data. sider again a network with 104 real nodes and 106 keys. Figure 9
Add shows the 1st and 99th percentiles for r = 1,2,5,10, and 20, re-
Chord ring to the desired successor. In the recursive style, each intermediate node forwards a request to the next node until it reaches the successor. The simulator implements the Chord protocol in an iterative style.
During each stabilization step, a node updates its immediate successor and one other entry in its successor list or finger table. Thus, if a node’s successor list and finger table contain a total of k unique entries, each entry is refreshed once every k stabilization rounds. Unless otherwise specified, the size of the successor list is one, that is, a node knows only its immediate successor. In addition to the optimizations described on Section IV-E.4, the simulator implements one other optimization. When the predecessor of a node n changes, n notifies its old predecessor p about the new predecessor p0. This allows p to set its successor to p0 without waiting for the next stabilization round. node n0 within 500 milliseconds, n concludes that n0 has left or failed. If n0 is an entry in n’s successor list or finger table, this entry is removed. Otherwise n informs the node from which it learnt about n0 that n0 is gone. When a node on the path of
Fig. 9. The 1st and the 99th percentiles of the number of keys per node as a function of virtual nodes mapped to a real node. The network has 104 real nodes and stores 106 keys.
tance. It is a standard fact that the distribution of this minimum is tightly approximatedby an exponentialdistribution with mean 2m/N. Thus, for example, the owned region exceeds twice the average value (of 2m/N) with probability e−2.
Chord makes the number of keys per node more uniform by
The delay of each packet is exponentially distributed with mean of
50 milliseconds. If a node n cannot contact another
B. Load Balance the probability density function (PDF) of the number of keys per node when there are 5 × 105 keys stored in the network. The
We first consider the ability of consistent hashing to allocate maximum number of nodes stored by any node in this case is keys to nodes evenly. In a network with N nodes and K keys we
457, or 9.1× the mean value. For comparison, the 99th percentile would like the distribution of keys to nodes to be tight around
N/K. is 4.6× the mean value.
One reason for these variations is that node identifiers do not
In particular, the 99th percentile decreases from 4.8× to 1.6× the cases some nodes store no keys. To clarify this, Figure 8(b) plots
mean value, while the 1st percentileincreases from 0 to 0.5× the mean value. Thus, adding virtual nodes as an indirection layer can significantly improve load balance. The tradeoff is that each real node now needs r times as much space to store the finger tables for its virtual nodes.
We make several observations with respect to the complexity incurred by this scheme. First, the asymptotic value of the query path length, which now becomes O(log(N logN)) =
O(logN), is not affected. Second, the total identifier space covered by the virtual nodes mapped on the same real node is with high probability an O(1/N) fraction of the total, which is the same on average as in the absence of virtual nodes. Since to the total identifier space covered by that node, the worst-case number of queries handled by a node does not change. Third, while the routing state maintained by a node is now O(log2 N), this value is still reasonable in practice; for N = 106, log2 N is only 400. Finally, while the number of control messages inihigh probability, this number is O(logN), where N is the total number of nodes in the network.
To understand Chord’s routing performance in practice, we simulated a network with N = 2k nodes, storing 100× 2k keys in all. We varied k from 3 to 14 and conducted a separate experiment for each value. Each node in an experiment picked a random set of keys to query from the system, and we measured
the number of queries handled by a node is roughly proportional each query’s path length.
(a) (b)
Fig. 8. (a) The mean and 1st and 99th percentiles of the number of keys stored per node in a 104 node network. (b) The probability density function (PDF) of the number of keys per node. The total number of keys is 5 × 105.
expect half the of the bits to be ones. As discussed in Theorem tiated by a node increases by a factor of O(logN), the asymptotic IV.2, after the logN most-significant bits have been fixed, in number of control messages received from other nodes is not expectation there is only one node remaining between the affected. To see why is this, note that in the absence of virtual current position and the key. Thus the average path length will nodes, with “reasonable” probability a real node is respon- be about sible for O(logN/N) of the identifier space. Since there are . O(N logN) fingers in the entire system, the number of fingers
that point to a real nodeis O(log2 N). In
contrast, if each real D. Simultaneous Node Failures
node maps logN virtual nodes, with high probability each real In this experiment, we evaluate the impact of a massive failnode is responsible for O(1/N) of the identifier space. Since ure on Chord’s performance and on its ability to perform correct
2 there are O(N log N) fingers in the entire system, with high lookups. We consider a network with N = 1,000
nodes, where probability the number of fingers thatpoint2to the virtual nodes each node maintains a successor list of size r = 20 = 2log2 N
mapped on the same real node is still O(log N). (see Section IV-E.3 for a discussion on the size of the successor list). Once the
network becomes stable, each node is made
C. Path Length to fail with probability p. After the failures occur, we perform
Chord’s performance depends inAdd part on the number of nodes
10,000 random lookups. For each lookup, we record the numthat must be visited to resolve a query. From Theorem IV.2, with ber of timeouts experienced by the lookup, the number of nodes
Figure 10(a) plots the mean, and the 1st and 99th percentiles experiments stop stabilization just before of path length as a function of k. As expected, the mean path the failures occur and do not remove the fingers pointing to length increases logarithmically with the number of nodes, as failed nodes from the finger tables. Thus the failed nodes are do the 1st and 99th percentiles. Figure 10(b) plots the PDF of detected only when they fail to respond during the lookup the path length for a network with 212 nodes (k = 12). protocol.
Figure 10(a) shows that the path length is about . The value of Table II shows the mean, and the 1st and the 99th percentiles the constant term () can be understood as follows. Consider a of the path length for the first 10,000 lookups after the failure
(a) (b)
Fig. 10. (a) The path length as a function of network size. (b) The PDF of the path length in the case of a 212 node network.
Fraction of Mean path length Mean num. of timeouts
failed nodes (1st, 99th percentiles) (1st, 99th percentiles)
0 3.84 (2, 5) 0.0 (0, 0)
0.1 4.03 (2, 6) 0.60 (0, 2)
0.2 4.22 (2, 6) 1.17 (0, 3)
0.3 4.44 (2, 6) 2.02 (0, 5)
0.4 4.69 (2, 7) 3.23 (0, 8)
0.5 5.09 (3, 8) 5.10 (0, 11)
values match well the measured number of timeouts shown in Table
II.
Finally, we note that in our simulations all lookups were successfully resolved, which supports the robustness claim of Theorem IV.5.
E. Lookups During Stabilization
TABLE II In this experiment, we evaluate the performance and accu-
The path length and the number of timeouts experienced by a lookup as racy of Chord lookups when nodes are continuously joining and function of the fraction of nodes that fail simultaneously. The 1st and the 99th leaving. The leave procedure uses the departure optimizations percentiles are in parenthesis. Initially,the network has 1,000 nodes. outlined in
Section IV-E.4. Key lookups are generated accord- ing to a Poisson process at a rate of one per second. Joins and voluntary leaves are modeled by a Poisson process with a mean arrival rate of R. Each node runs the stabilization routine at which is very close to the value of 3.84 shown in Table II for
p = 0. Add
node making a query for a randomly chosen key. Represent the distance in identifier space between node and key in binary. The most significant (say ith) bit of this distance can be corrected to 0 by following the node’s ith finger. If the next significant bit of the distance is 1, it too needs to be corrected by following a finger, but if it is 0, then no i − 1st finger is followed—instead, we move on the the i−2nd bit. In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query. Since the node identifiers are randomly distributed, we contactedduring the lookup(includingattempts to contact failed nodes), and whether the lookup found the key’s true current successor. A timeout occurs when a node tries to contact a failed node. The number of timeouts experienced by a lookup is equal to the number of failed nodes encountered by the lookup operation. To focus the evaluation on Chord’s performance immediately after failures, before it has a chance to correct its tables, these intervals that are uniformly distributed in the interval [15,45] seconds; recall that only the successor and one finger table en- occurs as a function of p, the fraction of failed nodes. As expected, the path length and the number of timeouts increases as the fraction of nodes that fail increases.
To interpret these results better, we next estimate the mean path length of a lookup when each node has a successor list of size r. By an argument similar to the one used in Section VC, a successor list of size r eliminates the last hops from the lookup path on average. The mean path length of a lookup becomes then . The last term (1) accounts for accessing the predecessor of the queried key once this predecessor is found in the successor list of the previous node. For N = 1,000 and r = 20, the mean path length is 3.82, Let x denote the progress made in the identifier space towards a target key during a particular lookup iteration, when there are no failures in the system. Next, assume that each node fails independently with probability p. As discussed in Section IVE.3, during each lookup iteration every node selects the largest alive finger (from its finger table) that precedes the target key. Thus the progress made during the same lookup iteration in the identifier space is x with probability (1 − p), roughly x/2 with probability p(1−p), roughly x/22 with probability p2 (1 − p), and so on. The expected progress made towards the target key is then a result, the mean path length becomes approximately
, where. As an example, the mean path length for p = 0.5 is 5.76. One reason for which the predicted value is larger than the measured value in Table II is because the series used to evaluate d is finite in practice. This leads us to underestimating the value of d, which in turn leads us to overestimating the mean path length.
Table III shows the means and the 1st and 90th percentiles of the path length and the number of timeouts experienced by the lookup operation as a function of the rate R at which nodes join and leave. A rate R = 0.05 corresponds to one node joining and leaving every 20 seconds on average. For comparison, recall that each node invokes the stabilize protocol once every 30 seconds. Thus, R ranges from a rate of one join and leave per 1.5 stabilization periods to a rate of 12 joins and 12 leaves per one stabilization period.
As discussed in Section V-D, the mean path length in steady state is about . Again, since N = 1,000 and r = 20, the mean path length is 3.82. As shown in Table III, the measured path length is very close to this value and does not change dramatically as R increases. This is because the number of timeouts experienced by a lookup is relatively small, and thus it has minimal effect on the path length. On the other hand, the number of timeouts increases with R. To understand this result,
18
Node join/leave rate Mean path length Mean num. of timeouts Lookup failures
(per second/per stab. period) (1st, 99th percentiles) (1st, 99th percentiles) (per 10,000 lookups)
0.05 / 1.5 3.90 (1, 9) 0.05 (0, 2) 0
0.10 / 3 3.83 (1, 9) 0.11 (0, 2) 0
0.15 / 4.5 3.84 (1, 9) 0.16 (0, 2) 2
0.20 / 6 3.81 (1, 9) 0.23 (0, 3) 5
0.25 / 7.5 3.83 (1, 9) 0.30 (0, 3) 6
0.30 / 9 3.91 (1, 9) 0.34 (0, 4) 8
0.35 / 10.5 3.94 (1, 10) 0.42 (0, 4) 16
0.40 / 12 4.06 (1, 10) 0.46 (0, 5) 15
TABLE III
The path length and the number of timeouts experienced by a lookup as function of node join and leave rates. The 1st and the 99th percentiles are in parentheses.
is then an interleaving of three Poisson processes. The fingered node departs as a Poisson process at rate R0 = R/N. Stabilization of that finger occurs (and detects such a departure)at rate S. In each stabilization round, a node stabilizes either a node in its finger table or a node in its successor list (there are 3logN such nodes in our case). Since the stabilization operation reduces to a lookup operation (see Figure 6), each stabilization operation will use l fingers on the average, where l is the mean lookuppath length. As result, the rate at which a finger is touched by the stabilization operation is S = (1/30) l/(3logN) where 1/30 is the average rate at which each node invokes stabilization. Finally, lookups using that finger are also a Poisson process. Recall that lookups are generated (globally) as a Poisson process with rate of one lookup per second. Each such lookup uses l fingers on average, while there are N logN fingers in total. Thus a particular finger is used with probability l/(N logN), meaning that the finger gets used according to a Poisson process at rate L = l/(N logN).
We have three interleaved Poisson processes (the lookups, departures, and stabilizations). Such a union of Poisson processes is itself a Poisson process with rate equal to the sum of the three values shown in Table III.
The last column in Table III shows the number of lookup failures per 10,000 lookups. The reason for these lookup failures
about. As a result, for any key id (n,s), n will return node s2 ask f for its successor list, and then ping each node in the list.
The network has roughly 1,000 nodes.
consider the following informal argument. underlying rates. Each time an “event” occurs in this union
of an interleaving of three types of events: (1) stabilizations of 0 R that finger, (2) departures of the node pointed at
and
(3) lookups that traverse the finger. A lookup causes a timeout if
N 90logN N logN by the finger,
the finger points at a departednode. This occurs precisely when R
the event immediately preceding the lookup was a departure—if the preceding event was a stabilization, then the node currently pointed at is alive; similarly, if the previous event was a lookup, In particular, the event immediately preceding any lookup is then that lookup timed out an causedhttps://.comeviction of that dead fin- a departure with this probability. This is the probability that ger pointer. So we need merely determine the fraction of lookup the lookup encounters the timeout. Finally, the expected numevents in the history that are immediately preceded by a depar- ber of timeouts experienced by a lookup operation is l pt = ture event.
R/(R/l + N/(90logN) + 1/log(N)). As examples, the ex-
19
To simplify the analysis we assumeAdd that, like joins and leaves, pected number of timeouts is 0.041 for R = 0.05, and 0.31 for stabilization is run according to a Poisson process. Our history R = 0.4. These values are reasonable close to the measured
F. Improving Routing Latency While Chord ensures that the average path length is only , the lookup latency can be quite large. This is because the node identifiers are randomly distributed, and therefore nodes close in the identifier space can be far away in the underlying network. In previous work [8] we attempted to reduce lookup latency with a simple extension of the Chord protocol that exploits only the information already in a node’s finger table. The idea was to choose the next-hop finger based on both progress in identifier The node can update n either periodically, or when it detects that n has failed. Observe that this heuristic can be applied only in the recursive (not the iterative) implementation of lookup, as the original querying node will have no distance measurements to the fingers of each node on the path.
To illustrate the efficacy of this heuristic, we consider a Chord system with 216 nodes and two network topologies:
• 3-d space: The network distance is modeled as the geometric distance in a 3-dimensional space. This model is motivated by recent research [19] showing that the network latency between two nodes in the Internet can be modeled
does not require any additional state, its performance is difficult to analyze [8]. In this section, we present an alternate the routing table by maintaining, for each finger f, only the closest node n among f’s s successors. To update n, a node can
Number of
fingers’ successors
(s) Stretch (10th, 90th percentiles)
Iterative Recursive
3-d space Transit stub 3-d space Transit stub
1 7.8 (4.4, 19.8) 7.2 (4.4, 36.0) 4.5 (2.5, 11.5) 4.1 (2.7, 24.0)
2 7.2 (3.8, 18.0) 7.1 (4.2, 33.6) 3.5 (2.0, 8.7) 3.6 (2.3, 17.0)
4 6.1 (3.1, 15.3) 6.4 (3.2, 30.6) 2.7 (1.6, 6.4) 2.8 (1.8, 12.7)
8 4.7 (2.4, 11.8) 4.9 (1.9, 19.0) 2.1 (1.4, 4.7) 2.0 (1.4, 8.9)
16 3.4 (1.9, 8.4) 2.2 (1.7, 7.4) 1.7 (1.2, 3.5) 1.5 (1.3, 4.0)
TABLE IV
The stretch of the lookup latency for a Chord system with 216 nodes when the lookup is performed both in the iterative and recursive style. Two network models
are considered: a 3-d Euclidean space, and a transit stub network.
network, trying to maximize the former while minimizing the The latter is computed as the round-trip time between the latter. While this protocol extension is simple to implement and initiator and the server responsible for the queried ID.
protocol extension, which provides better performance at the cost of slightly increasing the Chord state and message complexity. We emphasize that we are actively exploring techniques to minimize lookup latency, and we expect further improvements in the future.
We use the lookup stretch as the main metric to evaluate our heuristic. The lookup stretch is defined as the ratio between the
(1) latency of a Chord lookup from the time the lookup is f and simply initiated to the time the result is returned to the initiator, and the (2) latency of an optimal lookup using the underlying network. a node to the closest node from a set of s + 1 random nodes (with good accuracy) as the geometric distance in a ddimensional Euclidean space, where d ≥ 3.
• Transit stub: A transit-stub topology with 5,000 nodes, where link latencies are 50 milliseconds for intra-transit
its s successors. For simplicity, we choose s = r, where space and latency in the underlying r is the length of the successor list; one could reduce the storage requirements for of the lookup stretch over 10,000 lookups for both the iterative
The main idea of our scheme is to maintain a set of alternate and the recursive styles. The results suggest that our heuristic is
nodes for each fingerAssignment Project Exam Help(that is, nodes with
similar identifiers that quite effective. The stretch decreases significantly as s increases are roughly equivalent for routing purposes), and then route the from one to 16. queries by selecting the closest node among the alternate nodes As expected, these results also demonstrate that recursive according to some network proximity metric. In particular, ev- lookups execute faster than iterative lookups. Without any laery node
optimization, the recursive lookup style is expected to be
diate successors of f. In addition, we modify the find successor approximately twice as fast as the iterative style: an iterative function in Figure 5 accordingly: instead of simply returning the lookup incurs a round-trip latency per hop, while a recursive largest finger, f, that precedes the queried ID, the function re- lookup incurs a one-way latency. turns the closest node (in terms
the expected distance from
VI. FUTURE WORK
Work remains to be done in improving Chord’s resilience against network partitions and adversarial nodes as well as its efficiency.
Chord can detect and heal partitions whose nodes know of each other. One way to obtain this knowledge is for every node to know of the same small set of initial nodes. Another approach might be for nodes to maintain long-term memory of a random set of nodes they have encounteredin the past; if a partition forms, the random sets in one partition are likely to include nodes from the other partition.
A malicious or buggy set of Chord participants could present an incorrect view of the Chord ring. Assuming that the data
Chord is being used to locate is cryptographicallyauthenticated, this is a threat to availability of data rather than to authenticity. One way to check global consistency is for each node n to periodically ask other nodes to do a Chord lookup for n; if the lookup does not yield node n, this could be an indication for victims that they are not seeing a globally consistent view of the Chord ring.
VII. CONCLUSION
Many distributed peer-to-peer applications need to determine the node that stores a data item. The Chord protocol solves this challenging problem in decentralized manner. It offers a powerful primitive: given a key, it determines the node responsible for storing the key’s value, and does so efficiently. In the steady state, in an N-node network, each node maintains routing information for only O(logN) other nodes, and resolves all lookups via O(logN) messages to other nodes.
[7] COX, R., MUTHITACHAROEN, A., AND MORRIS, R.
Serving DNS using Chord. In First International Workshop on Peer-to-Peer Systems (Cambridge, MA, Mar. 2002).
[9] DABEK, F., KAASHOEK, F., KARGER, D., MORRIS,
R.,
AND STOICA, I. Wide-area cooperative storage with
CFS. In Proc. ACM SOSP’01 (Banff, Canada, 2001), pp. 202–215.
[10] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information
Service, Springfield, VA, Apr. 1995.
[11] Gnutella. http://gnutella.wego.com/.
[12] KARGER, D., LEHMAN, E., LEIGHTON, F., LEVINE, M., LEWIN, D., AND PANIGRAHY, R. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on
[15] LI, J., JANNOTTI, J., DE COUTO, D., KARGER, D., geographic ad hoc routing. In Proceedings of the 6th ACM AND MORRIS, R. A scalable location service for International Conference on Mobile Computing and
Attractive featuresAssignment Project Exam Helpof Chord include its
simplicity, provable [16] LIBEN-NOWELL, D., BALAKRISHNAN, H., AND KARGER, D. R. Obcorrectness, and provable performance even in the
face of con- servations on the dynamic evolution of peer-to-peer networks. In First
International Workshop on Peer-to-Peer Systems (Cambridge, MA, Mar. current node arrivals and departures. It continues to function 2002). correctly, albeit at degraded performance, when a node’s infor-
[17] MOTWANI, R., AND RAGHAVAN, P. Randomized Algorithms. Cambridge mation is only partially correct.
analysis and [18]
Napster.Universityhttp://www.napster.com/Press, New York, NY, 1995. .
simulation results confirm that Chord scales well with the num- [19] NG, T. S. E., AND ZHANG, H. Towards global network positioning. In ber of nodes, recovers from large numbers of simultaneous node ACM SIGCOMM Internet Measurements Workshop 2001 (San dur-
Francisco, CA, Nov. 2001). failures and joins, and answers most lookups correctly even [20] Ohaha, Smart decentralized peer-to-peer
component for peer- [21] PLAXTON, C., RAJARAMAN, R., AND RICHA, A. Accessing nearby ing recovery. ohaha.com/design.html. copies of replicated objects in a distributed environment. In Proceedings
[13] KUBIATOWICZ, J., BINDEL, D., CHEN, Y., CZERWINSKI, S., EATON, P., GEELS, D., GUMMADI, R., RHEA, S., WEATHERSPOON, H., WEIMER, W., WELLS, C., AND ZHAO, B. OceanStore: An architecture
190– 201.
[14] LEWIN, D. Consistent hashing and random trees:
Algorithms for caching in distributed networks. Master’s thesis, Department of EECS, MIT, 1998. Available at the MIT
Library, http://thesis.mit.edu/. to-peer, large-scale distributed applications such as cooperative file sharing, time-shared available storage systems, distributed indices for document and service discovery, and large-scale distributed computing platforms. Our initial experience with Chord has been very promising. We have already built several peer-to-peer applications using Chord, including a cooperative file sharing application [9]. The software is available at http://pdos.lcs.mit.edu/chord/.
REFERENCES
[1] AJMANI, S., CLARKE, D., MOH, C.-H., AND RICHMAN, S. ConChord:
Cooperative SDSI certificate storage and name resolution. In First International Workshop on Peer-to-Peer Systems (Cambridge, MA, Mar. 2002).
[3] CARTER, J. L., AND WEGMAN, M. N. Universal classes of hash functions. Journal of Computer and System Sciences 18, 2 (1979), 143–154.
[6] CLARKE, I., SANDBERG, O., WILEY, B., AND HONG, T. W. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the ICSI
[23] ROWSTRON, A., AND DRUSCHEL, P. Pastry: Scalable, distributed object location and routing for large-scale peerto-peer systems. In Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001) (Nov. 2001), pp. 329–350.
[24] STOICA, I., MORRIS, R., LIBENNOWELL, D., KARGER, D.,
KAASHOEK, M. F., DABEK, F., AND BALAKRISHNAN,
H. Chord:
A scalable peer-to-peer lookup service for Internet applications. Tech. Rep. TR-819, MIT LCS, 2001. http://www.pdos.lcs.mit.edu/ chord/papers/.
[25] VAN STEEN, M., HAUCK, F., BALLINTIJN, G., AND TANENBAUM, A.
Algorithmic design of the Globe wide-area location service. The Computer Journal 41, 5 (1998), 297–310.
[26] ZHAO, B., KUBIATOWICZ, J., AND JOSEPH, A.
2001.
