CS 739 - Reviews - Spring 2011

Summary:

An important problem in most p2p system is efficient location of data items in a scalable manner. This paper describes Chord, a distributed lookup protocol to efficiently locate the node that stores a particular data item.

Problem:

A fundamental problem in peer-to-peer applications is how to provide efficient data item lookup service. Most previous work focusing on consistent hashing assumed that each node needs to be aware of most other nodes. However, this is not practical for a large number of nodes. So, the efficiency and scalability are the core challenges.

Contributions:

1. Performance guarantees: Chord improves the consistent hashing by maintaining extra successor node related routing information to achieve a scalable key location service. In a network with N nodes, each Chord node only needs to maintain information about O(logN) other nodes; a lookup will be guaranteed with O(logN) messages; during the node joining and leaving, the update process just requires O(log2N) messages.

2. Failure handling: Chord carefully deals with concurrent node join and failure. A stabilization protocol is proposed to keep nodes' successor pointers up to date to guarantee the correctness of lookups.

3. Thorough evaluations: Both simulations and prototype experiments with different setups are conducted to verify the correctness and performance of Chord. The results confirm the guaranteed performance and scalability of Chord in a reasonable large p2p system.

Flaws:

1. Chord does not consider the physical network locality of nodes when it routes the messages. Chord purely depends on the hash value of key as the distance of two node, which does not reflect the actual routing distance. So, Chord missed opportunity to improve its lookup latency. A related work which considers the network locality is presented in Peter Druschel's Pastry paper.

2. Another flaw is that a malicious Chord node could affect the consistency of Chord state, which is discussed by authors in the future work section. I think malicious attack is very frequent in peer-to-peer system. Thus, the security should be a high priority for the design.

Applicability:
Chord provides an efficient and scalable primitive which can be used to build lots of other applications. For example, building a distribute key-value store on Chord (Dynamo maybe), building a distributed file system on Chord (GFS maybe, using Chord to lookup the data chuck location given the data chunk ID). Basically, Chord can be widely used in a system which needs scalable lookup services.

Summary
This paper proposes a distributed lookup protocol for locating the node that
stores a particular data item in large peer to peer systems.

Problem
How to efficiently locate the node that stores a particular data item in large
peer to peer systems with frequent node arrivals and departures?

Contribution
This paper proposes a distributed lookup protocol, Chord, to map a key onto a node.
- Chord uses a variant of consistent hashing to assign keys to Chord nodes,
where in a N-node P2P system, each node only has to maintain routing
information about O(log N) nodes, and resolves all lookups via O(log N)
messages to other nodes, Updates to the routing information for nodes
leaving and joining require only O(log^2 N) messages.
- Chord is load-balanced in that consistent hashing spreads keys evenly over the
nodes.
- Chord is highly scalable because the cost of a Chord lookup grows as the log
of the number of nodes.
- Chord handles concurrent node joins/leaves well in that Chord automatically
adjusts its internal tables to reflect newly joined nodes as well as node
failures.
- Chord is simply to focus on distributed lookup in flat key space, and it
shifts the responsibility of authentication, caching, replication, and
user-friendly naming of data to applications.

Flaw
In Section 6.1, the paper mentions "The Chord protocol can be implemented in an
iterative or recursive style". However, in both simulation and experiment, Chord
is only implemented as iterative style, and the paper doesn't give the reason
why they choose iterative style, instead of using recursive style. It seems that
it would yield better performance for Chord to use recursive style to select
particular servers with low latency network path, as mentioned in Section 7.

Applicability
Chord focuses on distributed key lookup that has quite a few of applications,
including Cooperative Mirroring, Time-shared storage, Distributed Indices, Large
scale combinatorial searches etc.

Summary

The paper provides a summary and evaluation of the Chord Protocol, which provides a foundation to build large-scale peer-to-peer systems.

Problem

Distributed systems, which utilize consistent hashing as a means of load balancing as well as key lookup, require a node to be aware of most of the other nodes present in the system. This requirement limits the scalability of a system as well as requires the environment to be fairly stable with infrequent updates due to node additions and removals.

Contribution

The major contribution of the paper is the Chord protocol, which allows for large distributed peer-to-peer systems with frequent node arrivals and departures. The system requires that each node maintain information for about log N nodes as opposed to a majority of most nodes, and requires a maximum path length of log N to resolve a query. The paper describes the routing tables used in the Chord protocol as well as the algorithms necessary to populate and maintain correct routing information as well as the search algorithm to locate a key via the routing table.

In addition to providing an outline of the Chord protocol, the paper also provides several experiments and simulations to measure the performance of a system built using the Chord protocol as well as application correctness (i.e. correctly locating a key) during the stabilization period of the system.

Flaws

The paper does an excellent job of describing the Chord protocol, providing several theorems and proofs as well as experiments to prove Chord’s scalability in a distributed environment. However, one deficiency with the system is the lack of network topology and locality, which can be utilized during a lookup. Instead the authors’ decide to focus on the number of hops as the measure of lookup performance, rather than geographical distance / link speed.

Applicability to real systems

The Chord system provides the foundation to develop many distributed hash table systems. Several examples sited in the paper include: cooperative mirroring, time-shared storage and distributed indexes.

Summary: Chord introduces a distributed naming protocol for decentralized peer-to-peer systems. The protocol achieves load balance (keys are evenly spread across nodes), is effecient in terms of state information on each node and communication during lookups, and is tolerant to dynamically changing node membership. A few simulation-based results are presented showing its viability.

Problem: The basic problem Chord addresses is very simple. In a system of many nodes each of which is responsible for storing some subset of keys, how does one discover which node holds a given key. The most naive solution is for each node to keep a routing table for all other nodes and keys in the system. This infeasible approach requires large amounts of state information and excessive communication when nodes join and leave the system.

Contribution: Consistent hashing had already been used to attach this problem, but previous designs required that nodes are aware of most or all other nodes in the system. This would not scale to very large memberships. Instead in Chord the routing information itself is distributed so that any single node only needs to store routing tables for a small subset of the total nodes in the system (the finger table). Lookups via the finger table requires O(log N) messages (with high probability).

Chord also defines protocols for nodes joining the system. The new node needs only to be informed of one existing node to find all the information it needs to join the system. It must 1. Initialize its finger table, 2. Update the fingers and predecessors of some existing nodes, and 3. Arrange to get the keys/values it is now responsible for. This operation is shown to take O(log^2 N) messages (with high probability). The authors also discuss difficulties that arise when there are many concurrent joins by loosening the finger table invariant and instead using a stabilization protocol. Failure tolerance is achieved with replication and successor lists.

Flaws: One weakness of the vanilla Chord protocol is that it does not take network latency considerations into account. A key is mapped to a node regardless of whether it is spatially far from requestors or burdened by network bottlenecks. The authors also point out that the system does not provide anonymity or full protection against malicious nodes. You could argue that these are particularly important concerns for p2p systems for certain, possibly not entirely legal, uses.

Applications: Several applications were pointed out in the paper including cooperative mirroring, time shared storage, distributed indices, and combinatorial searching. Another interesting application is as a replacement for DNS. With Chord there is no need for a special set of distinguished root servers, and it has a more flexible flat (non-hierarchical) namespace.

Summary:

This paper describes Chord, a completely decentralized peer-to-peer system for mapping keys to nodes responsible for them. Chord can be used as a foundation for many P2P applications, as it solves the common problem of distributing and locating data amongst many nodes reliably and efficiently.

Problem:

Many peer-to-peer systems require the ability to locate nodes where particular data resides (the authors cite examples such as distributed indexes and cooperative and timesharing-based mirroring). It is desirable that the process of locating a node for a particular data item be fast, highly scalable (and incrementally scalable, such that nodes can join in an ad-hoc fashion), and robust (so that a large number of nodes frequently failing or leaving does not break the ability to locate data). The Chord developers also stress the equality of nodes: there are no "special" nodes that play a different role than the others, and load (both in terms of keys stored and network traffic) is balanced across all nodes in the system.

Contributions:

Chord builds on consistent hashing. As in consistent hashing, keys and nodes are hashed into the same circular range, with the node immediately after a key on the ring being responsible for that key. When a single node joins or leaves the ring, key relocations are limited to that node's immediate region of the ring.

Chord extends the basic model of consistent hashing by having each node store some additional routing information. To speed up searches, each node has a finger table which keeps track of nodes which succeed it by doubling distances on the ring. To find the node responsible for some key, a search can start at any node, which will then pick the closest predecessor for that key in its finger table, repeating this process at that node and so on, halving the distance to the target node with each iteration and, with high probability, reaching the target in logarithmic time.

To better deal with node failures, each node in Chord also maintains a successor list of some number of its immediate successors on the ring. If a node notices that its first successor has failed, it can replace it with the first live entry on its successor list and the system will continue to work correctly. To maintain the correctness of successor lists and finger tables (for efficient lookup), a periodic stabilization procedure is run.

Flaws:

By striving for complete symmetry of nodes and not using virtual nodes, the Chord system balances load across all nodes. In a real P2P system, however, nodes are likely to have widely varying hardware and network capacity, and better performance would likely be achieved if load balance reflected this. Adding virtual nodes and allowing a varying number of virtual nodes per physical node could address this.

The authors note that it is possible for Chord to devolve into a pathological state (usually because of a network partition) where the system becomes partitioned into more than one ring. The authors propose a method for healing partitions if nodes are aware of the existence of nodes in the other partition and are eventually able to contact them.

It is also noted that a buggy or malicious implementation of Chord could present an incorrect view of the ring (essentially a Byzantine failure) and undermine the availability of the system. Techniques similar to those used for partition healing could be used to deduce whether a node sees an incomplete or incorrect view of the system,

Applicability:

Key distribution and location is indeed a key problem in P2P systems. Chord forms a flexible basis for such systems, and was in fact used to implement the CFS distributed filesystem. However, many successful real-world systems don't follow the completely symmetric design of Chord and achieve high performance by doing specific tasks on some "special purpose" nodes (for example, trackers and webseeds in BitTorrent or the master in GFS).

Summary

This paper presents Chord, a distributed lookup protocol, to address the problem about how to locate the node that stores a particular data item in a peer-to-peer system.

Problem

The problem this paper solves is how to design a scalable protocol for fast lookup in a dynamic peer-to-peer system.

Contribution

Since nodes will join and leave the peer-to-peer system dynamically, authors choose consistent hash to do lookup. There are two basic ways to finish designing this lookup protocol based on consistent hash: one is that each node are aware of all other nodes; the second is that each node is only aware of his successor. The defects of the first method is that each node will have to contain too much information, and it is not scalable. The defects of the second methods is that it may need a lot of jump to get to the target node.

Authors make a trade-off between the number of jump and information held by each node. There is a finger table in each node. The ith entry in the table at node n contains the identity of the first node that success n by at least 2**(i-1). The first few entries of finger table is used to make small jump and find the target precisely, and last entries of finger table is used to make large jump and reduce the number of jumps.

Flaw
authors make assumption that the communication time between different nodes is almost the same, in the lookup process, authors only try to reduce to jump number. But if the communication time is varies dramatically, the next jump chosen by current protocol may cause more time to get to the target node. I think CFS has a improved algorithm for this lookup process.

Applicability:

1. Authors of this paper successfully abstract the workload feature of P2P system. The fundamental problem of peer-to-peer system is to efficiently locate the node that stores a particular data item. The chord protocol only supports one map-key-node operation. I feel chord is a kind of finding key problems and solving key problems.

Summary:
This paper proposed the Chord protocol, which is used to locate the node that stores a particular data item in a distributed system. Chord improves the scalability of consistent hashing and avoids the requirement that every node know about every other node. A chord nodes only maintains information about O(log N) other nodes and resolves the hash function by communicating with a few other nodes.

Problem:
The traditional way of locating the node that stores a particular data item is not scalable because it requires that every node to be aware of every other node in the system. However, if you maintain only the successors, the loop up will be inefficient. Chord is trying to solve this dilemma and be efficient while maintaining small amount of states.

Contributions:
1. Chord proposed an additional data structure (the figure table) to speed look-ups, so that lookup is approaching the right node in O(log N) hops. The figure table doesn’t have to be 100% correct, and the successor list is responsible to ensure correctness (inefficiently). This idea of maintaining two fold-data structure to achieve both efficiency and correctness is neat.
2. Both the size of figure table and successor list is modest O(log N) and Chord tackles the scalability issue by having both O(log N) states and O(log N) routing.
3. A stabilization protocol is also proposed so that the successor list is guaranteed to be uptodate, and it deals with nodes frequently joins and leaves.

Flaws:
1. The network topology and latency is not taken into account when doing routing, which could degrade performance.
2. The chord protocol is vulnerable to malicious node, which should be considered as norm rather than exception in a peer-to-peer environment where nodes join volunteerly.

Applicability:
Since Chord provides an efficient and scalable scheme to route request to the right node in a distributed system, which could potentially be used in many applications, like distributed key-value store, distributed hash-table or cooperative mirroring.

Chord protocol
Summary

This paper describes the distributed look up protocol –Chord based on a variant of consistent hashing which achieves scalability, flexibility and availability. It explains how the dynamic environment and failures are handled in the peer to peer environment elegantly.

Problem being solved

All peer to peer applications face the problem of efficiently locate the node that contains a particular data item. In a peer to peer system nodes can leave and join the system quite often. The primary goal of chord would be to answer the queries even if the system is continuously changing and handle the scale of systems gracefully.

Contributions of the paper

Chord protocol is a variant of consistent hashing technique and stores information about log N nodes(N is the total number of nodes in the system) is sufficient to route requests properly. The finger table is the data structure that stores the successors of the node in powers of 2 to enable a faster lookup. The paper theoretically justifies that with high probability, the number of nodes that must be contacted to find a successor in an N-node network is O(log N). Also, the dynamic addition and removal of nodes from the system is managed by maintaining a predecessor pointer. Again it proves that any node joining or leaving a n-node chord network will use O(log^2 N) messages to establish the routing. The paper also demonstrates a stabilization protocol to keep nodes successor pointers upto date which guide in keeping the finger table entries correct. It also uses a successor list to tackle failures of nodes.

Concerns

The main concern is about the relationship between the identifier and the physical location. The protocol does not consider the physical location of nodes. Routing based on hash value and not by locality can lead to unnecessary delay. There could be some caching on the routes to speed up the lookup.

Relevance to Systems

The CFS Peer-to-peer read only file system uses the chord protocol to look up the nodes. Also the paper enlists some relevant examples like cooperative mirroring, time shared storage and distributed indexes. The chord protocol indeed plays an important part in the efficient functioning of P2P systems .

Summary:
Stoica et al present Chord, a decentralized protocol for key look-up in a peer-to-peer system. The authors introduces Chord model as a potential underlying framework in peer-to-peer system which can be used by other applications such as distributed file-sharing applications. The paper proofs on its efficient behavior under conditions, like the concurrent node failures.

Problem:
The fundamental problem that Chord tries to address is to come up with an efficient distributed lookup service (given a particular data item, locate the node that stores it) for p2p applications

Contributions:
In my opinion Chord is a proof that centralized or hierarchical control of a distributed system is not necessary to maintain efficient lookups.(Actually this could be said for almost all of the other P2P papers of the Chord era like Pastry, Tapestry and CAN but Chord probably came first.)

At a high level, Chord provides an efficient distributed lookup service,and uses a logarithmic-sized routing table to route object queries. I guess, the focus is on providing hashtable-like functionality of resolving key-value pairs.For a namespace defined as a sequence of m bits,a node keeps at most m pointers to nodes which succeed it in the namespace by pow(2,1), pow(2,2),and so on (upto pow(2,m-1)).The ith entry in node N’s routing table contains the first node that succeeds N by at least pow(2,i-1) in the namespace. Each key is stored on the first node whose identifier is equal to or immediately follows it in the namespace. The way they do it, allows lookups in O(log N)

Flaws:
To me, one of the biggest flaws in Chord is it being locality unaware.There seems to be no natural correlation between overlay namespace distance and network distance in the underlying network,which could lead to extremely long physical routes for every close logical hop.

Also its stabilization protocol is not efficient. I went through some of the papers on the Chord webpage. One tech report defines weak and strong notions of stability. Each stabilization round at a peer involves a constant number of messages and Strong stability takes O(N square) stabilization rounds.

It seems Chord cannot handle partition failures. (when all r successors of any node fail simultaneously, the system will become partitioned and will be unable to recover)

P2P systems thrive on anonymity. Chord neither protects the identity of the publisher nor the reader of the data.

Chord is also not secure against malicious nodes trying to interfere with routing (something that the authors admit as well)

Application:
I am not sure if Chord in its current form, as described in the paper could be used for any real P2P systems. However, concepts in Chord have formed the basis for many DHTs. DHash and CFS are written on top of Chord btw. Authors have also mentioned some other applications of Chord like Distributed Indexes (like in Search engines) and code breaking (combinatorial search).

Aside:
Can we replace DNS with Chord or a Chord variant?

Summary:
Stoica et al present Chord, a decentralized protocol for key look-up in a peer-to-peer system. The authors introduces Chord model as a potential underlying framework in peer-to-peer system which can be used by other applications such as distributed file-sharing applications. The paper proofs on its efficient behavior under conditions, like the concurrent node failures.

Problem:
The fundamental problem that Chord tries to address is to come up with an efficient distributed lookup service (given a particular data item, locate the node that stores it) for p2p applications

Contributions:
In my opinion Chord is a proof that centralized or hierarchical control of a distributed system is not necessary to maintain efficient lookups.(Actually this could be said for almost all of the other P2P papers of the Chord era like Pastry, Tapestry and CAN but Chord probably came first.)

At a high level, Chord provides an efficient distributed lookup service,and uses a logarithmic-sized routing table to route object queries. I guess, the focus is on providing hashtable-like functionality of resolving key-value pairs.For a namespace defined as a sequence of m bits,a node keeps at most m pointers to nodes which succeed it in the namespace by pow(2,1), pow(2,2),and so on (upto pow(2,m-1)).The ith entry in node N’s routing table contains the first node that succeeds N by at least pow(2,i-1) in the namespace. Each key is stored on the first node whose identifier is equal to or immediately follows it in the namespace. The way they do it, allows lookups in O(log N)

Flaws:
To me, one of the biggest flaws in Chord is it being locality unaware.There seems to be no natural correlation between overlay namespace distance and network distance in the underlying network,which could lead to extremely long physical routes for every close logical hop.

Also its stabilization protocol is not efficient. I went through some of the papers on the Chord webpage. One tech report defines weak and strong notions of stability. Each stabilization round at a peer involves a constant number of messages and Strong stability takes O(N square) stabilization rounds.

It seems Chord cannot handle partition failures. (when all r successors of any node fail simultaneously, the system will become partitioned and will be unable to recover)

P2P systems thrive on anonymity. Chord neither protects the identity of the publisher nor the reader of the data.

Chord is also not secure against malicious nodes trying to interfere with routing (something that the authors admit as well)

Application:
I am not sure if Chord in its current form, as described in the paper could be used for any real P2P systems. However, concepts in Chord have formed the basis for many DHTs. DHash and CFS are written on top of Chord btw. Authors have also mentioned some other applications of Chord like Distributed Indexes (like in Search engines) and code breaking (combinatorial search).

Aside:
Can we replace DNS with Chord or a Chord variant?

Summary
Each peer-to-peer system has 2 important components. First is how to find where an item is stored, and second is how to manage membership changes in the system efficiently and robustly. This paper focuses on the first issue and then designs their approach to membership changes to be consistent with their proposed solution to the key finding issue. The main design decision that they have made is to use consistent hashing for key lookup. The main result is that they get a bound on the number of look ups that is necessary to find a key.

Problem Statement
The problem at hand is to design a scalable peer-to-peer lookup service. The issue is that peer-to-peer systems tend to be not scalable because of the overhead of key lookup and detecting membership changes. A lot of this overhead is because of extensive communication that needs to be done between the peers for supporting these features.

Contributions

• Use of consistent hashing and arriving to a guarantee for number of steps that is needed to perform a lookup.
  
• Limiting the amount of information that is required to be stored at each node in order for routing to be done correctly.
  
• Handling different cases of membership changes and at the same time keeping the invariants of the system design.
  

Critique
Relying on only the hash of the keys to find the serving node does not seem a very good idea to me. The main advantage of hashing is that it spreads your data uniformly to your nodes. However, sometimes this randomness is not desirable. For example, there might be a set of keys that are frequently accessed together, or for some other reason is beneficial to store them together. This is not easily possible in this scheme.

Completely ruling out using hierarchy also seems not very reasonable. First, without levels of hierarchy, the peer-to-peer system might get so large that even a log(N) lookup mechanism might seems unreasonable. Second, it would not be possible to connect together different such peer-to-peer systems. Thus, hierarchy might be useful to connect different Chord rings together. This is especially true if we are having the security concerns that are mentioned in the Future Work section and each ring is managed by a different organization or section of the organization.

It is not totally clear to me on what kind of systems we would be able build with this mechanism. Many peer-to-peer systems have personal users that go on an off frequently. In this case, how could we force the users to store the data or move the data to other nodes?

Application
As the title suggests, this approach can be used in peer-to-peer systems to improve scalability. Some peer-to-peer systems such as Gnutella are not very scalable in the way they find the data items as a lot of communication between the nodes is needed. However, this approach introduces some level of determinism into the system which can significantly improve the lookup time.