[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 08:59:45 -0400 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Branch:
Changes by: Hermanni Hyytiälä <address@hidden> 03/10/08 08:59:45
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
Log message:
Barbara's comments #2
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.208&tr2=1.209&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.208
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.209
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.208 Wed Oct
8 06:07:18 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Wed Oct 8
08:59:43 2003
@@ -92,7 +92,7 @@
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".
+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
@@ -820,90 +820,91 @@
\chapter{Open Problems in Peer-to-Peer}
-In this chapter we discuss open problems in Peer-to-Peer research.
-Note that the unsolved problems considered do not represent
-an exhaustive survey of \emph{all} unsolved problems in Peer-to-Peer domain.
In this chapter
-we focus our attention on some issues related to security, scalability,
usability and performance.
+This chapter discusses open problems in Peer-to-Peer research.
+Note that the issues considered do not represent
+an exhaustive survey of all unsolved problems in Peer-to-Peer domain. We focus
+our attention on some issues related to security, scalability, usability and
performance.
\section{Overview}
-Partly due to the non-maturity of modern Peer-to-Peer technology, there are
several
-problems to be solved. Also, many techniques developed for traditional
distributed
-systems may no longer apply with Peer-to-Peer systems, e.g., load balancing
techiques \cite{byers03dhtbalancing}.
-
-Different problems apply to both the loosely structured and the tightly
structured approach.
-For instance, since the introduction of Gnutella \cite{gnutellaurl}, the main
concern has been the scalability problem of loosely structured
-systems. However, the scalability problem of the loosely structured is often
misunderstood;
-\emph{the network overlay} of loosely structured systems is scalable, but the
\emph{data lookup model} is not, because
-the data lookup process creates lot of extra network traffic (e.g.,
\cite{yang02improvingsearch}).
+Due partly to the immaturity of contemporary Peer-to-Peer technology, several
+problems need to be solved. Also, many techniques developed for
''traditional'' distributed
+systems may no longer apply to Peer-to-Peer systems, e.g., load balancing
techiques \cite{byers03dhtbalancing}.
+
+Various problems apply to both the loosely structured and the tightly
structured approaches.
+For instance, since the introduction of Gnutella \cite{gnutellaurl}, the
primary concern has been the scalability problem of loosely structured
+systems. However, the scalability of this loosely structured approach is often
misunderstood:
+the network overlay of loosely structured systems is scalable, but the data
lookup model is not, because
+the data lookup process creates too much extra network traffic (e.g.,
\cite{yang02improvingsearch}).
-In tightly structured systems the main objective is to make overlay's data
lookup process
+In tightly structured systems, the leading objective is to make overlay's data
lookup process
more fault tolerant against hostile attacks (e.g.,
\cite{castro02securerouting}). Other key problems in tightly structured
systems are the lack of keyword searches \cite{harren02complex,
ansaryefficientbroadcast03}, support for heterogeneous peers
-\cite{rowston03controlloingreliability} and load balancing
\cite{balakrishanarticle03lookupp2p, byers03dhtbalancing}.
+\cite{rowston03controlloingreliability}, and load balancing
\cite{balakrishanarticle03lookupp2p, byers03dhtbalancing}.
\section{Security problems}
-In this section we describe security problems related to the Peer-to-Peer
domain. First, we discuss well-known attacks
-on Peer-to-Peer systems. Then, we discuss the common lack of trust in
Peer-to-Peer system, and related issues of anonymity, access control, hostile
entities
+This sections deals with security problems related to the Peer-to-Peer domain.
First, we discuss well-known attacks
+on Peer-to-Peer systems. Then, we discuss the common lack of trust in a
Peer-to-Peer system, as well as the
+related issues of anonymity, access control, hostile entities
and secure query routing. Finally, we briefly cover external security threats.
\subsection{Attacks}
-As stated in \cite{naor03simpledht}, an important aspect is that when it comes
to different attack models in
-any Peer-to-Peer system, there should be a clear distinction between attacks
on the
-algorithms assuming the construction of the overlay is correct, and attacks on
the construction itself.
+As Naor et al. state \cite{naor03simpledht}, when it comes to different attack
models in
+any Peer-to-Peer system, a clear distinction between attacks on the
+algorithms, assuming the construction of the overlay is correct, and attacks
on the construction itself
+should be made.
There are five known attack models against Peer-to-Peer systems: the Sybil
attack \cite{douceur02sybil},
-the Fail-stop attack, the Spam attack \cite{naor03simpledht}, the Byzantine
attack \cite{357176, 296824}, and
+the Fail-stop and Spam generating attack \cite{naor03simpledht}, the Byzantine
attack \cite{357176, 296824}, and
the Distributed Denial of Service attack.
In the Sybil attack model \cite{douceur02sybil}, a hostile entity presents
multiple
-entities, i.e., when a peer communicates with a subset of other participating
entities to perform an operation whereas a peer communicates
-only with the same hostile entity. A hostile entity can control a large
fraction of a Peer-to-Peer system while
-repressing the redundancy of the system. Authors argue in
\cite{douceur02sybil} that without a centralized authority, Sybil attacks are
always possible in a Peer-to-Peer
-system except under extreme and unrealistic assumptions of resource parity and
coordination among entities. Unrealistic assumptions include: all entities
-should be nearly homogeneous; all identities can be validated simultaneously
by all
+entities. For instance, when a peer communicates with a subset of other
participating entities to perform an operation, a peer
+actually communicates only with the same hostile entity. A hostile entity can
control a large segment of a Peer-to-Peer system while
+repressing the redundancy of the system. Douceur argues \cite{douceur02sybil}
that, without a centralized authority, Sybil attacks are always possible in a
Peer-to-Peer
+system, except under the extreme and unrealistic assumptions of resource
parity and coordination among entities. Unrealistic assumptions include: all
entities
+would be nearly homogeneous; all identities can be validated simultaneously by
all
entities across the system; and, when accepting identities that are not
directly validated, the required number of certificates exceeds
-the number of systemwide failures \cite{douceur02sybil}. Castro et al.
\cite{castro02securerouting} suggest the use of cryptographic content hashes in
the
-creation process of peer identifier against the Sybil attack. According to the
authors, in this technique the IP address of a peer can be verified by the
other peer.
-They characterize this method as a form of \emph{self-certifying data}.
+the number of system wide failures \cite{douceur02sybil}. Castro et al.
\cite{castro02securerouting} suggest the use of cryptographic content hashes as
part of the
+creation process of peer identifier against the Sybil attack. According to the
Castro et al., the IP address of a peer can be verified by the other peer in
this technique.
+They characterize this method as a form of self-certifying data.
-In the Fail-stop attack model, cited in \cite{naor03simpledht}, a faulty peer
is deleted from the Peer-to-Peer system. Thus,
-a specific data item can be lost from the system temporarily or permanently.
The reason for the faultiness of a peer can be a
-software failure or a hostile attack. The Byzantine attack model \cite{357176}
is closely related to the Fail-stop model. In the Byzantine attack model,
+In the Fail-stop attack model \cite{naor03simpledht}, a faulty peer is deleted
from the Peer-to-Peer system either beacause a software
+failure of a hostile attack. Thus, a specific data item can be lost from the
system temporarily or permanently.
+The Byzantine attack model \cite{357176} is closely related to the Fail-stop
model. In the Byzantine attack model,
$3f + 1$ is the minimum number of peers that allow the system to provide the
safety and liveness properties when up to $f$ peers are faulty \cite{357176}.
-The Byzantine model can be seen as more severe than the Fail-stop model
because there are no restrictions over the behavior of faulty peers, e.g., the
cooperation
-between multiple \emph{malicious} faulty peers is possible \cite{357176}.
Castro et al. \cite{296824} have proposed a practical solution for the
Byzantine failures.
-The authors use in their work replication algorithm to tolerate Byzantine
faults and cryptographic
+The Byzantine model can be seen as more severe than the Fail-stop model
because there are no restrictions on the behavior of faulty peers, e.g., the
cooperation
+between multiple malicious faulty peers is possible \cite{357176}. Castro et
al. \cite{296824} have proposed a practical solution for the Byzantine
failures.
+The authors use in their work a replication algorithm to tolerate Byzantine
faults and cryptographic
certificate techniques to prevent spoofing and replays to detect corrupted
messages.
-The Spam generating attack \cite{naor03simpledht} is another known attack
model against a Peer-to-Peer system. In the Spam
-attack, a hostile or faulty peer may produce false data information, or
refuses to (or is not able to) reply to requests.
-Naor et al. \cite{naor03simpledht} have proposed a partial solution against
this Spam attack in a \emph{faulty} peer environment (not hostile).
+The Spam generating attack \cite{naor03simpledht} results when a hostile or
faulty peer produces false data information, or refuses to (or is not able to)
reply to requests.
+Naor et al. \cite{naor03simpledht} have proposed a partial solution against
this Spam attack in a faulty peer environment.
-Overloading of targeted peers is a form of Distributed Denial of Service
attack (DDoS) (see, e.g., \cite{372148}). For instance,
+The overloading of targeted peers is a form of Distributed Denial of Service
(DDoS) attack (see, \cite{372148}). For instance,
a hostile entity can attempt to burden specific peers with garbage network
packets. As a consequence, peers may act incorrectly or
stop working. Daswani et al. \cite{daswani02queryflooddos} suggest efficient
load balancing
policies for Peer-to-Peer systems in order to prevent massive system failures.
They suggest a traffic model
that can be used to understand the effects of DDoS attacks. Sit et al.
\cite{sit02securitycons}
suggest that an identifier assignment algorithm would assign an identifier
with respect to network topology
-and that replicas of data should be relocated physically to different
locations.
+and that replicas of data could be relocated physically to different locations.
\subsection{Trust management, data authenticity and integrity}
-According to \cite{aberer01trust}, mutual trust, ''...allows agents to
cooperate in a game-theoretic situation that corresponds
-to the repeated prisoners dilemma and leads in the long term to an increased
aggregated utility for the participating agents''.
-The authors of \cite{aberer01trust} define \emph{trust management} as a
mechanism that allows one to establish mutual trust. Furthermore,
\emph{reputation} is a measure
-that is derived from knowledge on interactions in the past
\cite{aberer01trust}. In this subsection, we briefly discuss mechanisms to
maintain
+According to Aberer et al. \cite{aberer01trust}, mutual trust, ''...allows
agents to cooperate in a game-theoretic situation that corresponds
+to the repeated prisoners dilemma and leads in the long term to an increased
aggregated utility for the participating agents.''
+Aberer et al. define \emph{trust management} as a mechanism that allows one to
establish mutual trust. Furthermore, \emph{reputation} is a measure
+that is derived from knowledge of past interactions in the past
\cite{aberer01trust}. In this subsection, we briefly discuss mechanisms to
maintain
trust in Peer-to-Peer systems.
-Currently, most trust mechanisms are based on \emph{reputation}. Some research
has been done on the reputation models in Peer-to-Peer
-systems, such as \cite{aberer01trust, cornelli02reputableservents}. In
\cite{aberer01trust}, the authors present a scalable
-trust management model, which can be used in a Peer-to-Peer enviroment. The
authors in \cite{cornelli02reputableservents}
-suggest techniques to keep track of and share reputation information regarding
a peer with others peers.
+Currently, most trust mechanisms are based on reputation. Some research has
been done on the reputation models in Peer-to-Peer
+systems, such as work by Aberer et al. \cite{aberer01trust} and Cornelli et
al. \cite{cornelli02reputableservents}. Aberer et al.
+present a scalable trust management model, which can be used in a Peer-to-Peer
enviroment. Cornelli et al.
+suggest techniques to keep track of and share reputation information between
and among peers.
Quite recently, the widely used Public Key Infrastructure (PKI) has been
deployed in distributed
systems \cite{rivest96sdsi}, \cite{spkiworkinggroup}. PKI is a reliable
technology for securing
@@ -911,34 +912,34 @@
networks, the problem of key-based security mechanisms may be the revocation
of keys and the
distribution of new keys in a hostile environment \cite{KohMau99}.
-ConChord \cite{ajmani02conchord} is the first Peer-to-Peer system which
supports the PKI based
-security infrastructure. Still, however, ConChord \cite{ajmani02conchord} is
in early phase of development and lacks
-important features of PKI to be fully usable. Furthermore, the hierarchy of
the Simple Distributed Security Infrastructure
+ConChord \cite{ajmani02conchord} is the first Peer-to-Peer system that
supports the PKI based
+security infrastructure. Still, ConChord \cite{ajmani02conchord} is in early
phases of development and lacks
+important features of PKI to be fully usable. Furthermore, the hierarchical
structure of the Simple Distributed Security Infrastructure
(SDSI) \cite{rivest96sdsi} and the Simple Public Key Infrastructure (SPKI)
\cite{spkiworkinggroup} may be a problem for
Peer-to-Peer systems, in which hierarchy is intentionally missing.
-On the other hand for data integrity, there are working techniques.
Cryptographic content hashes
-\cite{fips-sha-1}, including their variations \cite{merkle87hashtree} and
implementation techniques \cite{mohr02thex}
+On the other hand, there are working techniques for data integrity.
Cryptographic content hashes
+\cite{fips-sha-1}, including their variations \cite{merkle87hashtree} and
implementation techniques \cite{mohr02thex},
are efficient and reliable methods for identifying the integrity of data in
Peer-to-Peer systems.
\subsection{Anonymity}
-According to \cite{dingledine00free}, there exists several kinds of anonymity:
author-anonymity,
+According to Dingledine et al. \cite{dingledine00free}, there exists several
kinds of anonymity: author-anonymity,
publisher-anonymity, reader-anonymity, peer-anonymity and query-ano-nymity.
Author-anonymity is a form
of anonymity in which no one can link the document to its author.
Publisher-anonymity means that no one is able to determine the document to its
publisher.
Reader-anonymity means that a document cannot be linked to its readers.
-With peer-anonymity, no one is able to determine the peer, that originally was
published the document.
-Document-anonymity means that a peer does not know which data it is currently
hosting. Finally, query-anonymity is a form
+With peer-anonymity, no one is able to traceback the peer that originally was
published the document.
+Document-anonymity means that a peer does not know which data it are being
currently hosting. Finally, query-anonymity is a form
of document-anonymity: when other peers perform data lookups, a peer does not
know which local data is searched by
-the data lookup originators. As the authors of \cite{dingledine00free} cite,
some forms of anonymity
-may imply each other. Possible issues raised by this property is one area of
future work.
+the data lookup originators.
Obviously, the existence of several types of anonymity often conflicts with
other key properties of
-Peer-to-Peer systems. For example, let us consider anonymity and efficient
data lookup. In an efficient data lookup, we must know the
+Peer-to-Peer systems. Possible issues raised by this property is one area of
future work.
+For example, let us consider anonymity and efficient data lookup. In an
efficient data lookup, we must know
the peers responsible for any given data. Of course, when we know the peers
responsible
for the data, the anonymity of a peer is lost. Fortunately, there are partial
solutions to these kinds of
-situations, such as pseudonymity which is a partial form of anonymity
\cite{daswani03openproblems}.
+situations, such as pseudonymity \cite{daswani03openproblems}.
For instance, pseudonymity can be used for addressing peer-anonymity by
providing anonymous-like identifiers to
peers (e.g., peer identifiers of a tightly structured system).
@@ -946,27 +947,28 @@
proxies are used in Freenet \cite{clarke00freenet}, Crowds
\cite{reiter98crowds} and Free Haven \cite{dingledine00free}
in order to provide various types of anonymity. Tangler \cite{502002} and
Publius \cite{pub00} use cryptographic sharing methods
to split data into fragments \cite{Shamir1979a}. Mix mailer networks (e.g.,
\cite{mixminionurl}) are commonly used in
-distributed systems which are able to provide some level of anonymity (e.g.,
\cite{mneturl}).
+distributed systems and are able to provide some level of anonymity (e.g.,
\cite{mneturl}).
-Even if many existing Peer-to-Peer systems are able to provide some of the
types of anonymity, there is no
-such system which is able to provide complete anonymity in all levels (see
above). Specifically, the conflicts
-between anonymity and other properties of Peer-to-Peer systems require more
research work.
+Even if many existing Peer-to-Peer systems are able to provide some types of
anonymity, no
+current system is able to provide complete anonymity at all levels.
Specifically, the conflicts
+between anonymity and other properties of Peer-to-Peer systems require more
research.
\subsection{Access control}
Any distributed computing system must support different levels of access
control. For instance, in a Peer-to-Peer
-system, we may want to restrict the accessibility of data to the limited
amount of participating peers. Yet, Peer-to-Peer
+system, we may want to restrict the accessibility of data to a limited number
of participating peers. Yet, Peer-to-Peer
systems do not have a working access control scheme. Moreover,
-there have been lot of violations of copyright laws by users of Peer-to-Peer
file sharing systems. As a
+many violations of copyright laws are committed by users of Peer-to-Peer file
sharing systems. As a
consequence, some law suits have been filed against the companies who have
build popular file-sharing programs.
+Quite recently law suits have been filed against invidual users also.
Nejdl et al. \cite{nejdl03accesscontrol} have very recently proposed a
practical solution to access
control problem. They use Resource Description Framework (RDF) \cite{w3rdfurl}
based
schema policies to restrict access to certain data. Their current early
prototype version only works in
loosely structured systems.
-More research work is required in the development of \emph{working} access
control scheme for Peer-to-Peer
+More research is required for developing a working access control scheme for
Peer-to-Peer
systems.
@@ -978,15 +980,15 @@
of peer identifiers that cannot be controlled by a hostile entity.
One possible solution is to use a self-monitoring system, such as SOMO
\cite{zhang03somo}, in which a self-monitoring overlay
-constantly analyses the Peer-to-Peer overlay. Self-monitoring overlay is built
on top of Peer-to-Peer overlay. Authors in
-\cite{sit02securitycons} suggest the use of system invariants. They emphasize
that system invariants should be verifiable, and if
-system invariants fail the system must have a recovery mechanism. In
distributed peer identifier assignment \cite{castro02securerouting,
clarke00freenet},
+constantly analyzes the Peer-to-Peer overlay. A self-monitoring overlay is
built on top of the Peer-to-Peer overlay. Sit et al.
+\cite{sit02securitycons} suggest the use of system invariants. They emphasize
that system invariants should be verifiable and if
+system invariants fail, the system must have a recovery mechanism. In the
distributed peer identifier assignment model \cite{castro02securerouting,
clarke00freenet},
multiple participating peers participate in a creation of peer identifier.
-Centralized authorities could be used for the assignment of peer identifiers,
but they may not be suitable
-for ad hoc Peer-to-Peer environment and have property of single point of
failure. Distributed peer
-identification assignment can be problematic as long as the Sybil attack
\cite{douceur02sybil} remains unsolved.
-However, there are some partial solutions for controlling the \emph{rate} at
which hostile entity is able to obtain peer
+Centralized authorities could be used for assigning of peer identifiers, but
they may not be suitable
+for the ad hoc Peer-to-Peer environment and have the property of single point
of failure. The distributed peer
+identification assignment can be problematic as long as the potential for the
Sybil attack \cite{douceur02sybil} remains unsolved.
+However, some partial solutions exist for controlling the rate at which
hostile entity is able to obtain a peer
identifier, such as crypto-based puzzles \cite{juels99clientpuzzles}.
\subsection{Secure query routing}
@@ -994,42 +996,41 @@
Secure query routing is essential to any Peer-to-Peer system. By secure
routing in this context, we mean that a Peer-to-Peer system
is able to deliver a network message thoughout the overlay to a correct
destination efficiently.
-Aspnes et al. in \cite{aspnes02faultrouting} and Kaashoek et al. in
\cite{kaashoek03koorde} formally
-prove the lower and upper bounds for the space requirements of locating a
specific data item reliably in a
+Aspnes et al. \cite{aspnes02faultrouting} and Kaashoek et al.
\cite{kaashoek03koorde} formally
+proved the lower and upper bounds for the space requirements of locating a
specific data item reliably in a
Peer-to-Peer system. They show that to provide high degree of fault tolerance
and efficiency in the system, each
participating peer must maintain average of $O(\log{n})$ neighbors.
-Authors argue in \cite{castro02securitystructured} that with the combination
of
-secure peer identifer assignment, secure routing table maintenance and secure
message forwarding
-secure query routing in tightly structured systems is possible. Additionally,
authors cite in \cite{castro02securerouting}
+Castro et al. \cite{castro02securitystructured} argue that with the
combination of
+secure peer identifer assignment, secure routing table maintenance, secure
message forwarding
+and secure query routing in tightly structured systems is possible.
Additionally, Castro et al. cite in \cite{castro02securerouting}
that the probability of routing successfully between arbitrary
correct peers is $(1-f)^{h-1}$, when a fraction $f$ of the other peers are
faulty or hostile and where
$h$ is the number of hops in the overlay. Sit and Morris
\cite{sit02securitycons} discuss the possibility of
allowing the query originator to observe lookup progress and cross-check
routing tables using random queries to achieve
secure routing in tightly structured overlay. However, their
-approach is not very efficient, since this method creates a lot of additional
network traffic when
-in function i.e., it is unknown if this technique is realizable in an
efficient way.
+approach is not very efficient, since this method creates much of additional
network traffic when
+in use i.e., it is unknown if this technique is realizable in an efficient way.
Lynch et al. \cite{lynch02atomicdataaccess} propose a solution for secure
routing table
-maintenance, but their solution seems to have two major problems according to
\cite{castro02securitystructured}.
+maintenance, but their solution seems to have two major problems according
Castro et al. \cite{castro02securitystructured}.
First, the solution is very expensive even without faulty or hostile entities.
Second, each group of replicas
-in their solution must have less than 1/3 of its peers faulty. This feature
results in a low
+in Lynch et al.'s solution must have less than 1/3 of its peers faulty. This
feature results in a low
probability of successful routing.
-Fiat et al. in \cite{fiat02censorship, saia02dynamicfaultcontentnetwork}
-and Datar in \cite{datar02butterflies} propose a tightly structured overlay
with secure query routing in the
+Fiat et al. \cite{fiat02censorship, saia02dynamicfaultcontentnetwork}
+and Datar \cite{datar02butterflies} propose a tightly structured overlay with
secure query routing in the
presence of hostile entities. However, none of these proposals address a
dynamic tightly structured
overlay with fault tolerance against multiple rounds
-of hostile attacks. Also, above mentioned proposals are not very efficient. In
\cite{fiat02censorship}, each peer
-must maintain information of $O(\log^3{n})$ other peers, and in
\cite{datar02butterflies}, $O(\log^2{n})$ is required.
+of hostile attacks. Also, the above mentioned proposals are not very
efficient. In Fiat et al.'s proposal each peer
+must maintain information of $O(\log^3{n})$ other peers and in Datar's
$O(\log^2{n})$ is required.
\subsection{Other security threats}
-Ross Lee Graham lists several external threats against Peer-to-Peer networks
\cite{grahamp2psecurity}. Most important,
-the list includes viruses and trojans. Currently, there are not even partial
solutions
-to the problems mentioned above. The reason for this is that there is no
experience about these kinds of
-attacks. Possible solution would be a distributed anti-virus software, but
much more intensive research is required until
-this kind of solution would be applicable.
+Ross Lee Graham \cite{grahamp2psecurity} lists several external threats
against Peer-to-Peer networks. Most potent threats include
+viruses and trojans. Currently, not even partial solutions to the problems
mentioned above are available principally
+because there is no practical experience with these attacks. A possible
solution could be a distributed
+anti-virus software, but much more intensive research is required before this
kind of solution would be applicable.
\subsection{Summary}
@@ -1072,20 +1073,20 @@
\parbox{90pt}{DoS attack \cite{sit02securitycons,
saia02dynamicfaultcontentnetwork, datar02butterflies, daswani02queryflooddos,
juels99clientpuzzles}} &
\parbox{110pt}{Distributed, controlled burden against specific computer(s).} &
\parbox{110pt}{Client puzzles, load balancing, traffic measurements, traffic
models, replication.} &
-\parbox{110pt}{Only partial solutions, traffic models most effective.}
+\parbox{110pt}{Only partial solutions; traffic models most effective.}
\\ \hline
\parbox{90pt}{Sybil attack \cite{douceur02sybil, castro02securerouting}} &
\parbox{110pt}{Single hostile entity presents multiple entities.} &
-\parbox{110pt}{Identify all peers simultaneously across the system, collect
pool of peers which are validated, distributed peer ID creation.} &
-\parbox{110pt}{Not practically realizable, research focused on persistence,
not on identity distinction.}
+\parbox{110pt}{Identify all peers simultaneously across the system, collect
pool of peers that are validated, distributed peer ID creation.} &
+\parbox{110pt}{Not practically realizable; research focused on persistence,
not on identity distinction.}
\\ \hline
\parbox{90pt}{Spam attack \cite{naor03simpledht}} &
-\parbox{110pt}{Hostile entity creates false versions of data, or gives wrong
information about the data which entity is responsible for/knows about.} &
-\parbox{110pt}{Do not trust to single entity, get information from multiple
entities, trust on majority's opinion.} &
+\parbox{110pt}{Hostile entity creates false versions of data, or gives wrong
information about the data that entity is responsible for/knows about.} &
+\parbox{110pt}{Avoid trusting to single entity; get information from multiple
entities; trust on majority's opinion.} &
\parbox{110pt}{Easy to implement, creates more network traffic.}
\\ \hline
@@ -1100,7 +1101,7 @@
\parbox{90pt}{Data integrity/authenticity \cite{fips-sha-1},
\cite{rivest96sdsi}, \cite{spkiworkinggroup}} &
\parbox{110pt}{Integrity/originality of data is unknown.} &
\parbox{110pt}{Cryptographic content hashes, key architectures.} &
-\parbox{110pt}{For data integrity, there are working solutions, but for data
authenticity, some of the solutions are partial, which may be practically
realizable.}
+\parbox{110pt}{For data integrity, there are working solutions, but for data
authenticity, some of the solutions are partial, and may be practically
realizable.}
\\ \hline
@@ -1121,21 +1122,21 @@
\parbox{90pt}{Access Control \cite{nejdl03accesscontrol,
daswani03openproblems}} &
\parbox{110pt}{Can we define access control levels in Peer-to-Peer network ?} &
\parbox{110pt}{Schema-based rules.} &
-\parbox{110pt}{Some initial experiences, needs more research.}
+\parbox{110pt}{Initial experiments underway; needs more research.}
\\ \hline
\parbox{90pt}{Inconsistent behavior \cite{sit02securitycons}} &
\parbox{110pt}{Hostile peer could act correctly with its neighbors, but
incorrectly with others.} &
\parbox{110pt}{Public keys, digital signatures.} &
-\parbox{110pt}{Not practical approach/working proposal created yet.}
+\parbox{110pt}{Yet, practical proposal does not exist.}
\\ \hline
\parbox{90pt}{Hostile groups \cite{castro02securerouting}} &
-\parbox{110pt}{Joining peer may join parallel network, formed a group of
hostile peers, hostile peer(s) controls the construction of the network.} &
-\parbox{110pt}{Use trusted peers, based on history information, cryptography,
key infrastructure.} &
-\parbox{110pt}{Not 100\% sure if Central Authority (CA) is missing, not
practical approach/working proposal created yet.}
+\parbox{110pt}{A peer may join parallel network, formed a group of hostile
peers, hostile peer(s) controls the construction of the network.} &
+\parbox{110pt}{Use trusted peers, based on previous information, cryptography,
key infrastructure.} &
+\parbox{110pt}{Yet, practical proposal does not exist.}
\\ \hline
@@ -1163,95 +1164,95 @@
\subsection{Efficient data lookup}
-The most intensive research in Peer-to-Peer domain has been focused on
efficient data lookup methods,
-especially with the loosely structured approach.
+The most intensive research in the Peer-to-Peer domain has focused on
efficient data lookup methods,
+especially within the loosely structured approach.
In iterative deepening \cite{yang02improvingsearch}, multiple BFS searches are
initiated
with successively larger TTL depth limits, until either the query is
satisfied,
-or the maximum depth $D$ has been reached. Expanding ring, proposed by Shenker
et al. in \cite{lv02searchreplication},
+or the maximum depth $D$ has been reached. Expanding ring, proposed by Shenker
et al. \cite{lv02searchreplication},
is similar to the iterative deepening technique. In this method, a peer starts
a flood with small TTL, and
waits to see if the search is successful. If it is, then the peer stops the
data lookup. Otherwise, the peer increases
the TTL and starts another data lookup. With these techniques, searches
-may not be fast when desired data item requires several consecutive flooding
rounds.
+may not be fast when the desired data item requires several consecutive
flooding rounds.
Directed BFS \cite{yang02improvingsearch} optimizes the original
-BFS in a way that a peer selects the neighbors which have provided many
quality results in the past,
+BFS in a way that a peer selects the neighbors that have provided many quality
results in the past,
thereby maintaining the quality of costs and decreasing the amount
of messages sent to network.
-In the local indices technique \cite{yang02improvingsearch}, each peer
maintains an index over the data of all peers within
-$h$ hops of itself, where $h$ is a system-wide variable, called radius of the
+In the local indices technique \cite{yang02improvingsearch}, each peer
maintains an index of the data of all peers within
+$h$ hops of itself, where $h$ is a system-wide variable, called a radius of the
index\footnote{In the normal BFS case, the value of $h$ is 0, as a peer only
has index
over its local content.}. Thus, when a peer receives a data lookup request, it
can
process the request on behalf of every node within $r$ hops. Compared to
original BFS,
-the local indices technique keeps data lookup cost low while maintaining the
same
+the local indices technique keeps the data lookup cost low while maintaining
the same
number of search results.
In the random walk approach \cite{lv02searchreplication}, a peer forwards
query to a
randomly selected neighbor. The basic random walk approach
has a poor response time but it does not generate as much network traffic as
-the original BFS. As suggested in \cite{lv02searchreplication}, the
+the original BFS. As Lv et al. \cite{lv02searchreplication} suggest, the
random walk approach can be made more effective by introducing
-multiple simultaneously working ''walkers''.
+multiple, simultaneously working ''walkers.''
Freenet \cite{clarke00freenet} uses random walk searches in data lookups.
Freenet's data lookup model resembles
-Depth-First-Search (DFS) and peers' routing tables are dynamically built
+Depth-First-Search (DFS) in which peers' routing tables are dynamically built
using caching. This is an outcome of Freenet's main design principles,
anonymity.
-Another property of the Freenet's data lookup model is that
+Another property of Freenet's data lookup model is that
it adapts well to varying usage patterns (e.g., searching for popular data
items in the overlay).
Improvements to Freenet's data lookup using
-the ''small-world'' techniques have been proposed by Zhang et al.
\cite{zhang02using}.
+social life's small-world techniques have been proposed by Zhang et al.
\cite{zhang02using}.
Since tightly structured systems have an efficient data lookup at the
application level overlay,
current research efforts are focused on the proximity-based data lookup. In
the proximity-based data lookup,
-peers try to choose entries of routing-tables referring to other peers that
are \emph{nearby} in the
+peers try to choose entries of routing-tables referring to other peers that
are nearby in the
underlying network. In this way, tightly structured systems are able to
decrease the actual
-lookup \emph{latency}. CAN \cite{ratnasamy01can}, Kademlia
\cite{maymounkov02kademlia},
-Pastry \cite{rowston01pastry} and Tapestry \cite{zhao01tapestry} have advanced
heuristics for
+lookup \emph{latency}. Kademlia \cite{maymounkov02kademlia},
+Pastry \cite{rowston01pastry}, CAN \cite{ratnasamy01can} and Tapestry
\cite{zhao01tapestry} have advanced heuristics for
the proximity-based routing. Additionally, most recent version of Chord uses
proximity-based
routing, inspired by Karger and Ruhl \cite{karger02findingnearest}. SkipNet
\cite{harvey03skipnet1}
uses a combination of proximity and application level overlay routing when
performing data
-lookups. Authors call this feature as a \emph{constrained load balancing}.
+lookups. The authors call this feature a constrained load balancing.
\subsection{Fast and usable search}
To make Peer-to-Peer systems even more popular (and usable), these systems
have to support flexible, efficient
and simple search methods \cite{li03feasibility}. Currently, loosely
structured systems are able to carry out the flexibility and
simplicity requirements and tightly structured systems are able to fulfill the
efficiency requirement.
-Research efforts have been focused to make security methods in tightly
structured systems more usable and flexible. However, studies
+Research efforts have concentrated on making security methods in tightly
structured systems more usable and flexible. However, studies
show that combining flexible search methods and tightly structured systems may
not be trivial: tightly
structured algorithms perform data lookups based on a globally unique
identifier thereby making efficient keyword searches hard to implement
\cite{harren02complex, ansaryefficientbroadcast03}.
Some studies have been concentrated on SQL-like queries \cite{harren02complex}
-in tightly structured overlays. It is unknown, however, if this approach is
realizable to implement, since
-initial analysis have shown that this approach is rather complex. Other
approaches include adaption of the data lookup model of the loosely
+in tightly structured overlays. It is unknown, however, if this approach is
implementable, since
+initial analysis have shown that this approach is rather complex. Other
approaches include the adaption of the data lookup model of the loosely
structured approach into tightly structured systems
\cite{ansaryefficientbroadcast03}.
-Authors' work is based on insight that
-performing a data lookup in the overlay resembles regular tree-like search,
where trees' data structure
-is distributed throughout the overlay. Some studies suggest additional layer
upon overlay network \cite{kronfol02fasdsearch,
-joseph02p2players}, which use metadata to implement search methods. The
feasibility of implementing additional
+This work is based on insight that
+performing a data lookup in the overlay resembles a regular ''tree-like''
search, where the trees' data structure
+is distributed throughout the overlay. Some studies suggest an additional
layer upon overlay network \cite{kronfol02fasdsearch,
+joseph02p2players}, which would use metadata to implement search methods. The
feasibility of implementing an additional
search layer on top of the network layer is questionable, especially if the
search layer and the network
layer have different assumptions about the participating peers (e.g., the
network layer supports heterogeneity
-of peers, but the search layer does not). Andrzejak et al. propose range
queries \cite{andrzejak02rangequeries}
+of peers, but the search layer does not). Andrzejak et al.
\cite{andrzejak02rangequeries} propose range queries
to be used with tightly structured overlays. In this technique, it is feasible
to perform data lookups
-using ranges of keys thereby covering larger amount of possible data items.
Currently their prototype
+using ranges of keys, thereby covering larger amount of possible data items.
Currently their prototype
is designed for the CAN system \cite{ratnasamy01can}.
-Recent study has been focused on the feasibility of Peer-to-Peer Web-like
indexing and searching
-on top of tightly structured overlays \cite{li03feasibility}. Authors argue
that it is possible to implement
-Peer-to-Peer Web-like search with certain compromises. First, Peer-to-Peer
search engine may need to
+A recent study by Li et al. \cite{li03feasibility} has focused on the
feasibility of Peer-to-Peer Web-like indexing and searching
+on top of tightly structured overlays. The authors argue that it is possible
to implement
+Peer-to-Peer Web-like search with certain compromises. First, a Peer-to-Peer
search engine may need to
decrease the result quality in order to make searching more efficient. Second,
Peer-to-Peer systems must
consult the properties of underlying network for better performance.
Additionally, many techniques have been developed in order to provide more
efficient search indexing. As
several studies show, the popularity of queries in the Internet follow
Zipf-like
distributions\footnote{Zipf-distribution is a variant of power-law function.
-Zipf-distribution can be used in observation of frequency of occurrence event
$E$, as a function of the rank
+Zipf-distribution can be used in observing the frequency of occurrence event
$E$, as a function of the rank
$i$ when the rank is determined by the frequency of occurrence, is a power-law
function $E_i \sim \frac{1}{i^{a}}$,
where the exponent $a$ is close to unity.} (e.g.,
\cite{breslau98implications}).
-Therefore, according to \cite{li03feasibility}, caching and pre-computation
can be done for optimizing search indices.
-Authors in \cite{li03feasibility} use gap compression \cite{wittengigabytes},
adaptive set intersections \cite{338634}
+Therefore, according to Li et al., caching and pre-computation can be done for
optimizing search indices.
+Li et al. use gap compression \cite{wittengigabytes}, adaptive set
intersections \cite{338634}
and clustering with their search optimizations. Regular compression
algorithms, Bloom filters \cite{362692}, vector
space models \cite{CuencaAcuna2002DSIWorkshop} and view trees
\cite{Bhattacharjee03resultcache} can be used for even
better optimizations.
@@ -1263,66 +1264,66 @@
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 a loosely
+systems require fewer system management properties than tightly structured
systems: in a loosely
structured system, peers join and leave the system constantly without any
restrictions \cite{saroiu02measurementstudyp2p}.
-On the other hand, however, peers in tightly structured system join and leave
the system but have less freedom,
+On the other hand, peers in tightly structured system join and leave the
system with less freedom,
i.e., overlay chooses peer's neighbors on behalf of the peer itself and maps
data items randomly
throughout the overlay network \cite{balakrishanarticle03lookupp2p}.
-Almost all presented algorithms
+Almost all current algorithms
for the tightly structured systems have been analyzed under static simulation
-environments \cite{libennowell01observations}. Furthermore, proposed tightly
structured overlays are configured statically to achieve
-the desired reliability even in an uncommon and adverse environment
\cite{rowston03controlloingreliability}.
-Thus, one of the most important factors for future research is to get
real-life experiences from tightly structured
-systems, when there are frequent joins and leaves of peers in the system.
+environments \cite{libennowell01observations}. Furthermore, proposed tightly
structured overlays are configured statically in
+order to achieve the desired reliability even in an uncommon and adverse
environment \cite{rowston03controlloingreliability}.
+Thus, one of the most important factors for future research is to obtain
real-life experiences from tightly structured
+systems, when there are frequent joinings and departures of peers in the
system.
-As mentioned before, an implicit assumption of almost every tightly structured
system is that there is a random, uniform
+As mentioned earlier, an implicit assumption of almost every tightly
structured system is that there is a random, uniform
distribution of peer and key identifiers. Even if participating peers are
extremely heterogeneous, e.g., in
computing power or network bandwidth, all data items are distributed
uniformly. Clearly, this is
-a serious problem of tightly structured overlays in face of performance and
load balancing \cite{rao03loadbalancing}.
-Measurement study by Saroiu et al. show that there is extreme heterogeneity
among participating peers in already deployed Peer-to-Peer
-systems \cite{saroiu02measurementstudyp2p}.
+a serious problem of tightly structured overlays in the face of performance
and load balancing \cite{rao03loadbalancing}.
+The measurement study by Saroiu et al. \cite{saroiu02measurementstudyp2p}
shows that there is
+extreme heterogeneity among participating peers in already deployed
Peer-to-Peer systems.
Some research has been done with regard to load balancing properties of
tightly structured
-overlays. Byers et al. suggest an idea of ''power of two choices'' whereby
data item is stored at the less loaded
-of two (or more) random peer alternatives \cite{byers03dhtbalancing}. Rao et
al. use virtual servers
-to control the load balance in a Peer-to-Peer system
\cite{rao03loadbalancing}. Their work rests on the
-idea which was originally introduced by Chord \cite{stoica01chord} system.
-Ledlie et al. propose techniques for forming and maintaining groups in a
highly dynamic environment
-\cite{ledlie02selfp2p}. Their work relies on the idea that
+overlays. Byers et al. \cite{byers03dhtbalancing} suggest a ''power of two
choices'' whereby
+data item is stored at the less loaded of two (or more) random peer
alternatives. Rao et al. \cite{rao03loadbalancing}
+use virtual servers to control the load balance in a Peer-to-Peer system.
Their work rests on the
+idea that was originally introduced by Chord \cite{stoica01chord} system.
+Ledlie et al. \cite{ledlie02selfp2p} propose techniques for forming and
maintaining groups in a highly dynamic environment.
+Their work relies on the concept that
participating peers would create multiple hierarchical groups. It is not clear
whether this approach
-is scalable or fault tolerant and suitable for Peer-to-Peer environment. More
promising work has been done by Rowston et al.
-in \cite{rowston03controlloingreliability}. Authors propose techniques for
self-tuning, dealing with
-uncommon conditions (e.g., network partition and high failure rates).
Moreover, authors argue that
-with these techniques, the concerns over tightly structured overlay
maintenance costs are no more
+is scalable or fault tolerant and and therefore suitable for Peer-to-Peer
environment. More promising
+work has been done by Rowston et al. \cite{rowston03controlloingreliability}.
They propose techniques for self-tuning and
+dealing with uncommon conditions (e.g., network partition and high failure
rates). Moreover, Rowston et al. argue that
+with these techniques, the concerns over tightly structured overlay
maintenance costs are no longer
an open issue.
Also, query and routing hot spots may be an issue in tightly structured
overlays \cite{ratnasamy02routing}.
-Hot spots happen, when a 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}. Authors' technique is especially suitable for the DOLR
abstraction of tightly structured overlays.
-They argue that with Sloppy hashing, the generation of query hot spots can be
reduced and peers are able
+Hot spots happen when a specific key is being requested extremely often in
tightly structured overlays. A recent study
+by Freedman et al. \cite{sloppy:iptps03} tries to reduce hot spots in the
system by performing sloppy hashing.
+This technique is especially suitable for the DOLR abstraction of tightly
structured overlays.
+Freedman et al. argue that with sloppy hashing, the generation of query hot
spots can be reduced and peers are able
locate nearby data without looking up data from distant peers.
-The concept of ''half-life'' was introduced by Liben-Nowell
\cite{libennowell01observations} since Peer-to-Peer
-system is \emph{never} in the ''ideal'' state as Peer-to-Peer system is
continuously evolving system. Half-life is defined
-as follows: let there be $N$ live peers at time $t$. The doubling from time
$t$ is the time that pass before
+The concept of ''half-life'' was introduced by Liben-Nowell
\cite{libennowell01observations} since
+Peer-to-Peer systems are continously evolving; they are never in the ''ideal''
state.
+Half-life is defined as follows: let there be $N$ live peers at time $t$. The
doubling from time $t$ is the time that pass before
$N$ new additional peers arrive into the system. The halving time from time
$t$ is the time
required for half of the living peers 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 over all times $t$. Concept of half-time can be used as a
basis for developing
-more powerful analytical tools for modelling complex Peer-to-Peer systems.
+more powerful analytical tools for modeling complex Peer-to-Peer systems.
-Finally, little research has been done regarding self-monitoring. Zhang et al.
-describe an arbitrary data structure on top of a tightly structured overlay
\cite{zhang03somo}. Authors
-call their technique as a \emph{data overlay}, since it supports several
fundamental data structures.
-Authors have used this data overlay when building a Self-Organized Metadata
Overlay (SOMO), which can be used
+Finally, little research has been done regarding self-monitoring. Zhang et al.
\cite{zhang03somo}
+describe an arbitrary data structure on top of a tightly structured overlay.
The authors
+call their technique a data overlay, since it supports several fundamental
data structures.
+Zhang et al. have used this data overlay when building a Self-Organized
Metadata Overlay (SOMO), which can be used
for monitoring the health of a tightly structured overlay. The fault tolerance
of SOMO itself is currently
unknown.
\subsection{Summary}
-In this subsection we list performance and usability problems in Peer-to-Peer
research. For each table entry,
+This subsection lists performance and usability problems in Peer-to-Peer
research. For each table entry,
there is a brief description of the problem, possible solutions and comments.
@@ -1351,8 +1352,8 @@
\parbox{90pt}{Web indexing and searching \cite{li03feasibility,
Bhattacharjee03resultcache, 362692, CuencaAcuna2002DSIWorkshop,
rhea02probabilistic, joseph02neurogrid, crespo02semanticoverlay,
joseph02p2players, chord:om_p-meng, wittengigabytes, 338634}} &
\parbox{110pt}{Perform Web like searches in Peer-to-Peer network.} &
-\parbox{110pt}{Data compression, view trees, bloom filters and its variations,
gap compression, index intersection optimizations, clustering.} &
-\parbox{110pt}{Effective but complex solutions, some compromises have to be
done (decrease result quality, modify overlay's structure), more research
needed.}
+\parbox{110pt}{Data compression, view trees, bloom filters, gap compression,
index intersection optimizations, clustering.} &
+\parbox{110pt}{Effective but complex solutions, some compromises have to be
made (decrease result quality, modify overlay's structure), more research
needed.}
\\ \hline
@@ -1361,30 +1362,30 @@
ramanathan02goodpeers, kleinberg99small, nips02-Kleinberg, zhang02using,
watts00dynamics, karger02findingnearest,
brinkmann02compactplacement, rhea02probabilistic, castro02networkproximity,
ng02predicting, pias03lighthouse, waterhouse02searchp2p, botros01jxtasearch,
ganesan02yappers}} &
-\parbox{110pt}{Find resource efficiently, if resource exists (loosely
structured).} &
+\parbox{110pt}{Find resources efficiently, if a resource exists (loosely
structured).} &
\parbox{110pt}{Super peers, peer clusters, caching techniques.} &
-\parbox{110pt}{More efficient, less network traffic, not comparable to the
efficiency of tightly structured systems.}
+\parbox{110pt}{More efficient, less network traffic; not comparable to the
efficiency of tightly structured systems.}
\\ \hline
\parbox{90pt}{Richness of queries \cite{harren02complex,
ansaryefficientbroadcast03, andrzejak02rangequeries}} &
\parbox{110pt}{Query languages should be more powerful in tightly structured
overlays.} &
\parbox{110pt}{SQL-like queries.} &
-\parbox{110pt}{Hard to implement, increases system complexity, not much
research has been done.}
+\parbox{110pt}{Hard to implement, increases system complexity; not much
research has been done.}
\\ \hline
\parbox{90pt}{Robustness \cite{datar02butterflies,
saia02dynamicfaultcontentnetwork, fiat02censorship, aspnes02faultrouting,
albert-00-tolerance, libennowell01observations}} &
-\parbox{110pt}{How well system performs under hostile attacks/in the case of
severe failure ?} &
+\parbox{110pt}{How well does a system perform under hostile attacks/in the
case of severe failure ?} &
\parbox{110pt}{Self-tuning, backup links, use diverse routing paths, power-law
networks/properties.} &
\parbox{110pt}{Partially working solutions.}
\\ \hline
\parbox{90pt}{Quality of Service} &
-\parbox{110pt}{The system can only provide (at most) best effort services.} &
+\parbox{110pt}{The system can only provide (at most) its best effort
services.} &
\parbox{110pt}{Use network proximity for better network performance
(bandwidth, latency, jitter, packet loss).} &
-\parbox{110pt}{Increases system complexity, some initial experiences, need
more research.}
+\parbox{110pt}{Increases system complexity; need more research.}
\\ \hline
@@ -1398,7 +1399,7 @@
\parbox{90pt}{Network proximity \cite{pias03lighthouse, ng02predicting,
ratnasamy02ght, eriksson03peernet, castro02networkproximity}} &
\parbox{110pt}{Can we take into account the underlying network's properties
better when forming overlay network (network-awareness for performance) ?} &
\parbox{110pt}{Global network positioning, lighthouse technique, triangulated
heuristics.} &
-\parbox{110pt}{Increases system complexity, no real world experience in a wide
scale, proposed solutions are susceptible to single point of failure.}
+\parbox{110pt}{Increases system complexity; no real world experience in a wide
scale; proposed solutions are susceptible to single point of failure.}
\\ \hline
@@ -1412,24 +1413,24 @@
\parbox{90pt}{Hot spots \cite{258660, sloppy:iptps03,
maymounkov03ratelesscodes}} &
\parbox{110pt}{What will happen if some resource is extremely popular and only
one peer is hosting it ?} &
\parbox{110pt}{Caching, multisource downloads, replication, load balancing,
sloppy hashing.} &
-\parbox{110pt}{For query hot spots, caching and multisource downloads
efficiently reduce hot spots, for routing hot spots, benefits are smaller.}
+\parbox{110pt}{For query hot spots, caching and multisource downloads
efficiently reduce hot spots; for routing hot spots, benefits are smaller.}
\\ \hline
\parbox{90pt}{Load balancing \cite{rao03loadbalancing, ledlie02selfp2p,
byers03dhtbalancing}} &
\parbox{110pt}{Random (but uniformly distributed) identifier selection could
cause system inbalance among participants with different capabilities.} &
\parbox{110pt}{Caching, virtual server transfers.} &
-\parbox{110pt}{Effective, more research required in fully dynamic environment.}
+\parbox{110pt}{Effective; more research required in fully dynamic environment.}
\\ \hline
\parbox{90pt}{System in flux \cite{libennowell01observations, 571863,
ledlie02selfp2p, albert-02-statistical}} &
-\parbox{110pt}{Peers join and leave system constantly. What about load
balancing and performance ?} &
-\parbox{110pt}{Half-life phenomenon (for analysis), simple overlay maintenance
and construction algorithm.} &
-\parbox{110pt}{Initial theoretical analysis have been created, but not
comprehensive model for analyzing different system states and its variations
(e.g. complex usage patterns).}
+\parbox{110pt}{Peers join and leave a system constantly. What about load
balancing and performance ?} &
+\parbox{110pt}{Half-life phenomenon (for analysis); simple overlay maintenance
and construction algorithm.} &
+\parbox{110pt}{Initial theoretical analysis have been created, but not a
comprehensive model for analyzing different system states and variations (e.g.
complex usage patterns).}
\\ \hline
\parbox{90pt}{Sudden network partition \cite{harvey03skipnet1,
harvey03skipnet2, rowston03controlloingreliability}} &
-\parbox{110pt}{Sub network is isolated from other network because of network
disconnection.} &
+\parbox{110pt}{Sub network is isolated from larger network because of network
disconnection.} &
\parbox{110pt}{Self-tuning, environment observation, localized network
connection for minimum latency (backup connections).} &
\parbox{110pt}{Creates more overhead/space requirements per peer.}
\\ \hline
@@ -1437,14 +1438,14 @@
\parbox{90pt}{Fail Stop \cite{rowston03controlloingreliability, zhang03somo}} &
\parbox{110pt}{A faulty peer stops working.} &
\parbox{110pt}{Failure detectors, informing algorithms.} &
-\parbox{110pt}{Creates more network traffic, peer's information can be
outdated, failure detectors not reliable.}
+\parbox{110pt}{Creates more network traffic; peer's information can be
outdated; failure detectors not reliable.}
\\ \hline
\parbox{90pt}{Byzantine faults \cite{296824}} &
\parbox{110pt}{Faulty peers may behave arbitrarily.} &
-\parbox{110pt}{Byzantine replication algorithms, get information from multiple
entities, trust majority's opinion.} &
-\parbox{110pt}{Much research has been done on this field, practical solutions,
decreases system performance slightly.}
+\parbox{110pt}{Byzantine replication algorithms; get information from multiple
entities; trust majority's opinion.} &
+\parbox{110pt}{Much research has been done on this field; practical solutions;
decreases system performance slightly.}
\\ \hline
\caption{Performance and usability problems in Peer-to-Peer.}
@@ -1457,36 +1458,38 @@
\section{Miscellaneous problems}
-In this section we discuss miscellaneous problems in Peer-to-Peer systems.
+This section we discusses miscellaneous problems in Peer-to-Peer systems.
\subsection{Programming guidelines and benchmarks}
-All existing Peer-to-Peer systems have rather different interfaces even though
they have common properties and
-components (e.g., \cite{zhao03api}). More important, all existing Peer-to-Peer
systems are incompatible with each other. One
+All existing Peer-to-Peer systems have rather unique programming interfaces
even though they have common properties and
+components. More important, all existing Peer-to-Peer systems are incompatible
with each other. One
of the most important area of future research is to create common programming
abstractions, i.e.,
-interfaces, design patterns and frameworks. Also, benchmarks are needed for
comparing
-the efficiency of different algorithms equally.
+interfaces, design patterns and frameworks. Also, benchmarks are needed for
comparing equally
+the efficiency of different algorithms.
-Recently, there have been few proposals towards common programming guidelines.
Authors in
-\cite{zhao03api} propose a higher level abstractions for tightly structured
overlays. Frise et al. suggest the use of
-additional layer in Peer-to-Peer system to hide the structure of the overlay
\cite{frise02p2pframework}.
+Recently, there have been few proposals towards common programming guidelines.
Zhao et al. \cite{zhao03api}
+propose a higher level abstractions for tightly structured overlays. Frise et
al. \cite{frise02p2pframework}
+suggest the use of an additional layer in the Peer-to-Peer system to hide the
structure of the overlay.
With their abstraction, both the loosely structured and tightly structured
approach can be used in the system.
-Montresor proposes a framework supporting developers and researchers in the
design of Peer-to-Peer system
-\cite{babaoglu02anthill}.
+Montresor \cite{babaoglu02anthill} proposes a framework supporting developers
and researchers in the design
+of Peer-to-Peer system.
-Very early experiments with Peer-to-Peer benchmarking include
\cite{rhea03benchmarks}. Currently, authors'
+Very early experiments with Peer-to-Peer benchmarking include thw ork by Rhea
et al. \cite{rhea03benchmarks}. This
work focus on application-driven benchmarks for tightly structured overlays.
\subsection{Social behavior}
-Frequent assumption in Peer-to-Peer systems is that peers are willing to
cooperate (e.g., \cite{shneidman03rationality}).
-Another belief is that all peers would behave equally, i.e., all peers both
consume and contribute services \cite{saroiu02measurementstudyp2p}.
-However, these assumptions are not true as several publications show: peers
rather consume than contribute and are
+According to Shneidman et al. \cite{shneidman03rationality}, frequent
assumption in Peer-to-Peer systems is
+that peers are willing to cooperate.
+Another belief is that all peers would behave equally, i.e., all peers both
consume and contribute
+services \cite{saroiu02measurementstudyp2p}.
+However, these assumptions are not true as several publications show: peers
consume rather than contribute and are
unwilling to cooperate \cite{saroiu02measurementstudyp2p,
oram01harnessingpower, hearn02mojonation}.
-Somewhat surprisingly little research has been done in this area, especially
when considering
-the possible impact of \emph{unwanted social behavior} to performance of a
Peer-to-Peer
-system. The problem is addressed by Golle et al. \cite{golle01incentivesp2p},
Ngan et al.
+Somewhat surprisingly, little research has been done in this area, especially
when considering
+the possible impact of unwanted social behavior on the performance of a
Peer-to-Peer
+system. This 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
co-operation among participating peers \cite{crespo02semanticoverlay}, i.e.,
peers'
@@ -1494,25 +1497,25 @@
Ramanathan et al. \cite{ramanathan02goodpeers} and Bernstein et al.
\cite{bernstein03selection} use
empirical metrics and decision trees when teaching peers to make better
decisions
when contacting other peers in Peer-to-Peer system. Alpine \cite{alpineurl} is
an example of
-Peer-to-Peer system, which uses empirical metrics for a peer selection.
+Peer-to-Peer system, that uses empirical metrics for a peer selection.
\subsection{Simulating Peer-to-Peer systems}
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 \cite{bhagwan03availability}. Floyd et al. have been studying the
simulation of the Internet in \cite{504642}. Authors
-state that simulating the Internet is very challenging task, because of its
heterogeneity
-and rapid change. These factors exist also in Peer-to-Peer systems even with
higher
+is due to the complex nature of the Peer-to-Peer system, which makes
comprehensive simulations very
+difficult \cite{bhagwan03availability}. Floyd et al. \cite{504642} have been
studying the simulation of the Internet. The
+authors aknowledge that simulating the Internet is very challenging because of
its heterogeneity
+and rapid change. These factors exist also in Peer-to-Peer systems which
experience these trends at even higher
rates.
As long as comprehensive simulations of a Peer-to-Peer systems are lacking, we
cannot make any detailed
-analysis on general properties of a Peer-to-Peer system, such as usage
patterns of participating peers.
+analysis on the general properties of a Peer-to-Peer system, such as usage
patterns of participating peers.
\subsection{Summary}
-In this subsection we list miscellaneous problems in Peer-to-Peer research.
For each table entry,
-there is a brief description of the problem, possible solutions and comments.
+In this subsection we list miscellaneous problems in current Peer-to-Peer
research. For each table entry below,
+a brief description of the problem, possible solutions and comments are
provided.
\scriptsize
\begin{longtable}{|l|l|l|l|}
@@ -1539,28 +1542,28 @@
\parbox{90pt}{Mutual distrust \cite{cornelli02reputableservents,
aberer01trust}} &
-\parbox{110pt}{Nobody trusts anybody.} &
+\parbox{110pt}{Peers don't trust each other.} &
\parbox{110pt}{Reputation methods, key infrastructures.} &
-\parbox{110pt}{Resource demanding, not practical to implement/not working
solutions, no real world experience in a wide scale.}
+\parbox{110pt}{Resource demanding, not practical to implement and not working
solutions; no real world experience in a wide scale.}
\\ \hline
\parbox{90pt}{Lack of motivation to cooperate \cite{golle01incentivesp2p,
ngan03enforcefile, shneidman03rationality}} &
-\parbox{110pt}{All participants do not behave like they should be, instead
they go for own profit.} &
+\parbox{110pt}{Peers tend to go only for own profit.} &
\parbox{110pt}{Different reputation methods.} &
\parbox{110pt}{No real world experience in a wide scale.}
\\ \hline
\parbox{90pt}{Heterogeneity \cite{saroiu02measurementstudyp2p,
brinkmann02compactplacement, zhao02brocade, gurmeet03symphony,
rowston03controlloingreliability}} &
-\parbox{110pt}{There are different kind of peers in the system, in light of
bandwidth and computing power.} &
-\parbox{110pt}{Super peers (loosely structured), clusters (loosely structured)
additional layer upon tighty structured systems, structure itself is simple
(tightly structured).} &
-\parbox{110pt}{Working solutions, increases system complexity (additional
layer).}
+\parbox{110pt}{Various types of peers in the system of bandwidth and of
computing power.} &
+\parbox{110pt}{Super peers (loosely structured); clusters (loosely structured)
additional layer upon tighty structured systems; structure itself is simple
(tightly structured).} &
+\parbox{110pt}{Working solutions; increases system complexity (additional
layer).}
\\ \hline
\parbox{90pt}{Programming guidelines \cite{zhao03api, frise02p2pframework,
babaoglu02anthill, rhea03benchmarks, garciamolina03sil,
balakrishnan03semanticfree}} &
-\parbox{110pt}{Set of programming guidelines/frameworks is needed for better
interoperability between different systems.} &
+\parbox{110pt}{Set of programming guidelines/frameworks is needed for better
interoperability among different systems.} &
\parbox{110pt}{Common frameworks and APIs.} &
\parbox{110pt}{Common framework/API is still missing, a few proposals have
been made (tightly structured).}
\\ \hline
@@ -1569,20 +1572,20 @@
\parbox{90pt}{Comprehensive simulations or analysis of Peer-to-Peer system} &
\parbox{110pt}{Ability to simulate whole Peer-to-Peer network's usage
patterns, network traffics, flux state etc.} &
\parbox{110pt}{Use same techniques as simulating/analyzing the Internet.} &
-\parbox{110pt}{Only small subsets of Peer-to-Peer networks has been analysed,
because of ad hoc properties of network, more powerful solutions needed.}
+\parbox{110pt}{Only small subsets of Peer-to-Peer networks have been analyzed,
because of ad hoc properties of network; more powerful solutions needed.}
\\ \hline
\parbox{90pt}{Overlay management and health monitoring \cite{zhang03somo}} &
-\parbox{110pt}{System is self-capable to monitor it is status and health for
better performance.} &
-\parbox{110pt}{Build a meta data overlay atop of structured overlay (such as
SOMO for structured overlays), make local decisions about overlay (loosely
structured).} &
-\parbox{110pt}{For tightly structured overlays, efficient and simple to
implement, fault tolerance unknown, for the loosely structured approach not
necessarily efficient because decisions are based on local knowledge.}
+\parbox{110pt}{System is self-capable to monitor its status and health for
better performance.} &
+\parbox{110pt}{Build a metadata overlay atop the structured overlay (such as
SOMO for structured overlays); make local decisions about overlay (loosely
structured).} &
+\parbox{110pt}{For tightly structured overlays; efficient and simple to
implement; fault tolerance unknown; for the loosely structured approach, not
necessarily efficient because decisions are based on local knowledge.}
\\ \hline
\parbox{90pt}{Locating Peer-to-Peer network} &
\parbox{110pt}{How old peers or new peers are able to locate Peer-to-Peer
network, if it exists.} &
-\parbox{110pt}{Servers maintaining online peers (e.g. gnutellahosts.com),
peer's history information.} &
-\parbox{110pt}{Depends on implementation and purpose of the system, for a
desktop system there are working solutions.}
+\parbox{110pt}{Servers maintaining online peers (e.g. gnutellahosts.com);
peer's history information.} &
+\parbox{110pt}{Depends on implementation and purpose of the system; for a
desktop system there are working solutions.}
\\ \hline
\caption{Miscellaneous problems in Peer-to-Peer.}