[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc... |
Date: |
Tue, 17 Dec 2002 03:27:50 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 02/12/17 03:27:50
Modified files:
Documentation/misc/hemppah-progradu: research_problems
Log message:
Updates to summary table
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.3&tr2=1.4&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.3
gzz/Documentation/misc/hemppah-progradu/research_problems:1.4
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.3 Mon Dec
16 09:14:48 2002
+++ gzz/Documentation/misc/hemppah-progradu/research_problems Tue Dec 17
03:27:50 2002
@@ -21,7 +21,7 @@
-Of couse, there is the possibility to route in constant times, but it
requires that *each** node
maintains information about all the nodes in the network. Therefore ,
practically, this method
impossible
--Example systems: Chord, CAN, Kademlia, Pastry, Tapestry
+-Example systems: Chord, CAN, Kademlia, Pastry, Tapestry, Viceroy
*Update*
-Viceroy system achieves O(log n) hops with only O(1) neighbors
@@ -75,24 +75,24 @@
This summary table is far from complete (and from total truth)
Insert/Delete Space Search
-Chord: O(log^2 n) O(nlog n) O(log n)
-CAN: O(r) O(nr) O((r/4)n^(1/r)), where r is the
number of dimensions used in a virtual space
-Pastry: O(log^2 n) O(nlog n) O(log n)
-Tapestry: O(log^2 n) O(nlog n) O(log n)
-Kademlia: N/A O(log n) O(log n)
-Viceroy: N/A 7 O(log n)
-Small Worlds: N/A O(1) O(log^2 n)
+Chord: O(log^2 n) O(log n) O(log n)
+CAN: O(r) O(r) O(rn^(1/r)), where r is the
number of dimensions used in a virtual space
+Pastry: O(log^2 n) O(log n) O(log n)
+Tapestry: O(log^2 n) O(log n) O(log n)
+Kademlia: O(log n)* O(log n) O(log n)
+Viceroy: O(log n) O(1) O(log n)
+Small Worlds: O(1) O(1) O(log^2 n)
Flooding: N/A O(1) "high"
Hybrid: N/A N/A N/A
Social: N/A O(1) N/A
-*I will try fill in N/As as quickly as possible!*
+* = In Kademlia, there is no action required when nodes leaves the system
Insert/Delete:
Number of messages when a node joins or leaves the network.
Space:
-Total amount of space required in a system for routing tables
+Space required for a node's neighbors
Search:
Number of messages when an object lookup is performed
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/16
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/17
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/17
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/18
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/18
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/18
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/18
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/19
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/19
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc..., Hermanni Hyytiälä, 2002/12/19