[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: |
Thu, 09 Oct 2003 05:56:50 -0400 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Branch:
Changes by: Hermanni Hyytiälä <address@hidden> 03/10/09 05:56:50
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
Log message:
polish
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.211&tr2=1.212&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.211
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.212
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.211 Thu Oct
9 05:49:00 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Thu Oct 9
05:56:49 2003
@@ -135,10 +135,10 @@
The most popular form of modern Peer-to-Peer computing is file-sharing. In
this scenario,
participants of Peer-to-Peer networking share their file resources.
-This is form of a distributed file system (e.g.,
\cite{levy90distributedfilesystems}).
+This is form of a distributed file system (see
\cite{levy90distributedfilesystems}).
A modern Peer-to-Peer system is composed of an \emph{application} level
overlay network, i.e.,
the network operates at the application level and forms a logical network
overlay on top of the physical
-network with regard to the ISO-OSI reference model (e.g., \cite{800902}).
Figure \ref{fig:application_level}
+network with regard to the ISO-OSI reference model (see \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 ad hoc, i.e., peers join and leave the system constantly. Thus, this
property
@@ -324,7 +324,7 @@
a large identifier space by the overlay. Globally unique identifiers, known as
\emph{keys},
are also assigned to application-specific data items
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.
+using a cryptographic content hash function (see 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}
@@ -333,7 +333,7 @@
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 mapped uniformly (e.g., using
consistent
+unique key (see 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 responsible for the keys that are assigned by the
overlay.
@@ -369,7 +369,7 @@
Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
\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}),
+data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data
structure (see \cite{226658}),
which requires only a constant number of neighbor peers while providing
$O(\log{n})$ data lookup
efficiency where $n$ is the number of peers in the system. Koorde
\cite{kaashoek03koorde}, a recent modification of Chord, uses de Bruijn graphs
\cite{debruijn46graph} to maintain local routing tables. It requires
@@ -449,9 +449,9 @@
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}).
+difference between identifiers (see Chord \cite{stoica01chord}), number of
+same prefix bits between identifiers (see Pastry \cite{rowston01pastry} and
Tapestry
+\cite{zhao01tapestry}) or Bit-Wise Exclusive Or (XOR) (see 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$
@@ -836,10 +836,10 @@
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}).
+the data lookup process creates too much extra network traffic (see
\cite{yang02improvingsearch}).
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
+more fault tolerant against hostile attacks (see
\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}.
@@ -946,8 +946,8 @@
Anonymity is widely used in a Peer-to-Peer system in which data publication
and non-censorship are important. Forwarding
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 and are able to provide some level of anonymity (e.g.,
\cite{mneturl}).
+to split data into fragments \cite{Shamir1979a}. Mix mailer networks (see
\cite{mixminionurl}) are commonly used in
+distributed systems and are able to provide some level of anonymity (see
\cite{mneturl}).
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
@@ -1250,7 +1250,7 @@
distributions\footnote{Zipf-distribution is a variant of power-law function.
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}).
+where the exponent $a$ is close to unity.} (see \cite{breslau98implications}).
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
@@ -1801,7 +1801,7 @@
tolerance in presence of system flux, non-optimal distance functions in
identifier space,
proximity routing, hostile entities and flexible search
\cite{balakrishanarticle03lookupp2p}.
Additionally, there are few real world experiments with tightly structured
systems
-(e.g., \cite{overneturl, edonkey2kurl}). Therefore, we cannot say explicitly,
how well these
+(see \cite{overneturl, edonkey2kurl}). Therefore, we cannot say explicitly,
how well these
systems would perform in a real Peer-to-Peer environment. However, we believe
that these issues will be
solved in the near future, since much current research is concentraing on
tightly structured
overlays \cite{projectirisurl}.
@@ -1825,7 +1825,7 @@
reasons for this. First, Kademlia's XOR-based distance function is superior
to the distance functions of other systems (see section 2.3.2). Secondly,
Kademlia
is one of the few tightly structured systems that has been deployed in
practical applications
-(e.g., \cite{overneturl, edonkey2kurl, kashmirurl,kato02gisp}), which means
that
+(see \cite{overneturl, edonkey2kurl, kashmirurl,kato02gisp}), which means that
Kademlia's algorithm is simple and easy to implement.
In addition to Kademlia, we propose the use of sloppy hashing
\cite{sloppy:iptps03} which