[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/25 06:03:29

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

Log message:
        More algorithms

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.68 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.69
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.68       Tue Feb 
25 04:48:13 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Feb 25 
06:03:29 2003
@@ -1788,19 +1788,18 @@
 and urn-5 random string. 
 
 \subsection{Assumptions}
-We use tightly structured ovelay's DOLR method. Each peer hosts the data, 
-overlay maintains the \emph{pointers} of the data. Furthermore, each peer 
maintains 
+In our analysis, we use tightly structured ovelay's DOLR method. Each peer 
hosts the data, 
+overlay maintains only the \emph{pointers} to the data. Furthermore, each peer 
maintains 
 following data structures for local operations: one data structure for listing 
all 
-key/value-pairs; one data structure for scroll blocks; one data structure for
-pointer blocks. Key/value-pairs are as follows: 
-
-For scroll blocks
-
+key/value-pairs; one data structure for listing all key/value-pair in 
chronological order
+(the most recent block is topmost). Every key/value-pairs consists of a hash 
of urn-5 
+random string (pointer blocks) or a hash of block's content (scroll blocks) as 
a key. 
+Value is always a reference to a hosting peer (e.g. IP-address). Finally, we 
assume 
+that all local operations can be done in a constant time.
 
 \subsection{Algorithms}
 
 
-
 \begin{itemize}
 \item Data lookup with a given scroll block's identifier
 \begin{enumerate}
@@ -1811,6 +1810,10 @@
 \end{enumerate}
 \end{itemize}
 
+Figure \ref{fig:storm_query_blockid} illustrates how scroll block is located 
+in a tightly structured overlay using DOLR method, where scroll block's
+identifier is known.
+
 
 \begin{itemize}
 \item Data lookup with a given urn-5 random string returning most recent 
scroll block
@@ -1834,60 +1837,14 @@
 \end{enumerate}
 \end{itemize}
 
+Figure \ref{fig:storm_query_urn5} illustrates how scroll block is located 
+in a tightly structured overlay using DOLR method, where urn-5 is known.
 
-
-
-       Req. 1:
-       -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
-       which node hosts. The most recent block is topmost --> we don't have to 
check all blocks and their urn-5 associations to get the most recent
-       Req. 2:
-       -all urn-5 name mappings are stored as <key, value[ ]>, where the key 
is urn-5 name's hash and value is a record containing
-       block ID and timestamp of that block. So, when we store a block in our 
system first time, we have to create a new key-value: 
-       %<hash_of_urn_5_name, [block id, block timestamp]> and route this 
mapping to node which is "closest" to a hash value. Now when we want to find 
the most 
-       recent block associated with a specific urn-5 name, we do:
-       
+Each of these algortihms can locate a specific scroll block in 
$\Theta(\log{n})$ time;
+$\Theta(\log{n})$ time for query routing to pointer peer and constant time for 
+locating hosting peer with a given reference link.     
                
-               
-       In this approach, we don't have to perform additional searching and 
sorting of mappings. And of course, we know that for given urn-5, only one node
-       hosts *all* the block information ("block history") for the urn-5, 
since mappings are mapped to a single node, closest to urn-5 hash value.
-       Again, this should work fine under existing DHTs (and SWTs ?).
-       
-       Some simple analysis: 
-       -there are more key-value pairs in the system for additional urn-5 --> 
block associations
-       -however, I don't think this is an issue, since data's size is small
-       -efficiency: find node which hosts urn-5 names + find node which hosts 
blocks associated with urn-5 name: logn + logn = 2logn (logarithmical)
-       
--for FBS and others:
-       -there is no very efficient (simple) methods for finding urn-5 name 
associated with the most recent block
-       -one simple proposal is that when we visit to each node (first idea 
above), get only the most recent one and compare them (or greedy approach: 
dismiss currently 
-       most recent block as we visit to nodes, if newer block have been found)
-       
-       
-       Please notice: In this approach, DHT doesn't store the actual block, 
only the values for locating the data from the system
-
-       Req. 1:
-       -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
-       which node hosts. The most recent block is topmost --> we don't have to 
check all blocks and their urn-5 associations to get the most recent
-       Req. 2:
-       -all urn-5 name mappings are stored as <key, value[ ]>, where the key 
is urn-5 name's hash and value is a record containing
-       block ID and timestamp of that block. So, when we store a block in our 
system first time, we have to create a new key-value: 
-       %<hash_of_urn_5_name, [block id, block timestamp]> and route this 
mapping to node which is "closest" to a hash value. Now when we want to find 
the most 
-       recent block associated with a specific urn-5 name, we do:      
-       
-               1. locally compute a hash for given urn-5 string
-               2. route the query to a node which hosts the given hash of 
urn-5 ("closest" node)
-               %3. get the specific block(s) data (block ID) from the stack 
which matches to given date&time properties (we compare to block header data)
-               4. use IDs to get the specific blocks using normal DHT/SWN 
operation            
-       
-       Some simple analysis: 
-       -there are more key-value pairs in the system for additional urn-5 --> 
block associations
-       -however, I don't think this is an issue, since data's size is small
-       -efficiency: find node which hosts urn-5 names + find node which hosts 
blocks associated with urn-5 name: logn + logn = 2logn (logarithmical)
-       
--for FBS and others:
-       -there is no very efficient (simple) methods for finding urn-5 name 
associated with the most recent block
-       -one simple proposal is that when we be that we visit to each node 
(first idea above), get all blocks which matches to given properties
-      
+
 
 
 \begin{figure}
@@ -1905,6 +1862,13 @@
 \end{figure}
 
 \section{Open issues and future work}
+
+-identification
+-search engine & fake blocks
+-transclusions and filtering
+-xanadu links and filtering
+
+
 
 \cite{gribble01p2pdatabase}