[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      02/12/10 06:48:35

Modified files:
        Documentation/misc/hemppah-progradu: masterthesis.tex 
                                             progradu.bib 

Log message:
        Review of existing DHTs

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.18&tr2=1.19&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.26&tr2=1.27&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.18 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.19
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.18       Thu Dec 
 5 05:50:40 2002
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Dec 10 
06:48:35 2002
@@ -165,12 +165,12 @@
 
 
 
-Anonymity and Autonomy
-Self-organization
-Cost Of ownership
-ad-hoc connectivity
-accountability
-reputation
+Anonymity and Autonomy\
+Self-organization\
+Cost Of ownership\
+ad-hoc connectivity\
+accountability\
+reputation\
 
 \subsection{Adaptations of Peer-to-Peer}
 
@@ -206,13 +206,67 @@
 
 \chapter{Summary of existing Peer-to-Peer file sharing systems}
 
+In this section, we review briefly existing algorithms used in existing 
Peer-to-Peer systems.
+
+\section{Distributed Hash Tables}
+
+In DHT approach, each value is associated with a key 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. 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 
+assumes a proportional static node population. However, algorithm provides 
very efficient routing for search 
+lookups. In Plaxton's approach, the routing works as follows: if a node number 
e.g. 88768 received a lookup with key 
+88797, which matches the first three digits, then the routing algorithm 
forwards the query to a node which matches 
+the first four digits. To accomplish this, a each node forwards a packet to a 
neighbor whose label matches (from left 
+to right) incrementally the destination label in one more digit than its own 
label does. For a system with $n$ nodes, 
+Plaxton's algorithm routes in $O(log n)$ hops and requires a routing table 
size of $O(log n)$. 
+  
+
+\subsection{Tapestry}
+Tapestry \cite{zhao01tapestry} is a adaption of Plaxton's algorithm 
\cite{plaxton97accessingnearby}. Tapestry 
+routes queries with path lengths of $O(log n)$, and each node, for a systems 
with $n$ nodes, maintains routing table 
+size of $O(log n)$.
+
+\subsection{Pastry}
+In Pastry \cite{rowston01pastry}, the key space is considered as a virtual 
circle. Each node is responsible for keys 
+which are closest numerically. The neighbors consist of leaf set, which is the 
set of $|L|$ closest nodes. In addition, 
+Pastry has another set of neighbors randomly spread out in the key space for 
more efficient routing. As in Plaxton approach, 
+Pastry also forwards the query to the neighbor which have the longest shared 
prefix of the key. Pastry routes within 
+the pathlength of $O(log n)$ and each node has $O(log n)$ neighbors.
+
+\subsection{CAN}
+In the CAN model \cite{ratnasamy01can}, nodes are mapped into a virtual 
$d$-dimensional coordinate key space. Each node 
+is associated with a hypercubal blocks of this keyspace and every block keeps 
information on its immediate hypercubal 
+neighbors. In CAN, nodes have $O(d)$ neighbors and expected pathlengths are 
$O(dn^\frac{1}{d})$. Setting 
+$d = log_2(n)/2$, CAN provides similar scalability as Plaxton approach.
+
+\subsection{Chord}
+Chord \cite{stoica01chord} uses virtual circle as the key space. As Pastry, 
Chord also threats node's neighbors as leaf sets. 
+However, in Chord, there are two sets of neighbors: each node has a successor 
list of k nodes which immediately follows the node 
+in the key space. For better efficiency, each node has additional finger list 
of $O(log n)$ nodes placed around the key space.
+In a $n$ node network, each node maintains information about $O(log n)$ 
neighbors, and a lookup is performed within $O(log n)$ 
+hops. Additionally in Chord, a join or leave requires $O(log^2 n)$ messages.
+ 
+
+\subsection{Kademlia}
+
+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 
+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)$.
+
+
+
 \section{Gnutella}
-\section{Plaxton}
 \section{OceanStore}
-\section{Tapestry}
-\section{Pastry}
-\section{Chord}
-\section{CAN}
 \section{GISP}
 \section{Coral}
 \section{Yappers}
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.26 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.27
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.26   Thu Dec  5 
05:50:40 2002
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Tue Dec 10 
06:48:35 2002
@@ -1179,3 +1179,18 @@
        booktitle = {In Proc. Systemics, Cybernetics and Informatics (SCI)} 
(2002)},
        year = {2002}
 }
+
+%DIET system (small world network)
address@hidden,
+       author = {Cefn Hoile and Fang Wang and Erwin Bonsma and Paul Marrow},
+       title = {Core specification and experiments in DIET: a decentralised 
ecosystem-inspired mobile agent system},
+       booktitle = {Proceedings of the first international joint conference on 
Autonomous agents and multiagent systems},
+       year = {2002},
+       isbn = {1-58113-480-0},
+       pages = {623--630},
+       location = {Bologna, Italy},
+       doi = {http://doi.acm.org/10.1145/544862.544890},
+       publisher = {ACM Press},
+}
+
+