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

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/02/05 07:51:44

Modified files:
        Documentation/misc/hemppah-progradu: progradu.bib 
                                             research_problems 

Log message:
        More notes

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.64&tr2=1.65&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.42&tr2=1.43&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.64 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.65
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.64   Wed Feb  5 
07:32:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Wed Feb  5 
07:51:44 2003
@@ -880,7 +880,7 @@
        
 }
 
-%BitTorrent - tool for downloading data from multpile hosts
+%BitTorrent - tool 
 @misc{bittorrenturl,
        key = {BitTorrent},
        title = {BitTorrent},
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.42 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.43
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.42      Wed Feb 
 5 07:32:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Wed Feb  5 
07:51:44 2003
@@ -1,7 +1,10 @@
-
+To be included in text:
 We (footonote)
 footnote:use of the plural is customary even if research paper is authored 
solely
 
+Stretch is the ratio between the distance traveled by a query to an specific 
object
+and the minimal distance from the query origin to the object
+
 1. Approaches
 
 -there are five approaches when performing searches in p2p networks.
@@ -43,6 +46,8 @@
 -Example systems: Chord \cite{stoica01chord}, CAN \cite{ratnasamy01can}, 
Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry}, Tapestry 
\cite{zhao01tapestry}, Viceroy \cite{malkhi02viceroy}, Symphony 
\cite{gurmeet03symphony}, SkipNet \cite{harvey03skipnet2}, Skip Graph 
\cite{AspnesS2003}
                Plaxton \cite{plaxton97accessingnearby}, Kelips 
\cite{gupta03kelips}, Overlapping Distance Halving DHT \cite{naor03simpledht}
 -Example applications: CFS \cite{dabek01widearea}, PAST 
\cite{rowstron01storage}, Oceanstore \cite{kubiatowicz00oceanstore}
+-data distribution approaches (like in Squirrel \cite{iyer02squirrel}): home 
node approach and directory approach
+-CFS splits files into blocks (<50Kb), PAST distributed whole files
 
 *Update*
 -Viceroy system achieves O(log n) hops with only O(1) neighbors
@@ -164,7 +169,7 @@
 Kademlia:              O(log n)*       O(log n)        O(log n)                
2(log n)
 Viceroy:               O(log n)        O(1)            O(log n)                
11
 SWAN 1):               O(1)            O(1)            O(log^2 n)              
r(2b+2s+2l) (r=# of resurces provided, b=boot, s=short, l=long), typical link 
conf: 2*(6+7+8)=36 
-Flooding:              O(1)            O(1)            O(n)**                  
typical conf: 5, depends on implementation --> 2*5=10 total             
+Gnutellas:             O(1)            O(1)            O(n)**                  
typical conf: 5, depends on implementation --> 2*5=10 total             
 Social:                        O(1)***         O(1)***         O(n)***         
        can be 1-10000 connections (aka social connections, connections are 
permament)
 Skip graphs 1):        O(log n)        O(log n)        O(log n)                
4r(log n) + (log n) (r=# of resurces provided)
 SkipNet:               O(log n)        O(log n)        O(log n)                
2(log n)
@@ -173,6 +178,7 @@
 Plaxton et al 3):      not supported   O(log n)        O(log n)                
2(log n)
 PeerNet 4):            O(log n)        O(log n)        O(log n)                
O(log n)
 Kelips:                        *****           O(sqrt(n))      O(1)            
        n/sqrt(n) + c*(sqrt(n)-1) + 'Total number of files'/sqrt(n)
+Freenet:               O(1)            O(1)            O(n)                    
??
 
 * = In Kademlia, there is no action required when nodes leaves the system
 
@@ -183,6 +189,7 @@
 **** = Can be also O(1). Additional space of 'space^2' can be used as a 
lookahed list for better performance
 
 ***** = constant background overhead is: O(2(sqrt(n)*(log^2 n)) + (sqrt(n) + 
(log^3 n))) (which includes convergence times for insertion/deletion of node)
+
 
 1) = In these approaches, node is treated as 'named resource'; in this 
approach, *resources* self-organise (opposite to DHTs).
 E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k 
resources. SWAN requires O(1) space..