A Scalable Content-Addressable Network
SIGCOMM 2001

Introduces the concept of using a distributed hash table, hashing
content on to a virtual space, and examines in simulation several
improvements to the basic algorithm.

Basic algorithm:
- each node stores a chunk (called a zone) of the entire hash table.
There are no virtual servers, etc.
- d-dimensional Cartesian coordinate space on a d-torus (in other
words, it wraps).
- in contrast to Chord, Pastry, and Plaxton, each node stores a
constant sized neighbor table of 2d neighbors and the average routing
path length is (d/4)(n^(1/d)) hops.  They note that CAN could easily
be changed to maintain log(n) state and then have log(n) hops, but
they have chosen not to have it this way for scalability.
- hops follow a greedy algorithm and failover to an expanding ring
search.
- a node joins by finding a spot at random in the id space, contacting
the node in charge of that spot, and then splitting it.  
- "to prevent repeated further fragmentation of the space, a
background zone-reassignment algorithm" is run.  Hmmm.

Improvements:
- note that the larger d is, the more state needs to be kept but fewer
hops need to be taken.
- instead of just having a single space, nodes can participate in
parallel "realities."  Thus, data can be stored on each reality for
reliability.  Additionally, a datum can be quickly accessed from the
nearest copy in any reality.
- they discuss using round-trip time as a metric instead of Cartesian
distance.
- they introduce the idea of having nodes share the same spot in the
space (they are called "peers") to increase redundancy and limit the
fragmentation of the space.
- data can be stored and then fetched using multiple hash functions.
- they start looking at giving nodes IDs according to topologically
here, but leave it for another paper (which was forthcoming).
- instead of just picking one spot to join in, nodes look at the
neighbors of their id and see if splitting their id spaces would make
more sense.

There is no presentation of CAN recovery algorithms.  That is in a TR.

They note that they looked at and turned down Plaxton's algorithm
because it required global knowledge and because it was geared toward
replicating web objects.

All evaluations take place using a simulated transit-stub network.

It is cool to see that they introduce so many of the improvements that
have been looked into in the few years since this paper was written.