[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert... |
Date: |
Tue, 25 Feb 2003 06:03:29 -0500 |
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}
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., (continued)
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/21
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/02/26