[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/11 09:09:38

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

Log message:
        More into protocol table

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.33 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.34
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.33       Tue Feb 
11 08:26:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Feb 11 
09:09:38 2003
@@ -694,56 +694,153 @@
 
 
 
-\begin{longtable}{|l|l|l|l|l|}
+\begin{longtable}{|l|c|c|c|c|l|}
 \caption[Comparison of Broadicasting and Structured approaches]{Comparison of 
Broadicasting and Structured approaches} 
 \label{table_comparison_approach} \\
 
 \hline
 \multicolumn{1}{|c|}{\textbf{Protocol}} &
-\multicolumn{1}{|c|}{\textbf{Insert/Delete}} & 
+\multicolumn{1}{c|}{\textbf{Insert/Delete}} & 
 \multicolumn{1}{c|}{\textbf{Space}} & 
 \multicolumn{1}{c|}{\textbf{Search}} &
-\multicolumn{1}{c|}{\textbf{# of network connections}} &
+\multicolumn{1}{c|}{\textbf{\# of network connections}} &
 \multicolumn{1}{c|}{\textbf{Notes}}
+\\ \hline
 
-\parbox{50pt}{Chord}
-\parbox{50pt}{O(log\^2 n)}
-\parbox{50pt}{O(log n)}
-\parbox{50pt}{O(log n)}
-\parbox{50pt}{2(log n)}
+\parbox{50pt}{Chord} &
+\parbox{50pt}{$O$(log\^2 n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2(log n)} &
 \parbox{50pt}{}
+\\ \hline
 
-CAN
-
-Pastry
+\parbox{50pt}{CAN} &
+\parbox{50pt}{$O$(d)} &
+\parbox{50pt}{$O$(d)} &
+\parbox{50pt}{$O$(dn\^(1/d))} &
+\parbox{50pt}{2d} &
+\parbox{50pt}{}
+\\ \hline
 
-Tapestry
+\parbox{50pt}{Pastry} &
+\parbox{50pt}{$O$(log\^2 n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2\^b - 1)(log n)/b} &
+\parbox{50pt}{}
+\\ \hline
 
-Kademlia
+\parbox{50pt}{Tapestry} &
+\parbox{50pt}{$O$(log\^2 n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2\^b - 1)(log n)/b} &
+\parbox{50pt}{}
+\\ \hline
 
-Viceroy
+\parbox{50pt}{Kademlia} &
+\parbox{50pt}{$O$(log n)*} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2(log n)} &
+\parbox{50pt}{}
+\\ \hline
 
-SWAN
+\parbox{50pt}{Viceroy} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{11} &
+\parbox{50pt}{}
+\\ \hline
 
-Gnutellas
+\parbox{50pt}{SWAN} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(log\^2 n)} &
+\parbox{50pt}{r(2b+2s+2l) (r=\# of resurces provided, b=boot, s=short, 
l=long), typical link conf: 2*(6+7+8)=36} &
+\parbox{50pt}{}
+\\ \hline
 
-Social
+\parbox{50pt}{Gnutellas} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(n)} &
+\parbox{50pt}{typical conf: 5, depends on implementation --> 2*5=10 total} &
+\parbox{50pt}{}
+\\ \hline
 
-Skip Graphs
+\parbox{50pt}{Social} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(n)} &
+\parbox{50pt}{can be 1-10000 connections (aka social connections, connections 
are permament)} &
+\parbox{50pt}{}
+\\ \hline
 
-SkipNet
+\parbox{50pt}{Skip Graphs} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{4r(log n) + (log n) (r=\# of resurces provided)} &
+\parbox{50pt}{}
+\\ \hline
 
-Symphony
+\parbox{50pt}{SkipNet} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2(log n)} &
+\parbox{50pt}{} 
+\\ \hline
+
+\parbox{50pt}{Symphony} &
+\parbox{50pt}{$O$(log\^2 n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{2k+2+f (k = long, 2 = node's neighbors, f = fault-tolerance 
links)} &
+\parbox{50pt}{}
+\\ \hline
 
-ODHDHT
+\parbox{50pt}{ODHDHT} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)/O(log\^2 n)} &
+\parbox{50pt}{2(log n)} &
+\parbox{50pt}{}
+\\ \hline
 
-Plaxton et al
+\parbox{50pt}{Plaxton et al} &
+\parbox{50pt}{-} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{}
+\\ \hline
 
-Kelips
+\parbox{50pt}{PeerNet} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{$O$(log n)} &
+\parbox{50pt}{}
+\\ \hline
 
-Freenet
+\parbox{50pt}{Kelips} &
+\parbox{50pt}{} &
+\parbox{50pt}{$O$($\sqrt{n}$)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{'Total number of 
files'}{\sqrt{n}}$} &
+\parbox{50pt}{}
+\\ \hline
 
- 
+\parbox{50pt}{Freenet} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(1)} &
+\parbox{50pt}{$O$(n)} &
+\parbox{50pt}{??} &
+\parbox{50pt}{}
 \\ \hline