[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/13 06:23:54

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

Log message:
        More

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.136 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.137
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.136      Thu Mar 
13 04:55:51 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Mar 13 
06:23:49 2003
@@ -363,7 +363,8 @@
 To store data into tightly structured overlay, each application-specific
 unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} uniformly (e.g., 
using consistent
 hashing \cite{258660}) by the overlay to an existing peer in the overlay. 
Thus, tightly 
-structured overlay assigns a subset of all possible keys to every 
participating peer. 
+structured overlay assigns a subset of all possible keys to every 
participating peer 
+\footnote{We say that a peer is \emph{responsible} for the keys which are 
assigned by the overlay.}.  
 Also, each peer in tightly structured overlay maintains a \emph{routing 
table}, which 
 consists of identifiers and IP addresses of other peers in the overlay. 
Entries of routing
 table are peer's neighbors in the overlay network. Figure 
\ref{fig:structured_hashing} illustrates the 
@@ -413,7 +414,7 @@
 for maintaining information about other peers in the system and 
 $O(\log{n})$ data lookup efficiency.
 
-Stoica et al. \cite{balakrishanarticle03lookupp2p} have listed 
+Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed 
 four requirements for tightly structured overlays, which have to be 
 addressed in order to perform efficient data lookups in tightly structured 
overlays. 
 First, mapping of keys to peers must be done in a load-balanced
@@ -534,16 +535,18 @@
 experimented in simulation environments. In real-life, measuring fault 
tolerance is much more 
 challenging task and requires more research to get reliable answers.
  
-There are significant differences between loosely structured and tightly 
structured approaches.
 The most important difference between approaches is performance and 
scalability properties. While 
 performance of loosely structured approach is not always even linear, 
generally tightly structured 
 approach can perform all internal operations in poly-logarithmic 
time\footnote{However, it is unknown 
-whether all proposed algorithms can preserve logarithmic properties in 
real-life applications or not.}. 
+whether all proposed algorithms can preserve logarithmic properties in 
real-life applications or not.}.
+Loosely structured systems scale to millions of peers, whereas tightly 
structured systems are able
+to cope with billions of concurrent peers.
 
 Another key point is the philosophy how overlay network is constructed and 
maintained. While loosely 
 structured approach gives much freedom to individual peers to join and leave 
the overlay network, tightly 
 structured approach has certain features, in which participating peers have no 
control at all 
-(such as mapping of data items). 
+(such as mapping of data items). With DHT abstraction of tightly structured 
approach, for instance, 
+peer has no power to decide where the data items are mapped in the overlay.
 
 To end user, biggest difference between these systems is how data lookups are 
performed. Loosely
 structured systems provide more richer and user friendly way of searching data 
as they
@@ -579,11 +582,6 @@
 \endfoot
 
 
-
-\parbox{90pt}{Construction of overlay} &
-\parbox{100pt}{Uncontrolled} &
-\parbox{100pt}{Controlled}  
-
 \\ \hline
 
 \parbox{90pt}{Queries} &
@@ -597,8 +595,8 @@
 \\ \hline
          
 \parbox{90pt}{Query traffic} &
-\parbox{100pt}{$O(n)/O(n^{2})$}  &
-\parbox{100pt}{$O(1)/O(\log{n})$} 
+\parbox{100pt}{$O(n), O(n^{2})$}  &
+\parbox{100pt}{$O(1), O(\log{n})$} 
 \\ \hline
 
 \parbox{90pt}{Guaranteed data lookup} &
@@ -606,12 +604,12 @@
 \parbox{100pt}{Yes} 
 \\ \hline
 
-\parbox{90pt}{Overlay's structure} &
-\parbox{100pt}{Uncontrolled and ad hoc}  &
+\parbox{90pt}{Construction and maintenance of overlay} &
+\parbox{100pt}{uncontrolled and ad hoc}  &
 \parbox{100pt}{Controlled and structured}
 \\ \hline
                  
-\parbox{90pt}{Max. number of peers} &
+\parbox{90pt}{Maximum number of peers} &
 \parbox{100pt}{Millions} &
 \parbox{100pt}{Billions} 
 \\ \hline
@@ -620,11 +618,6 @@
 \parbox{100pt}{Local} &
 \parbox{100pt}{Not local} 
 \\ \hline
-                 
-\parbox{90pt}{Support for heterogeneity} &
-\parbox{100pt}{Yes} &
-\parbox{100pt}{No} 
-\\ \hline
        
 \parbox{90pt}{Support for locality} &
 \parbox{100pt}{Yes} &
@@ -635,11 +628,6 @@
 \parbox{100pt}{No} &
 \parbox{100pt}{Yes} 
 \\ \hline
-       
-\parbox{90pt}{Design/Implementation complexity} &
-\parbox{100pt}{Low} &
-\parbox{100pt}{High} 
-\\ \hline
 
 \parbox{90pt}{Fault-tolerant} &
 \parbox{100pt}{High} &
@@ -1296,7 +1284,8 @@
 
 Somewhat surprisingly little research has been done in this area, especially 
when considering 
 the possible impact of \emph{unwanted social behavior} to performance of 
Peer-to-Peer 
-system. Problem is addressed by Golle et al. \cite{golle01incentivesp2p}. Some 
+system. The problem is addressed by Golle et al. \cite{golle01incentivesp2p}, 
Ngan et al. 
+\cite{ngan03enforcefile} and Shneidman et al. \cite{shneidman03rationality}. 
Some 
 research has been focused on semantic properties of the overlay in order to 
increase 
 cooperation among participating peers \cite{crespo02semanticoverlay}. 
Ramanathan et al. 
 \cite{ramanathan02goodpeers} and Bernstein et al. \cite{bernstein03selection} 
use 
@@ -1307,16 +1296,16 @@
 
 \subsection{Simulating Peer-to-Peer systems}
 
-Very little research has been done on simulating a \emph{global} Peer-to-Peer 
system. Presumably, this
+Very little research has been done on simulating a Peer-to-Peer system. 
Presumably, this
 is due to complex nature of Peer-to-Peer system, which makes comprehensive 
simulations very 
 difficult. Floyd et al. has been studying the simulation of the Internet in 
\cite{504642}. Authors
 state that simulating the Internet is very challenging task, because of 
Internet's heterogeneity
 and rapid change. Obviously, these factors exist also in Peer-to-Peer systems 
even with higher
 rates.
 
-As long as global simulations of Peer-to-Peer systems are lacking, we cannot 
make any detailed
-analysis on usage patterns in Peer-to-Peer systems. However, we can assume 
that, e.g., 
-query keywords follow the Zipf-like distributions \cite{breslau98implications} 
both in the 
+As long as comprehensive simulations of Peer-to-Peer systems are lacking, we 
cannot make any detailed
+analysis on general properties of Peer-to-Peer system such as usage patterns. 
However, we can assume 
+that, e.g., query keywords follow the Zipf-like distributions 
\cite{breslau98implications} both in the 
 Internet and in Peer-to-Peer systems.
 
 \section{Summary}
@@ -1926,14 +1915,17 @@
 
 \subsection{Algorithms}
 
-We use DOLR abstraction of tightly structured approach, i.e., each 
participating peer hosts 
-the data and overlay maintains only the \emph{pointers} to the data. We 
decided to use DOLR in our
-model, since DOLR systems locate data without specifying a storage policy 
explicitly \cite{rhea03benchmarks}. 
+We use the DOLR abstraction of tightly structured approach, i.e., each 
participating peer hosts 
+the data and overlay maintains only the \emph{pointers} to the data. We 
decided to use the DOLR 
+abstraction in our model, since DOLR systems locate data without specifying a 
storage policy explicitly \cite{rhea03benchmarks}. 
 DHT based storage systems, such as CFS \cite{dabek01widearea} and PAST 
\cite{rowstron01storage}, may have
 critical problems with load balancing in highly heterogeneous environment. 
This problem is caused by peers 
 which may not be able to store relatively large amount of data with key/value 
pair, assigned randomly by 
-mapping function of the overlay. Additionally, these systems wastes both 
storage and bandwidth, and
-are sensitive to certain attacks (e.g., DDoS attack).
+mapping function of the overlay. These systems wastes both storage and 
bandwidth, and
+are sensitive to certain attacks (e.g., DDoS attack). Additionally, we prefer 
\emph{abstraction}
+level analysis as very recently better and better tightly structured 
algorihtms have been proposed. 
+Thus, we don't want to bind our system proposal to a specific algorithm 
definitively as we expect 
+that this development continues.   
 
 In the following subsections we assume that we know the structure of 
 ''virtual file'' before hand, i.e., when assembling a ''virtual file'', we 
know all Storm 
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.107 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.108
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.107  Thu Mar 13 
04:55:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Thu Mar 13 
06:23:49 2003
@@ -2134,3 +2134,23 @@
        year = {2002},
        url = {http://www.jxta.org/project/www/docs/jsearch.pdf}
 }
+
+
address@hidden,
+       author = {Jeff Shneidman and David Parkes},
+       title = {Rationality and Self-Interest in Peer to Peer Networks},
+       booktitle = {Proceedings of the 2nd {I}nternational {W}orkshop on 
{P}eer-to-{P}eer {S}ystems ({IPTPS03})},
+       month = {February},
+       year = {2003},  
+       url = {http://iptps03.cs.berkeley.edu/final-papers/rationality.ps}
+}
+
address@hidden,
+       author = {Tsuen-Wan Ngan and Dan Wallach and Peter Druschel},
+       title = {Enforcing Fair Sharing of Peer-to-Peer Resources},
+       booktitle = {Proceedings of the 2nd {I}nternational {W}orkshop on 
{P}eer-to-{P}eer {S}ystems ({IPTPS03})},
+       month = {February},
+       year = {2003},  
+       url = {http://iptps03.cs.berkeley.edu/final-papers/rationality.ps}
+}  
+