[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/04 05:00:17

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

Log message:
        System maintenance

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.106 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.107
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.106      Tue Mar 
 4 03:15:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Mar  4 
05:00:17 2003
@@ -1267,26 +1267,24 @@
 argue, that it is possible to implement Peer-to-Peer Web-like search with 
certain radical compromises. 
 First, Peer-to-Peer search enginge may need to decrease result quality in 
order make searching more
 efficient. Second, Peer-to-Peer systems must observe better the properties of 
underlying network for
-better performance. Study list include \cite{kronfol02fasdsearch}, 
\cite{harren02complex}, 
-\cite{joseph02p2players}, \cite{Bhattacharjee03resultcache}, 
\cite{andrzejak02rangequeries},
-\cite{ansaryefficientbroadcast03} and \cite{chord:om_p-meng}. 
-
-Many techniques have been developed in order to provide more efficient search 
indexing. First, as 
-studies queries follow Zipf-like distributions \cite{breslau98implications} 
caching and precomputation
-can be done for optimizting search indices \cite{li03feasibility}. Second, 
regular compression algorithms
-and Bloom filters \cite{362692} can be used for even better optimizations. 
-
-
-
-
-
-
-
-
-
+better performance. 
 
+Some studies have been concentraded on SQL-like queries \cite{harren02complex},
+in tightly structured overlays. Another approaches include adapting loosely 
structured approache's
+data lookup model into tightly structured systems 
\cite{ansaryefficientbroadcast03}, \cite{chord:om_p-meng}.
+Additional studies include additional layer upon overlay network 
\cite{kronfol02fasdsearch}, 
+\cite{joseph02p2players} and range queries \cite{andrzejak02rangequeries}.
 
+Many techniques have been developed in order to provide more efficient search 
indexing. As 
+studies queries follow Zipf-like distributions \cite{breslau98implications} 
caching and precomputation
+can be done for optimizting search indices \cite{li03feasibility}. Regular 
compression algorithms,
+Bloom filters \cite{362692}, vector space models 
\cite{CuencaAcuna2002DSIWorkshop} and view 
+trees \cite{Bhattacharjee03resultcache} can be used for even better 
optimizations. In addition, authors 
+in \cite{li03feasibility} use Gap compression \cite{wittengigabytes}, Adaptive 
Set Intersection \cite{338634}  
+and Clustering with their search optimizations.
 
+While it is expected that web-like searches can be layered on top of tightly 
structured overlay, much
+more research is required to make indexing and searching more efficient.
 
 \cite{ramanathan02goodpeers}
 
@@ -1294,54 +1292,65 @@
 
 \subsection{System management}
 
-Symphony seems to be the first DHT system which support hetergeneity 
\cite{gurmeet03symphony}
-
-
-Better load balancing techiques:
--Better and simple load balancing \cite{byers03dhtbalancing} (insight: "power 
of two choices" whereby an item is stored at the less loaded of two (or more) 
random alternatives)
-
-%One question is: how well SWAN can self-organise, e.g. in the case of Tuomas' 
scanario #2 ?
-
-Half-life phenomenon \cite{libennowell01observations}
-%Current decentralized, but structured \cite{chord, can, pastry, Tapestry 
etc.) ignores the fact 
-that a P2P system is never in 'ideal' state. P2P system is always evolving 
system.
-
--techniques for maintaining DHT structure in real and dynamic environment 
\cite{rowston03controlloingreliability}
--this is not problem any more for structured p2p overlay networks
--results can be directly applied to other DHTs
+Adaptive system management and self-organization are essential properties
+of any Peer-to-Peer system, since centralized control over the system is 
missing. Loosely structured
+systems require less system management properties than tightly structured 
systems; in loosely
+structured system, peers join and leave the system constantly without any 
restrictions. On the
+other hand, however, peers in tightly structured system have less freedom, 
i.e. overlay chooses peer's
+neighbors on behalf of peer itself and maps data items randomly throughout the 
overlay network. However,
+Peer-to-Peer system is \emph{never} in ''ideal'' state as it is always 
evolving system.
+
+Current research has been focused on tightly structured systems' system 
management, since all presented
+algorithms have been analyzed under static simulation environments. 
Furthermore, propsed tightly structured
+overlays are configured statically to achieve the desired reliability even in 
uncommon and adverse environment
+\cite{rowston03controlloingreliability}. The most important factor for
+future research is to get real-life experiences from tightly structured 
system, when there are frequent
+joins and leaves in the system. Some research has been done already in this 
area. 
 
-Half-life concept:
-'Let there be N live nodes at time t. The doubling from time t is the time 
that pass before
+A concept of ''half-life'' was introduced by Liben-Nowell 
\cite{libennowell01observations}. Half-life is defined
+as follows: let there be N live nodes at time t. The doubling from time t is 
the time that pass before
 N new additional nodes arrive into the system. The halving time from time t is 
the time
 requires for half of the living nodes at time t to leave the system. The 
half-life from 
 time t is smaller of the properties stated above. The half-life of the entire 
system is the 
-minimum half-life overl all times t.'
+minimum half-life overl all times t. Concept of half-time can be used as basic 
for developing
+more efficient analytical tools for modelling complex Peer-to-Peer system. 
 
-Heterogeneity
-%Current decentralized, but structured \cite{chord, can, pastry, Tapestry 
etc.) designs assume
-that all participating peers are equal, in terms of processing power, memory 
and network bandwidth.
-However, recent measurement study \cite{saroiu02measurementstudyp2p} exhibits 
the fact that in p2p networks, 
-there is a great amount of heterogeneity among participating peers.
-
-Proposal, Brocade: Landmark routing on overlay networks \cite{zhao02brocade}
--Secondary overlay layer on top of routing layer, which exploits knowledge of
-underlying network properties
-
-\cite{sloppy:iptps03}
-\cite{libennowell01observations}
-\cite{karger02findingnearest}
-\cite{rao03loadbalancing}
-\cite{zhang03somo}
-\cite{bhagwan03availability}
-\cite{zhao02brocade}
-Practical Byzantine fault tolerance \cite{296824}
-Byzantine Generals \cite{357176}
-
-%dup
-\cite{liben-nowell02observatorionsp2p}
-\cite{571863}
+Some research has been done with regard to load balancing properties of 
tightly structured
+overlays. Byers et al. suggest "power of two choices" whereby an item is 
stored at the less loaded 
+of two (or more) random alternatives \cite{byers03dhtbalancing}. Rao et al. 
uses virtual servers
+to control load balance in Peer-to-Peer systems \cite{rao03loadbalancing}. 
Their work rests on
+idea which was originally introduced by Chord system.
+
+Also, query and routing hotspots may be an issue in tightly structured 
overlays \cite{ratnasamy02routing}. 
+Hotspots happen, when specific key is being requested extremely often in 
tightly structured overlays. Recent study 
+by Freedman et al. tries to reduce hot spots in the system by performing 
\emph{sloppy} hashing 
+\cite{sloppy:iptps03}. Another key feature of their work is that peers 
self-organize into clusters, 
+therefore enabling peers to find nearby data without looking up data from 
distant peers.
+
+An implicit assumption of almost every tightly structured system is that there 
is random, uniform 
+distribution of peer and key identifiers. Even if participating peers are 
extremely heterogeneous in
+face of computing power, or network bandwidth, data items are distributed 
uniformly. Clearly, this
+a serious problem of tightly structured overlays , since measurement study by 
Saroiu et al. shows 
+that there extreme heterogeneity among participating peers in already deployed 
Peer-to-Peer systems.
+\cite{saroiu02measurementstudyp2p}. Symphony seems to be the first tightly 
structured overlay system 
+which support hetergeneity. However, Zhao et al. have proposed a secondary 
layer a top of structured overlay
+to support hetergeneity better \cite{zhao02brocade}. 
+
+Research has been done on self-organization. Ledlie et al. propose techniques 
for forming and maintaining
+groups in highly dynamic environment \cite{ledlie02selfp2p}. Unfortunately 
their work relies on idea that
+participating peers would create multiple hierarchical groups; it's not clear 
whether this approach
+is fault-tolerant and suitable to Peer-to-Peer environment. More promising 
work has been done by Rowston et al.
+in \cite{rowston03controlloingreliability}. Authors propose techiques for 
self-tuning, dealing with
+uncommon conditions (e.g., network partition and high failure rates). 
Moreover, authors arque that
+these techniques, the concerns over the tightly structured overlay maintenance 
costs are no more
+an open issue.
+
+Finally, little research has been done regarding self-monitoring and data 
availability. Zhang et al.
+describe a arbitrary data structure on top of tightly structured overlay 
\cite{zhang03somo}. They
+call their proposal as \emph{data overlay}, since it support several 
fundamental data structures.
+Authors use this data overlay to build Self-Organized Metadata Overlay (SOMO), 
which can be used
+for monitoring health of tightly structured overlay. 
 
-\cite{ledlie02selfp2p}
 
 \section{Miscellaneous problems in Peer-to-Peer}
 
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.93 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.94
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.93   Tue Mar  4 
03:15:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Tue Mar  4 
05:00:17 2003
@@ -2061,8 +2061,6 @@
        year = {1979}
 } 
 
-
-
 @inproceedings{breslau98implications,
        author = "L. Breslau and P. Cao and L. Fan and G. Phillips and S. 
Shenker",
        title = "On the Implications of Zipf's Law for Web Caching",
@@ -2070,3 +2068,27 @@
        year = "1998",
        month = "June",         
 }
+
+
address@hidden,
+       author = {Ian H. Witten and Alistair Moffat and Timothy~C. Bell},
+       title = {Managing Gigabytes: Compressing and Indexing Documents and 
Images},
+       year = {1999},
+       publisher = {Morgan Kaufmann Publishers}
+}
+
address@hidden,
+       author = {Erik D. Demaine and Alejandro L?pez-Ortiz and J. Ian Munro},
+       title = {Adaptive set intersections, unions, and differences},
+       booktitle = {Proceedings of the eleventh annual ACM-SIAM symposium on 
Discrete algorithms},
+       year = {2000},
+       isbn = {0-89871-453-2},
+       pages = {743--752},
+       location = {San Francisco, California, United States},
+       doi = {http://doi.acm.org/10.1145/338219.338634},
+       publisher = {ACM Press},
+}
+
+
+ 
+