[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: |
Wed, 08 Oct 2003 06:07:20 -0400 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Branch:
Changes by: Hermanni Hyytiälä <address@hidden> 03/10/08 06:07:20
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
Log message:
Barbara's comment #1
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.207&tr2=1.208&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.207
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.208
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.207 Mon Jun
2 08:14:08 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Wed Oct 8
06:07:18 2003
@@ -42,13 +42,13 @@
In this thesis, first we review existing Peer-to-Peer approaches, algorithms
and their
key properties. We summarize open problems in Peer-to-Peer systems and divide
these
problems into three sub-categories. We realize that there are many problems
and few
-practical solutions, and some problems have no solution at all.
+practical solutions, and recognize that some problems have no solution at all.
Then, we provide an overview of the Fenfire system. The Fenfire system is a
free
software effort to build a location transparent, hyperstructured desktop
environment.
-We evaluate existing Peer-to-Peer approaches-- loosely and tightly structured
overlays-- with regard
+We evaluate existing Peer-to-Peer approaches--loosely and tightly structured
overlays--with regard
to Fenfire's needs. Finally, we propose simple methods to efficiently locate
Fenfire
-data from Peer-to-Peer networks.
+data within Peer-to-Peer networks.
}
\tiivistelma{
Tässä opinnäytetyössä esittelemme olemassaolevia vertaisverkkoja, algoritmeja
ja
@@ -83,54 +83,53 @@
academia \cite{projectirisurl} and industry \cite{p2pworkinggroup, jxtaurl}
for a
number of reasons. The lack of centralization in Peer-to-Peer systems
means that the participants can form a distributed system
\cite{couloris94distributedsystems}
-without any investment to centralized hardware by sharing their services and
connecting to each
+without any investment in centralized hardware by sharing their services and
by connecting to each
other directly. Peer-to-Peer systems can be characterized as distributed
systems in which all
-communication is symmetric and all participant entities have similar
capabilities and responsibilities
+communication is symmetrical and all participant entities have similar
capabilities and responsibilities
\cite{oram01harnessingpower}. Schollmeier \cite{schollmeier01p2pdefinition}
describes a Peer-to-Peer system as a system of
distributed entities that share their own services.
Each entity, i.e., \emph{peer}, may contribute services to the overall system.
The distributed
and ad hoc nature of Peer-to-Peer improves scalability and avoids single
points of failure.
The Fenfire project is an attempt to build a hyperstructured, seamlessly
interoperating desktop
-environment. In the Fenfire system, all data is stored as blocks.
-Each block has a globally unique identifier and it can be referred, by pointer
blocks.
+environment. In the Fenfire system, all data is stored as "blocks".
+Each block has a globally unique identifier and it can be referenced to, by
pointer blocks.
Other features of Fenfire include innovative user
interfaces for viewing data. The applicability of Peer-to-Peer networking with
Fenfire for network
transparency is currently under investigation.
Three research problems are discussed in this thesis: First, finding the most
efficient
-way to locate and fetch Fenfire data block from a Peer-to-Peer network when
the block's
-identifier is given. Second, we want to find the most efficient way to locate
and fetch the most
-recent Fenfire data block from a Peer-to-Peer network referred by a pointer.
The third problem
-is similar to the second problem, except we want to locate and fetch the
Fenfire
-data block when a date and or time range is given.
+way to locate and fetch a Fenfire data block from a Peer-to-Peer network when
the block's
+identifier is given. Second, finding the most efficient way to locate and
fetch the most
+recent Fenfire data block from a Peer-to-Peer network referenced to by a
pointer. Finally, the
+challenge of locating and fetching the Fenfire data block when a date and or
time range is given.
In this thesis, we evaluate existing Peer-to-Peer approaches and
evaluate them, based on Fenfire's needs. We start by reviewing existing
Peer-to-Peer approaches,
-algorithms and their key properties. Our insight is that, despite the great
amount of proposed
+algorithms and their key properties. Our insight is that, despite the great
number of existing
Peer-to-Peer systems, we are able to classify \emph{all} systems either as
loosely or
tightly structured approaches. We also discuss open problems in
Peer-to-Peer research and divide problems into three sub-categories: security,
performance, and miscellaneous
problems. We attempt to comprehensively summarize existing algorithms and open
problems in the
Peer-to-Peer domain. This thesis does not provide detailed information about
reviewed algorithms nor
-open problems. More detailed information can be found from the references.
+open problems. More detailed information can be found within references.
Finally, we give an overview of the Fenfire project, and compare Peer-to-Peer
approaches to Fenfire's
-needs. Finally, we propose simple yet efficient methods that could be used for
data lookups in a Peer-to-Peer
+needs. We propose simple yet efficient methods that could be used for data
lookups in a Peer-to-Peer
environment.
\chapter{Peer-to-Peer architectures}
-In this chapter we will give a brief history and overview of Peer-to-Peer
networks,
-review the most important Peer-to-Peer algorithms and list key differences
between the
+In this chapter we provide a brief history and overview of Peer-to-Peer
networks,
+review the most important Peer-to-Peer algorithms, and list key differences
between the
two main approaches.
\section{Brief history and overview}
The Internet was originally established in the late 1960s \cite{253741}. The
objective
-of the ARPANET-project was to share information resources among military
computers
+of the ARPANET project was to share information resources among military
computers
in the United States. The most challenging purpose of ARPANET was to integrate
-different kinds of existing network technologies with one common network
architecture.
-The ARPANET connected the first few hosts together not in client--server
relationship,
+various kinds of existing network technologies with one common network
architecture.
+The ARPANET connected the first few hosts together not in a client--server
relationship,
but rather as equal networking \emph{peers}. This could be seen as the
starting point
of both the Peer-to-Peer concept and the Internet
\cite{oram01harnessingpower}.
@@ -142,7 +141,7 @@
network with regard to the ISO-OSI reference model (e.g., \cite{800902}).
Figure \ref{fig:application_level}
illustrates the Peer-to-Peer application level overlay network.
Compared to ARPANET's Peer-to-Peer functionality, modern Peer-to-Peer systems
-are \emph{ad hoc}, i.e., peers join and leave the system constantly. Thus,
this property
+are ad hoc, i.e., peers join and leave the system constantly. Thus, this
property
poses challenges for efficient construction and maintenance
of the overlay network, performing efficient data lookups and maintaining
security in
a distributed environment.
@@ -157,14 +156,14 @@
In the development of modern Peer-to-Peer systems, many influences have come
from
-outside of computer science. First, it is interesting to realize that chemical
properties of biological cells, the Internet, ad hoc
-Peer-to-Peer systems, and social network self-organize based on the same
+outside of computer science. First, it is interesting to realize that the
chemical properties of biological cells, the Internet, ad hoc
+Peer-to-Peer systems, and social networks self-organize based on the same
principles \cite{albert-02-statistical, albert-00-tolerance, watts00dynamics}.
Second, the
association between social relationships among people and Peer-to-Peer overlay
topology has been
recently studied \cite{watts00dynamics, kleinberg99small, nips02-Kleinberg}.
This insight is motivated by Milgram \cite{milgram67smallworld}, who noticed
that people very effectively
locate other people on a wide geographic scale based on local knowledge. This
phenomenon is called
-''small-world phenomenon''. As a consequence, many modern Peer-to-Peer systems
+''small-world phenomenon.'' As a consequence, many modern Peer-to-Peer systems
have applied similar techniques when constructing and maintaining the
application level
overlay network.
@@ -175,16 +174,16 @@
\section{Loosely structured}
-In the loosely structured approach the construction and maintenance of the
overlay is controlled
+In the loosely structured approach, the construction and maintenance of the
overlay is controlled
loosely. The placement of services and the topology of overlay is random. The
data lookup model in loosely structured systems is
not very efficient because of unstructured properties of the overlay. The data
lookup model is a combination of methods which
are used for locating data in the overlay.
\subsection{Proposed definition}
-In this subsection, we try to \emph{sketch out} a formal definition of the
loosely structured overlay. This
-model is based on the original Gnutella overlay network with power-law
improvements. Please notice that the
-definition proposal is not used elsewhere in this thesis.
+In this subsection, we try to sketch a formal definition of the loosely
structured overlay. This
+model is based on the original Gnutella overlay network with power law
improvements. Please notice that the
+definition proposed is not used elsewhere in this thesis.
Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the
aggregate of
all peers $p$ in the system. Then, $\forall s \in S$, there is a provider of
the service,
@@ -209,7 +208,7 @@
Gnutella \cite{gnutellaurl} is a well-known example of loosely structured
overlay system. Gnutella
is a pure Peer-to-Peer network as no peer is more important than any other
peer in the network.
The construction and maintenance of Gnutella network is extremely ad hoc,
since participating
-peers can form the overlay network based on \emph{local} knowledge (i.e., a
peer has no knowledge
+peers can form the overlay network based on local knowledge (i.e., a peer has
no knowledge
of global state of the system). Figure \ref{fig:gnutella_overlay}
illustrates the overlay network of Gnutella network. The Gnutella network can
be considered as a variation of power-law
graph \cite{albert-02-statistical}. In power-law graphs only few peers have
high
@@ -231,7 +230,7 @@
Gnutella network. Figure \ref{fig:gnutella_query} illustrates why Gnutella's
data lookup model has
$O(n^{2})$ properties.
-To limit the amount of network traffic, Gnutella uses Time-To-Live-limited
+To limit the amount of network traffic, Gnutella uses Time-To-Live limited
(TTL) flooding to distribute queries. Therefore, Gnutella's data lookup
algorithm is a Breadth-First-Search (BFS)
with depth limit $T$ (e.g., 7), where $T$ is the system-wide maximum TTL of a
message in hops. Thus,
only peers that are TTL hops away from the query originator will forward the
query or respond to the query.
@@ -246,14 +245,14 @@
\label{fig:gnutella_query}
\end{figure}
-According to \cite{lv02searchreplication}, Gnutella's way to perform data
lookups, \emph{flooding}, has the
+According to Lv et al. \cite{lv02searchreplication}, Gnutella's way to perform
data lookups, known as \emph{flooding}, has the
following limitations. First, choosing the appropriate TTL is not easy. If the
TTL is too high, the query originator may unnecessarily strain the network. If
the TTL is too
low, the query originator might not find the desired data even if it is
available somewhere
in the network. Second, there are many duplicate messages generated by
flooding, especially
-in high connectivity graphs. It is obvious that with these limitations,
flooding creates
+in high connectivity graphs. It is obvious that, with these limitations,
flooding creates
significant message processing overhead for each data lookup. Even worse,
flooding may increase
-the load on participating peer to the point where it has to leave the network.
+the load on a participating peer to the point where it has to leave the
network.
Adamic et al. \cite{adamic99small, adamic02localsearch,
adamic01powerlawsearch}
have studied different data lookup methods in power-law networks and have
found that by
@@ -288,21 +287,21 @@
\end{figure}
The improvements presented above are only partial solutions. More advanced
techniques
-to improve data lookup of loosely structured systems are discussed in chapter
3. Yet, however,
-techniques presented in chapter 3 are not adopted in any loosely structured
system.
+to improve data lookup of loosely structured systems are discussed in Chapter
3. However,
+techniques presented in Chapter 3 have not been adopted in any loosely
structured system.
\section{Tightly structured}
-Partly due to scalability problems of loosely structured systems, several
tightly
+Due partly to scalability problems of loosely structured systems, several
tightly
structured overlays have been proposed. In the tightly structured
-approach the overlay is constructed deterministically, which all participating
peers have to follow; the topology of the
+approach, the overlay is constructed deterministically, which all
participating peers must follow; the topology of the
overlay and the placement of services is controlled tightly.
\subsection{Proposed definition}
-In this subsection, we try to \emph{sketch out} a formal definition of the
tightly structured overlay, such as
+In this subsection, we try to sketch a formal definition of the tightly
structured overlay, such as
identifiers, identifier space and the mapping function. Please notice that the
-definition proposal is not used elsewhere in this thesis.
+definition proposed is not used elsewhere in this thesis.
Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the
aggregate of
all peers $p$ in the system. Let $I$ be the aggregate of all identifiers $i$
in the system.
@@ -318,28 +317,28 @@
\subsection{Systems}
-With tightly structured systems, it is feasible to efficiently perform
\emph{global} data lookups in the overlay. By global lookup, we mean
-that the system is able to find a service from the overlay, if it exists.
-While there are significant differences among proposed tightly structured
systems, they all have a common property,
-in that \emph{peer identifiers} are assigned to participating peers from
-a large \emph{identifier space} by the overlay. Globally unique identifiers,
\emph{keys},
+With tightly structured systems, it is feasible to efficiently perform global
data lookups in the overlay. By global lookup, we mean
+that the system is able to find a information from the overlay, if the
information exists.
+While there are significant differences among proposed tightly structured
systems, they all share common property:
+peer identifiers are assigned to participating peers from
+a large identifier space by the overlay. Globally unique identifiers, known as
\emph{keys},
are also assigned to application-specific data items
-which are selected from the same identifier space. For instance, globally
unique keys can be created
+that are selected from the same identifier space. For instance, globally
unique keys can be created
using a cryptographic content hash function (e.g., SHA-1 \cite{fips-sha-1})
over the contents of a data item.
The form of identifier space differs between proposed systems. A geometrical
circular form of identifier space (and variants)
is most widely used. For instance, Chord \cite{stoica01chord}, Koorde
\cite{kaashoek03koorde},
Pastry \cite{rowston01pastry}, SWAN \cite{bonsma02swan}, Tapestry
\cite{zhao01tapestry}
and Viceroy \cite{malkhi02viceroy} use a circular form of identifier space of
$n$-bit integers modulo $2^{n}$. The
-value of $n$ varies among systems. Again, CAN \cite{ratnasamy01can} uses a
$d$-dimensional geometrical torus
+value of $n$ varies among systems. On the other hand, CAN
\cite{ratnasamy01can} uses a $d$-dimensional geometrical torus
model to implement the form of identifier space.
To store data in a tightly structured overlay, each application-specific
-unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} uniformly (e.g.,
using consistent
+unique key (e.g., SHA-1 \cite{fips-sha-1}) is mapped uniformly (e.g., using
consistent
hashing \cite{258660}) to an existing peer in the overlay. Thus, a tightly
structured overlay assigns a subset of all possible keys to every
participating peer.
-We say that a peer is \emph{responsible} for the keys which are assigned by
the overlay.
+We say that a peer is responsible for the keys that are assigned by the
overlay.
Figure \ref{fig:structured_hashing} illustrates this
-process. Also, each peer in the tightly structured overlay maintains a
\emph{routing table}, which
+process. Also, each peer in the tightly structured overlay maintains a routing
table, which
consists of identifiers and IP addresses of other peers in the overlay.
Entries of the routing
table represent peer's neighbors in the overlay network.
@@ -350,14 +349,14 @@
\label{fig:structured_hashing}
\end{figure}
-Currently, all proposed tightly structured overlays provide at least
-poly--loga-rithmical data lookup operations. However, there are some key
+Currently, all tightly structured overlays provide at least
+polylogarithmical data lookup operations. However, there are some key
differences between the data structures representing the identifier space.
For example, Chord \cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and
SkipNet \cite{harvey03skipnet2} maintain a
-distributed data structure which resembles skip lists \cite{78977}.
+distributed data structure that resembles skip lists \cite{78977}.
In figure \ref{fig:structured_query}, we present an overview of Chord's data
lookup process.
On the right side of Chord's lookup process, the same data lookup process
-is shown as a binary-tree abstraction. It can be seen, that in each step, the
distance
+is shown as a binary-tree abstraction. It can be seen that, in each step, the
distance
decreases with a logarithmic efficiency.
\begin{figure}
@@ -368,7 +367,7 @@
\end{figure}
Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
-\cite{zhao01tapestry} use balanced $k$-trees to implement the data structure
of the identifier space. Figure
+\cite{zhao01tapestry} use balanced k-trees to implement the data structure of
the identifier space. Figure
\ref{fig:kademlia_lookup} shows the process of Kademlia's
data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data
structure (e.g., \cite{226658}),
which requires only a constant number of neighbor peers while providing
$O(\log{n})$ data lookup
@@ -384,9 +383,9 @@
\label{fig:kademlia_lookup}
\end{figure}
-Currently, there are only three higher level abstractions which are provided
by the tightly structured overlays
+Currently, only three higher level abstractions are provided by the tightly
structured overlays
\cite{zhao03api}. Each of these abstractions represent a storage layer in the
overlay, but
-have semantical differences in the \emph{usage} of the overlay.
+have semantical differences in the usage of the overlay.
First, Distributed Hash Table (DHT) (see e.g., \cite{dabek01widearea},
\cite{rowstron01storage})
implements the same functionality as a regular hash table by storing the
mapping between a key and a value:
@@ -397,12 +396,12 @@
\item \texttt{remove(key)}: remove a data item with a given key.
\end{itemize}
-DHT's \emph{interface} is generic; values can be any size and type (e.g.,
content hash over a file). In the
+DHT's interface is generic; values can be any size and type (e.g., content
hash over a file). In the
DHT abstraction the overlay itself stores the data items. Figure
\ref{fig:Structured_lookup_using_DHT_model} shows the DHT abstraction
of the tightly structured overlay.
Second, Decentralized Object Location (DOLR) (see e.g.,
\cite{kubiatowicz00oceanstore}, \cite{iyer02squirrel}) is a distributed
-directory service. DOLR stores \emph{pointers} to data items throughout the
overlay. DOLR's main
+directory service. DOLR stores pointers to data items throughout the overlay.
DOLR's main
operations are:
\begin{itemize}
@@ -412,8 +411,8 @@
\end{itemize}
-The key difference between the DHT and the DOLR abstraction is that, in the
DOLR abstraction, the overlay maintains only \emph{pointers} to the data.
-Also, the DOLR abstraction routes overlay messages to the nearest available
peer, hosting a specific data item. This form of locality
+The key difference between the DHT and the DOLR abstraction is that, in the
DOLR abstraction, the overlay maintains only pointers to the data.
+Also, the DOLR abstraction routes overlay messages to the nearest available
peer hosting a specific data item. This form of locality
is not supported by DHT. DOLR's interface is similar to the DHT's interface,
i.e., values can be any size and type.
Third, tightly structured overlays can be used for scalable group multicast or
anycast operations (CAST) (see e.g., \cite{zhuang01bayeux}).
@@ -447,34 +446,35 @@
\label{fig:Strucutred_lookup_using_DOLR_model}
\end{figure}
-In tightly structured systems, messages are routed across the overlay towards
peers, whose
+In tightly structured systems, messages are routed across the overlay toward
peers, whose
peer identifier is gradually ''closer'' to the key's identifier
in the identifier space. The distance can be measured by numerical
difference between identifiers (e.g., Chord \cite{stoica01chord}), number of
same prefix bits between identifiers (e.g., Pastry \cite{rowston01pastry} and
Tapestry
-\cite{zhao01tapestry}) or bit-wise exclusive or (XOR) (e.g., Kademlia
\cite{maymounkov02kademlia}).
+\cite{zhao01tapestry}) or Bit-Wise Exclusive Or (XOR) (e.g., Kademlia
\cite{maymounkov02kademlia}).
Chord's \cite{stoica01chord} distance function does have the property of
unidirection
(for a given point $p_i$ in the identifier space and distance $d$ > 0, there
is exactly one point $p_j$ in a way that the distance between $p_i$ and $p_j$
is $d$), but does not have symmetry (the distance from $p_i$ to $p_j$ is same
as the
distance from $p_j$ to $p_i$). Pastry's \cite{rowston01pastry} distance
function supports
-symmetry, but does not support unidirection. According to
\cite{balakrishanarticle03lookupp2p}, because
-of XOR-metric, Kademlia's distance function is both unidirectional and
symmetric. Moreover, Kademlia's \cite{maymounkov02kademlia}
+symmetry, but does not support unidirection. According to Balakrishnan et al.
\cite{balakrishanarticle03lookupp2p},
+Kademlia's distance function is both unidirectional and symmetric because of
the XOR-metric.
+Moreover, Kademlia's \cite{maymounkov02kademlia}
XOR-based metric does not need stabilization (like in Chord
\cite{stoica01chord}) and backup links
(like in Pastry \cite{rowston01pastry}).
However, in all of the above schemes, each hop in the overlay shortens the
distance between
current peer working with the data lookup and the key that was looked up in
the identifier space.
Skip Graphs \cite{AspnesS2003} and SWAN \cite{bonsma02swan} employ a
identifier space
-in which queries are routed to \emph{keys}. In these systems
+in which queries are routed to keys. In these systems
a peer occupies several positions in the identifier space, one for each
-application-specific key. The indirection of placing close keys in the
+application-specific key. The opposite action of placing close keys in the
custody of a provider peer is removed at the cost of each peer maintaining one
''resource peer'' in the overlay network for each data item it publishes. The
provider peer is a peer
-which has initially published services into the overlay.
+that has initially published services into the overlay.
PeerNet \cite{eriksson03peernet} differs from other tightly structured
overlays in that it operates
-at the \emph{network} layer instead of application layer (see the ISO-OSI
reference model, e.g., \cite{800902}).
+at the \emph{network} layer instead of application layer (see the ISO-OSI
reference model \cite{800902}).
This property would provide a common interface
to all Peer-to-Peer systems using PeerNet. PeerNet makes an explicit
distinction
between peer identity and address, which is not supported by standard
@@ -483,53 +483,53 @@
the system and $O(\log{n})$ data lookup efficiency.
Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four
requirements
-for tightly structured overlays\footnote{Authors use the term 'DHT' in their
text, but in this context
-it does not matter as they list \emph{general} properties of tightly
structured overlays.} that have to be addressed in order
+for tightly structured overlays\footnote{The authors use the term 'DHT' in
their text, but in this paper
+it is not meant to be specific as the authors list \emph{general} properties
of tightly structured overlays.} that 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
+First, the mapping of keys to peers must be done in a load-balanced
way. Second, the overlay must be able to forward a data lookup for a
-specific key to an appropriate peer. Third, overlay must
-support efficient distance function. Finally, routing tables for each peer
+specific key to an appropriate peer. Third, the overlay must
+support efficient distance function. Finally, the routing tables for each peer
must be constructed and maintained adaptively.
-Additionally, authors argue in \cite{balakrishnan03semanticfree} that tightly
structured systems
+Additionally, Balakrishnan et al. argue \cite{balakrishnan03semanticfree} that
tightly structured systems
are suitable for next generation Reference Resolutions Services (RRS)\footnote{
-Domain Name System (DNS) \cite{rfc1101} is a widely used RRS system in the
Internet.}. They present
+Domain Name System (DNS) \cite{rfc1101} is a widely used RRS system on the
Internet.}. They present
two requirements about the nature of reference resolution. First, there should
be a general-purpose
-and application-indepedent substrate for reference resolution. Second, the
references themselves
-should be unstructured and semantic-free. In this text, we define unstructured
reference
-as a reference that does not expose the target in any way and semantic-free
reference as a reference
-that there are no directives in the reference itself which would expose how
the reference should be processed.
+and application-indepedent substratum for reference resolution. Second, the
references themselves
+should be unstructured and semantic-free. In this paper, we define a
unstructured reference
+as one that does not expose the target in any way and a semantic-free
reference as a reference
+that has no directives in the reference itself that would expose how the
reference should be processed.
\section{Differences}
-Even though the loosely structured and the tightly structured approach are
both Peer-to-Peer schemes, they
-have very little in common. Indeed, the only thing they share is the fact that
no other peer is more
-important than any other in the Peer-to-Peer network. Fault tolerance
\emph{may}
-be an area in which approaches have similar properties (e.g., no single point
of failure) \cite{milojicic02peertopeer}.
-Fault tolerance properties of both approaches are currently only initial
calculations, or
-experimented in simulation environments. In real life, however, measuring
fault tolerance is a much more
-challenging task and requires more research to get reliable answers.
+Even though the loosely structured and the tightly structured approaches are
both Peer-to-Peer schemes, they
+have very little in common. Indeed, the only similarity they share is the fact
that no one peer is more
+important than another within the Peer-to-Peer network. Fault tolerance
\emph{may}
+be an other area in which these approaches have similar properties (e.g., no
single point of failure) \cite{milojicic02peertopeer}.
+The fault tolerance properties of both approaches are currently only initial
calculations, or
+experimented in simulation environments. In practical applications, however,
measuring fault tolerance is a much more
+challenging task and requires additional research to obtain reliable answers.
-The most important differences between approaches are the performance and
scalability properties.
-Generally tightly structured systems can perform all internal operations in
poly--logarithmic time
+The most important differences between the approaches are in the performance
and scalability properties.
+Generally, tightly structured systems can perform all internal operations in
polylogarithmic time,
while the performance of loosely structured systems is not always even linear
\cite{balakrishanarticle03lookupp2p}.
Moreover, loosely structured systems scale to millions of peers,
whereas tightly structured systems are able to cope with billions of
concurrent
peers \cite{osokine02distnetworks}, \cite{kubiatowicz00oceanstore}. However,
it is unknown
-whether all proposed algorithms can preserve logarithmic efficiency and
scalability properties
-in real-life applications or not; several tightly structured systems
+whether or not all proposed algorithms can preserve logarithmic efficiency and
scalability properties
+in real-life applications; several tightly structured systems
assume that participating peers are homogeneous, and the rate of join or leave
operation is low \cite{gurmeet03symphony,
libennowell01observations, rowston03controlloingreliability}.
-To the end user, the biggest difference between these systems is how data
lookups are performed. Loosely
-structured systems provide a more rich and user friendly way of searching data
than tightly structured systems
-as they have a support for keyword searches \cite{yang02efficientsearch,
lv02searchreplication}. Tightly structured
+For the end user, the biggest difference between these systems is how data
lookups are performed. Loosely
+structured systems provide a more rich and user friendly way of searching for
data than do tightly structured systems,
+as the former have a support for keyword searches \cite{yang02efficientsearch,
lv02searchreplication}. Tightly structured
systems support only exact key lookups since each data item is identified by
globally unique keys \cite{balakrishanarticle03lookupp2p,
harren02complex, ansaryefficientbroadcast03}.
-Table \ref{table_comparison_approach} lists the key differences between the
loosely structured
+Table \ref{table_comparison_approach} lists the primary differences between
the loosely structured
approach and the tightly structured approach.
@@ -613,15 +613,14 @@
Table \ref{table_Peer-to-Peer_algorithms} lists proposed Peer-to-Peer
algorithms
and their key properties with regard to performance and scalability. The list
includes algorithms from both loosely and tightly structured approaches. The
list does not
-include \emph{all} proposed Peer-to-Peer algorithms but rather includes the
ones which already have
-been widely deployed, or the ones which may be promising in the future
-Peer-to-Peer systems.
+include \emph{all} proposed Peer-to-Peer algorithms but rather includes the
ones that already have
+been widely deployed or which show promise for future Peer-to-Peer systems.
-We decided to follow the guidelines from \cite{kaashoek03koorde} in measuring
-the properties of different Peer-to-Peer systems. However, we dropped
-out fault tolerance and load balancing properties, since they are hard to
measure
-in real life requirements. Additionally, however, we decided to include
-the number of \emph{real} network connections for each peer in the overlay.
Next,
+We decided to follow the guidelines provided by Kaashoek et al.
\cite{kaashoek03koorde} in measuring
+the properties of various Peer-to-Peer systems. We eliminated
+out fault tolerance and load balancing properties from consideration since
they are difficult to measure
+in real life applications. However, we decided to include
+a number of real network connections for each peer in the overlay. Here,
we describe the listed properties of Peer-to-Peer algorithms:
\begin{itemize}
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...,
Hermanni Hyytiälä <=