[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd... |
Date: |
Wed, 05 Feb 2003 07:51:45 -0500 |
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..
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/05
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/06
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/06
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/07
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/14
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/17
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/02/19