[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert... |
Date: |
Tue, 10 Dec 2002 07:32:28 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 02/12/10 07:32:28
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
progradu.bib
Log message:
DHT section updates
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.20&tr2=1.21&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.27&tr2=1.28&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.20
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.21
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.20 Tue Dec
10 06:54:48 2002
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Tue Dec 10
07:32:28 2002
@@ -210,17 +210,16 @@
\section{Distributed Hash Tables}
-In DHT approach, each value is associated with a key in an m-bit virtual
address space. The virtual
+In DHT approach, each value is associated with a unique key (e.g. SHA-1
\cite{fips-sha-1})in an m-bit virtual address space. The virtual
address space is partitioned into sections, which form adjoining regions of
this address space. In general,
either a single computer or multiple computers is assigned to each section of
the virtual address space. Each
computer is assigned one or more sections, and they maintains copies of those
key-value bindings whose key values
lie within its assigned cell. This means, in general, that computer that hosts
corresponding key-value pair,
-is not owned by the user that decided to provide the resource to the
community. Moreover, the allocation of the address
+is not owned by the user that decided to provide the resource to the netowork.
Moreover, the allocation of the address
space and the assigment of computers to sections is dynamic. Therefore,
everytime when a node joins or
leaves the network, the address space is reallocated.
-
\subsection{Plaxton Algorithm}
Plaxton \cite{plaxton97accessingnearby} developed the first routing algorithm,
which can be used with DHTs.
The algorithm is not designed to be used in dynamic distributed systems,
because Plaxton algorithm
@@ -263,11 +262,18 @@
Kademlia \cite{maymounkov02kademlia} is based on a XOR-based metric topology.
In this approach, every query (message) exchanged conveys
useful contact information. Furthermore, Kademlia uses this information to
send parallel query messages. XOR-metrics are used to calculate
distances between points in key space. XOR is symmetric, allowing nodes to
receive lookup queries from the same distribution of nodes
-contained in the key space. Routing table contains ''contact buckets'', which
allows to accommodate temporarily used nodes more
+contained in the key space. Routing table contains ``contact buckets'', which
allows to accommodate temporarily used nodes more
efficiently than other DHT approaches. For a system with $n$ nodes, Kademlia's
algorithm routes in $O(log n)$ hops and requires
a routing table size of $O(log n)$.
+\subsection{Coral}
+Coral [NOTYETPUBLISHED] is based on a new abstraction called distributed
sloppy hash table (DSHT) and is a layer on existing
+lookup systems, such as Chord, CAN, Kademlia, Pastry and Tapestry. In contrast
to original DHTs, Coral provides a lookup, which
+is based on name (instead of hash value). Furthermore, Coral aims to avoid
DHTs' hot spots and to find nearby data without querying
+distant nodes. DSHTs sacrifice the consistency of DHTs to support both
frequent fetches and frequent stores of the same hash table
+key. Moreover, the fundamental observation is that a node doesn't need to
know every replicated location of a resource---it only
+needs a single nearby copy.
\section{Gnutella}
\section{OceanStore}
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.27
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.28
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.27 Tue Dec 10
06:48:35 2002
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib Tue Dec 10
07:32:28 2002
@@ -1193,4 +1193,9 @@
publisher = {ACM Press},
}
-
+%SHA-1 secure hash standard
address@hidden(fips-sha-1,
+title = { FIPS PUB 180-1: Secure Hash Standard },
+organization = { NIST },
+year = { 1995 },
+)
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/05
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/11
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/11
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/12