[Gzz] Fwd: About Sloppy hashing and self-organizing clusters-article (fwd)

[hemppah]

FYI (For Your Information).

-Hermanni

----- Forwarded message from "Michael J. Freedman" <address@hidden> -----
    Date: Mon, 11 Nov 2002 10:50:58 -0500 (EST)
    From: "Michael J. Freedman" <address@hidden>
Reply-To: "Michael J. Freedman" <address@hidden>
 Subject: About Sloppy hashing and self-organizing clusters-article (fwd)
      To: address@hidden

Hi Hermanni,

It is indeed submitted to IPTPS 03.  I'll probably make the whole paper
public sometime in December if accepted.

For now, here's a short overview:

This paper presents Coral, a peer-to-peer content distribution system
we are building. Coral is based on a new abstraction we call a
\emph{distributed
sloppy hash table} (DSHT) and is built as a layer on existing node lookup
services~\cite{chord:ton,kademlia:iptps02,can:sigcomm01,pastry01,tapestry:tech}.
Coral lets nodes locate and download files from each other by name.  Web
caches can use it to fetch static data from nearby peers.  Users can
employ it directly to share directories of files.  Coral's two principal
goals are to avoid hot spots and to find nearby data without querying
distant nodes.

The DSHT abstraction is specifically suited to locating replicated
resources.  DSHTs sacrifice the consistency of DHTs to support both
frequent fetches and frequent stores of the same hash table key.  The
fundamental observation is that a node doesn't need to know every
replicated location of a resource---it only needs a single, valid,
nearby copy.  Thus, a sloppy insert is akin to an append in which a
replica pointer appended to a ``full'' node spills over to the
previous node in the lookup path.  A sloppy retrieve only returns some
randomized subset of the pointers stored under a given key.

In order to restrict queries to nearby machines, each Coral node is a
member of several DSHTs of increasing network \emph{diameter}.  We
refer to these DSHTs as \emph{clusters}.  The diameter of a cluster is
the maximum desired round-trip time between any two nodes it contains.
When data is cached somewhere in a Coral cluster, any member of the
cluster can locate a copy without querying machines farther away than
the cluster's diameter.  Since nodes have the same identifiers in all
clusters, even when data is not available in a low-diameter cluster,
the routing information returned by the lookup can be used to continue
the query in a larger-diameter cluster.

Coral's challenge is to organize and manage these clusters in a
decentralized manner.  As described in the next section, the DSHT
interface itself is well-suited to locate and
evaluate nearby clusters.



----- End forwarded message -----




-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/