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

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/02/19 05:04:12

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

Log message:
        More refs;table updates

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.46&tr2=1.47&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.72&tr2=1.73&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.46 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.47
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.46       Tue Feb 
18 09:14:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Wed Feb 19 
05:04:10 2003
@@ -798,14 +798,6 @@
 
 \endfoot
 
-\parbox{37pt}{Chord} &
-\parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O(\log{n}$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{2$(\log{n})$} &
-\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
-\\ \hline
-
 \parbox{37pt}{CAN} &
 \parbox{37pt}{$O$($d$)} &
 \parbox{37pt}{$O$($d$)} &
@@ -814,46 +806,24 @@
 \parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner, where $d$ is the 
dimension of virtual key space}
 \\ \hline
 
-\parbox{37pt}{Pastry} &
-\parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
-\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
-\\ \hline
-
-\parbox{37pt}{Tapestry} &
+\parbox{37pt}{Chord} &
 \parbox{37pt}{$O(\log^2{n})$} &
+\parbox{37pt}{$O(\log{n}$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
+\parbox{85pt}{2$(\log{n})$} &
 \parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
 \\ \hline
 
-\parbox{37pt}{Kademlia} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$2(\log{n})$} &
-\parbox{85pt}{There is no action required when nodes leaves the system}
-\\ \hline
 
-\parbox{37pt}{Viceroy} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{37pt}{$O(1)$} &
-\parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{11} &
-\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
-\\ \hline
-
-\parbox{37pt}{SWAN} &
+\parbox{37pt}{Freenet} &
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(1)$} &
-\parbox{37pt}{$O(\log^2{n})$} &
-\parbox{85pt}{$r(2b+2s+2l)$ (where r=number of resources provided, b=boot 
connections, s=short range connections, l=long range connections), typical 
connection configuration: 2*(6+7+8)=36} &
-\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
+\parbox{37pt}{$O(n)$} &
+\parbox{85pt}{??} &
+\parbox{85pt}{}
 \\ \hline
 
+
 \parbox{37pt}{Gnutella} &
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(1)$} &
@@ -862,44 +832,56 @@
 \parbox{85pt}{Number of messages can grow as fast as $O(n^{2})$}
 \\ \hline
 
-\parbox{37pt}{Social} &
-\parbox{37pt}{$O(1)$} &
-\parbox{37pt}{$O(1)$} &
-\parbox{37pt}{$O(n)$} &
-\parbox{85pt}{Can be 1-10000 connections (aka social connections, connections 
are permament)} &
-\parbox{85pt}{Connection number depends on node's memory/network capabilities}
-\\ \hline
 
-\parbox{37pt}{Skip Graphs} &
+\parbox{37pt}{Kademlia} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$4r(\log{n}) + (\log{n})$, where r=number of resources 
provided)} &
-\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{There is no action required when nodes leaves the system}
 \\ \hline
 
-\parbox{37pt}{SkipNet} &
+
+\parbox{37pt}{Kelips} &
+\parbox{37pt}{$O(2(\sqrt{n}*(log^2{n})) + (\sqrt{n} + (log^3{n})))$} &
+\parbox{37pt}{$O$($\sqrt{n}$)} &
+\parbox{37pt}{$O(1)$} &
+\parbox{85pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$, where n is the number of nodes and c the number of 
contacts/foreign affinity group} &
+\parbox{85pt}{Insert/delete overhead is constant and performed background, 
System's performance may decrease if nodes are not homogeneous and nodes join 
and leave the system in a dynamic manner}
+\\ \hline
+
+\parbox{37pt}{Koorde} &
+\parbox{37pt}{$O(\log^2{n})$} &
+\parbox{37pt}{$O(1)$ or $O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$ or $O(\frac{\log{n}}{\log{}\log{n}})$} &
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{Based on Chord protocol, uses de Bruijn graphs for better 
efficiency/fault-tolerance}
+\\ \hline
+
+\parbox{37pt}{ODHDHT} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{85pt}{$2(\log{n})$} &
-\parbox{85pt}{Partially supports underlying network's locality properties} 
+\parbox{85pt}{There are two lookup algorithms. The other is $O(\log{n})$, 
which is robus under random deletion. The second is $O(\log^2{n})$, which is 
also robust under spam generating model}
 \\ \hline
-
-\parbox{37pt}{Symphony} &
+ 
+ 
+\parbox{37pt}{Pastry} &
 \parbox{37pt}{$O(\log^2{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$2k+2+f$, where k = long range connections, 2 = node's 
neighbors, f = fault-tolerance connections)} &
-\parbox{85pt}{Space can be also $O(1)$. Additional space of $space^2$ can be 
used as a lookahead list for better performance}
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
+\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner, based on Plaxton's 
algorithm}
 \\ \hline
 
-\parbox{37pt}{ODHDHT} &
+
+\parbox{37pt}{PeerNet} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$2(\log{n})$} &
-\parbox{85pt}{There are two lookup algorithms. The other is $O(\log{n})$, 
which is robus under random deletion. The second is $O(\log^2{n})$, which is 
also robust under spam generating model}
+\parbox{85pt}{$O(\log{n})$} &
+\parbox{85pt}{Operates at network layer}
 \\ \hline
 
 \parbox{37pt}{Plaxton} &
@@ -910,29 +892,62 @@
 \parbox{85pt}{Plaxton's algortihm is designed to operate in static environment 
(e.g., web cache)}
 \\ \hline
 
-\parbox{37pt}{PeerNet} &
+\parbox{37pt}{Skip Graphs} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$O(\log{n})$} &
-\parbox{85pt}{Operates at network layer}
+\parbox{85pt}{$4r(\log{n}) + (\log{n})$, where r=number of resources 
provided)} &
+\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
 \\ \hline
 
-\parbox{37pt}{Kelips} &
-\parbox{37pt}{$O(2(\sqrt{n}*(log^2{n})) + (\sqrt{n} + (log^3{n})))$} &
-\parbox{37pt}{$O$($\sqrt{n}$)} &
-\parbox{37pt}{$O$(1)} &
-\parbox{85pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$, where n is the number of nodes and c the number of 
contacts/foreign affinity group} &
-\parbox{85pt}{Insert/delete overhead is constant and performed background, 
System's performance may decrease if nodes are not homogeneous and nodes join 
and leave the system in a dynamic manner}
+\parbox{37pt}{SkipNet} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{Partially supports underlying network's locality properties} 
 \\ \hline
 
-\parbox{37pt}{Freenet} &
+\parbox{37pt}{Social} &
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(n)$} &
-\parbox{85pt}{??} &
-\parbox{85pt}{}
-\\ \hline 
+\parbox{85pt}{Can be 1-10000 connections (aka social connections, connections 
are permament)} &
+\parbox{85pt}{Connection number depends on node's memory/network capabilities}
+\\ \hline
+
+\parbox{37pt}{Symphony} &
+\parbox{37pt}{$O(\log^2{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2k+2+f$, where k = long range connections, 2 = node's 
neighbors, f = fault-tolerance connections)} &
+\parbox{85pt}{Space can be also $O(1)$. Additional space of $space^2$ can be 
used as a lookahead list for better performance, not necessarily fault-tolerant 
because of constant degree of neighbors}
+\\ \hline
+
+\parbox{37pt}{SWAN} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(\log^2{n})$} &
+\parbox{85pt}{$r(2b+2s+2l)$ (where r=number of resources provided, b=boot 
connections, s=short range connections, l=long range connections), typical 
connection configuration: 2*(6+7+8)=36} &
+\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
+\\ \hline
+
+
+\parbox{37pt}{Tapestry} &
+\parbox{37pt}{$O(\log^2{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
+\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner, based on Plaxton's 
algorithm}
+\\ \hline
+
+\parbox{37pt}{Viceroy} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{11} &
+\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner, not necessarily 
fault-tolerant because of constant degree of neighbors}
+\\ \hline
 
 
 \end{longtable}
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.72 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.73
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.72   Tue Feb 18 
09:14:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Wed Feb 19 
05:04:11 2003
@@ -1905,4 +1905,25 @@
        pages = {758--764},
        year = {1946}
 }
+
  
address@hidden:om_p-meng,
+       title = {A Keyword Set Search System for Peer-to-Peer Networks},
+       author = {Omprakash D Gnawali},
+       school = {Massachusetts Institute of Technology},
+       year = {2002},
+       month = {June},
+}
+
address@hidden,
+        author = {Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert 
Morris, Ion Stoica},
+        title = {Looking up data in P2P systems},
+        journal = {Communications of the ACM},
+        volume = {46},
+        number = {2},
+        year = {2003},  
+        pages = {43--48},
+        url = {http://project-iris.net/papers/cacm-paper.pdf},
+        publisher = {ACM Press},
+}
+