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

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

Log message:
        More

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.182 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.183
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.182      Tue Mar 
25 04:19:25 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Mar 25 
04:29:56 2003
@@ -1870,12 +1870,10 @@
 severe problems with load balancing in a highly heterogeneous environment 
\cite{rao03loadbalancing}. The problem is caused by peers 
 which may not be able to store relatively large blocks, assigned randomly by 
the mapping function of the overlay. 
 
-In our method, each peer maintains the following data structures for local 
operations: a data structure for listing all 
-key-value pairs which peer maintains; a data structure for listing all 
key-value pairs in the 
-chronological order (the most recent block is topmost) which peer maintains. 
We use Storm blocks' identifiers
-as \emph{keys} of the overlay. Every key-value pair consists of either a hash 
of pointer random string 
-(pointer blocks), or a hash of block's content (scroll blocks) as a key. The 
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.
+In our method, each peer maintains the following local data structures for 
local operations: a data structure for listing all 
+key-value pairs which are assigned by the overlay; a data structure for 
listing all key-value pairs which are assigned by the overlay 
+in the chronological order (the most recent block is topmost). We use Storm 
blocks' identifiers and pointers
+as \emph{keys} of the overlay. 
 
 We assume that we have resolved the construction of the ''virtual file'' 
before locating any Storm blocks, i.e., 
 when assembling the ''virtual file'' we know all the Storm blocks, which are 
required to complete the ''virtual file''. 
@@ -1889,67 +1887,45 @@
 \item Data lookup with a given identifier of Storm scroll block.
 \begin{enumerate}
 \item Submit the data lookup using scroll block's identifier.
-\item Repeat until the pointer peer is found: each peer forwards the data 
lookup to a closer peer which hosts the given scroll block identifier.
+\item Each peer forwards the data lookup to a closer peer which hosts the 
given scroll block identifier in the overlay.
 \item The pointer peer returns value (e.g., the IP address of provider peer) 
to the query originator.
 \item The query originator requests the provider peer to return the scroll 
block.
 \end{enumerate}
 \end{itemize}
 
-Figure \ref{fig:storm_query_blockid} illustrates how Storm scroll block is 
located 
-in a tightly structured overlay using the DOLR abstraction, where the 
identifier of Storm scroll 
-block is given.
-
 
 \begin{itemize}
-\item Data lookup with a given pointer random string returning most recent 
scroll block.
+\item Data lookup with a given pointer returning most recent scroll block.
 \begin{enumerate}
-\item The query originator locally computes a hash over given pointer random 
string.
-\item Repeat until the pointer peer is found: each peer forwards the data 
lookup to a closer peer which hosts the given hash of pointer random string.
+\item The query originator locally computes a hash over given pointer.
+\item Each peer forwards the data lookup to a closer peer which hosts the 
given hash of pointer in the overlay.
 \item The pointer peer returns most recent pointer block's key-value pair 
(e.g., the IP address of provider peer) to the query originator, using pointer 
block's own indexing schemes. 
 \item The query originator requests the provider peer to return the scroll 
block.
 \end{enumerate}
 \end{itemize}
 
 \begin{itemize}
-\item Data lookup with a given pointer random string returning scroll block(s) 
for a given date or time range.
+\item Data lookup with a given pointer returning scroll block(s) for a given 
date or time range.
 \begin{enumerate}
-\item The query originator locally computes a hash over given pointer random 
string.
-\item Repeat until the pointer peer is found: each peer forwards the data 
lookup to a closer peer which hosts the given hash of pointer random string.
+\item The query originator locally computes a hash over given pointer.
+\item Each peer forwards the data lookup to a closer peer which hosts the 
given hash of pointer in the overlay.
 \item Pointer peer returns pointer block's key-value pair(s) (e.g., the IP 
address of provider peer) to the query originator, using pointer block's own 
indexing schemes. 
 \item The query originator requests the provider peer to return the scroll 
block.
 \end{enumerate}
 \end{itemize}
 
-Figure \ref{fig:storm_query_urn5} illustrates how Storm scroll block is 
located 
-in a tightly structured overlay using the DOLR abstraction, where the pointer 
random string is given.
 
 Each of these algorithms can locate Fenfire blocks in $O(\log{n})$ time at 
application level overlay:
 $O(\log{n})$ time for query routing to pointer peer (Kademlia 
\cite{maymounkov02kademlia}) and constant time for 
 locating hosting peer with a given reference link.
 
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=7cm]{storm_query_blockid.eps}
-\caption{Locating Storm block in Peer-to-Peer environment with a given block 
identifier.}
-\label{fig:storm_query_blockid}
-\end{figure}
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=7cm]{storm_query_urn5.eps}
-\caption{Locating Storm block in Peer-to-Peer environment with a given pointer 
random string.}
-\label{fig:storm_query_urn5}
-\end{figure}
-
-
 \subsection{Problems}
 
 Perhaps the most biggest issue in Peer-to-Peer systems is the non-maturity of
 security technologies. For instance, online entities cannot be identified 
 safely (e.g., the Sybil attack \cite{douceur02sybil}). For the Fenfire system, 
one
 security related problem occurs when a user wants to perform a global data 
lookup with a given
-pointer random string; how the user is able to verify the correctness
+pointer; how the user is able to verify the correctness
 of the search results, i.e.,  how she or he knows which one is the 
 correct Storm scroll block ? The Spam attack \cite{naor03simpledht} is a 
variation of previously
 mentioned problem; data lookup is performed by a user, but there is no reply