[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/01/30 07:01:17

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

Log message:
        Misc notes and more refs

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.58&tr2=1.59&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.37&tr2=1.38&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.58 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.59
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.58   Wed Jan 29 
07:45:31 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Thu Jan 30 
07:01:17 2003
@@ -1334,7 +1334,7 @@
 
 @inProceedings{saia02dynamicfaultcontentnetwork,
        title = "Dynamically Fault-Tolerant Content Addressable Networks",
-       author = "Jared Saia, Amos Fiat, Steve Gribble, Anna Karlin, Stefan 
Saroiu",
+       author = "Jared Saia, Amos Fiat, Steven Gribble, Anna Karlin, Stefan 
Saroiu",
        booktitle = {The 1st International Workshop on Peer-to-Peer Systems 
(IPTPS'02)},
        month = {March},
        year = {2002},
@@ -1711,4 +1711,11 @@
        url = 
{http://www.cs.cornell.edu/info/projects/spinglass/public_pdfs/Kelips.pdf}
 }
 
-
address@hidden,
+       author = {T.S. Eugene Ng, Hui Zhang},
+       title = {Predicting Internet network distance with coordiantes-based 
approaches},
+       booktitle = {The 21st Annual Joint Conference of the IEEE  Computer  
and Communications Societies (INFOCOM '02)},
+       location = {New York, USA},
+       year = {2001},
+       url = {http://www.ieee-infocom.org/2002/papers/785.pdf}
+}
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.37 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.38
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.37      Tue Jan 
28 08:17:24 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Thu Jan 30 
07:01:17 2003
@@ -153,19 +153,23 @@
 
 This summary table is far from complete (and from total truth)
 
-Protocol:      Insert/Delete   Space           Search          # of network 
connections
-Chord:                 O(log^2 n)      O(log n)        O(log n)        2(log n)
-CAN:           O(d)            O(d)            O(dn^(1/d))     2d
-Pastry:        O(log^2 n)      O(log n)        O(log n)        (2^b - 1)(log 
n)/b 
-Tapestry:      O(log^2 n)      O(log n)        O(log n)        (2^b - 1)(log 
n)/b 
-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             
-Social:                O(1)***         O(1)***         N/A***          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)
-Symphony:      O(log^2 n)      O(log n)****    O(log n)        2k+2+f (k = 
long, 2 = node's neighbors, f = fault-tolerance links)
-Plaxton et al: not supported   O(log n)        O(log n)        2(log n)
+Protocol:              Insert/Delete   Space           Search                  
# of network connections
+Chord:                         O(log^2 n)      O(log n)        O(log n)        
        2(log n)
+CAN:                   O(d)            O(d)            O(dn^(1/d))             
2d
+Pastry:                O(log^2 n)      O(log n)        O(log n)                
(2^b - 1)(log n)/b 
+Tapestry:              O(log^2 n)      O(log n)        O(log n)                
(2^b - 1)(log n)/b 
+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             
+Social:                        O(1)***         O(1)***         N/A***          
        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)
+Symphony:              O(log^2 n)      O(log n)****    O(log n)                
2k+2+f (k = long, 2 = node's neighbors, f = fault-tolerance links)
+ODHDHT 2):             O(log n)        O(log n)        O(log n)/O(log^2 n)     
2(log n)
+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)
 
 * = In Kademlia, there is no action required when nodes leaves the system
 
@@ -175,8 +179,16 @@
 
 **** = 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.. 
+E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k 
resources. SWAN requires O(1) space..
+
+2) = There are two lookup algorithms. The other is log n, which is robus under 
random deletion. The second is (log^2 n), which is also robust under spam 
generating model
+
+3) = Plaxton's algortihm is designed to operate in static environment (web 
cache)
+
+4) = Operates at network layer (not application level)
 - - -
 
 > Btw, how well Alpine can scale (e.g. number of users) ? Do you have any 
 > "real-
@@ -814,6 +826,7 @@
 Solution: 
 -SkipNet is able to self-organise after a organization has been disconnected 
from the network
 -However, SkipNet uses Pastry as routing layer. Kademlia/Symphony would be 
better choice
+-network partitions: techniques for maintaining DHT structure in real and 
dynamic environment \cite{rowston03controlloingreliability}
 
 Tuomas' example scenario #3:
 'What will happen if a malicious node quantities large amounts of data in the 
system ?'
@@ -822,7 +835,7 @@
 1) centralized: Per node based quotas based on reliable identification of 
publishers (usually requires CAs to work correctly)
 2) decentralized: Per node based quotas based on the ip address of the node
 
-It seems to be that DHTs are unable to self-reorganise after a sudden 
partitioning, because
+It seems to be that DHTs are unable to self-reorganise rapidly after a sudden 
partitioning, because
 a) every node has a fixed space in identifier space
 b) system has a fixed identifier space, e.g. Pastry and Chord require a priori 
knowledge about the size of the system
 c) even if system is able self-reorganise, the key space is not uniformly 
distributed anymore -> all nodes have to leave/rejoin --> lot of traffic
@@ -833,12 +846,26 @@
 copying
 
 
-The question is: how well SWAN can self-organise, e.g. in the case of Tuomas' 
scanario #2 ?
+Network proximity: 
+-\cite{pias03lighthouse}, \cite{ng02predicting}
+
+Efficient searching:
+-result caching and view trees \cite{Bhattacharjee03resultcache} (insight: 
store and and retrieve prior results from view tree)
+-bloom filters \cite{362692}
+
+Better load balancing techiques:
+-Better and simple load balancing \cite{byers03dhtbalancing} (insight: "power 
of two choices" whereby an item is stored at the less loaded of two (or more) 
random alternatives)
+
+One question is: how well SWAN can self-organise, e.g. in the case of Tuomas' 
scanario #2 ?
 
 Half-life phenomenon \cite{libennowell01observations}
 Current decentralized, but structured \cite{chord, can, pastry, Tapestry etc.) 
ignores the fact 
 that a P2P system is never in 'ideal' state. P2P system is always evolving 
system.
 
+-techniques for maintaining DHT structure in real and dynamic environment 
\cite{rowston03controlloingreliability}
+-this is not problem any more for structured p2p overlay networks
+-results can be directly applied to other DHTs
+
 Half-life concept:
 'Let there be N live nodes at time t. The doubling from time t is the time 
that pass before
 N new additional nodes arrive into the system. The halving time from time t is 
the time
@@ -883,7 +910,9 @@
        -e.g. -there is a single point of routing failure in these approaches 
(h hops, little amount f of system are adversial) 
 -make searching/query model more flexible (keyword searching)
        -use keywords/range searches instead of exact keys
-       proposal for range searches: Scalable, Efficient Range Queries for Grid 
Information Services \cite{andrzejak02rangequeries}
+       -proposal for range searches: Scalable, Efficient Range Queries for 
Grid Information Services \cite{andrzejak02rangequeries}
+       -proposal for broadcast operation in DHT-based systems 
\cite{ansaryefficientbroadcast03} (insight: k-ary tree is a spanning tree, 
traverse spanning tree)
+       -proposal for complex queries in DHTs \cite{harren02complex} (insight: 
use SQL-like mechanisms)
 
 2) Decentralized, but unstructured
 -make routing more scalable: reach more nodes, create less traffic