[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/storm article.rst
From: |
Benja Fallenstein |
Subject: |
[Gzz-commits] manuscripts/storm article.rst |
Date: |
Sat, 08 Feb 2003 12:38:34 -0500 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Benja Fallenstein <address@hidden> 03/02/08 12:38:34
Modified files:
storm : article.rst
Log message:
Restructure...
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/storm/article.rst.diff?tr1=1.114&tr2=1.115&r1=text&r2=text
Patches:
Index: manuscripts/storm/article.rst
diff -u manuscripts/storm/article.rst:1.114 manuscripts/storm/article.rst:1.115
--- manuscripts/storm/article.rst:1.114 Sat Feb 8 11:56:36 2003
+++ manuscripts/storm/article.rst Sat Feb 8 12:38:34 2003
@@ -37,10 +37,12 @@
However, recent developments in peer-to-peer systems have
rendered this assumption obsolete. Structured overlay networks
-[ref chord, can, tapestry, pastry, kademlia, symphony, viceroy]
-and similar systems [skip graph, swan, peernet] allow *location independent*
-routing based on random identifiers on a global scale. This, we believe,
-may be the most important result of intense peer-to-peer
+[ref chord, can, tapestry, pastry, kademlia, symphony, viceroy,
+skip graph, swan] allow *location independent*
+routing based on random identifiers on a global scale.
+It is now feasible to do a global search for all peers
+that have information about a given identifier.
+This, we believe, may be the most important result of peer-to-peer
research with regard to hypermedia.
In today's computing world, documents move quite freely between
@@ -118,6 +120,8 @@
[ref ht'02 paper]. Additionally, Storm provides services
for versioned data and Xanalogical storage [ref].
+.. [XXX figure of the different layers in Storm]
+
The main contribution of this paper is the Storm design,
a hypermedia system built to make use of the emerging
peer-to-peer search technologies. Additionally, we hope to
@@ -130,9 +134,6 @@
providing a platform for hypermedia-aware applications.
The peer-to-peer functionality is in a very early stage and not
usable yet.
-
-.. [General figure of Storm, i.e. application layer, storm layer,
- netowork layer ? -Hermanni]
.. [Move somewhere else -b]:
[Section 8 ?-) -Hermanni]
@@ -167,6 +168,9 @@
2. Related Work
===============
+2.1. Hypermedia and versioning
+------------------------------
+
The dangling link problem has received a lot of attention
in hypermedia research [refs]. As examples, we examine the ways
in which HTTP, Microcosm [ref], Chimera [ref] and Hyper-G [ref]
@@ -280,12 +284,57 @@
as well as serverless versioning (like e-mail collaboration).
+2.2. Peer-to-peer systems
+-------------------------
+
+During the last few years, there have been a lot of research efforts related
+to Peer-to-Peer (p2p) resource discovery, both in industry and academic world.
+Intensive work in p2p field has yielded two main approaches: broadcasting
+[ref: gnutella1, kazaa, limewire, shareaza] and Distributed Hash Tables (DHT)
+[refs: chord, can, tapestry, pastry, kademlia, symphony, viceroy, skip graphs,
+swan]. Both of these approaches use an application level overlay network.
+However, there are significant differences between broadcasting
+and DHT approach in scalability and efficiency properties. A DHT
+usually provides log-like bounds to *all* internal
+operations [#]_ (footnote about 'stable state' ?), while broadcasting can't
achieve
+either of these.
+
+.. [#] It's not clear whether *all* proposed DHT designs can preserve
+ log-like properties when participants are heterogeneous and they
+ join and leave the system in a dynamic manner.
+
+A distributed hashtable stores key/value pairs.
+In a DHT, both hashtable items and the addresses of peers
+are mapped into a single virtual key space. The form of the key space
+depends on implementation (for example, Chord uses a circle).
+A distance metric (e.g. numerical, XOR) is used to find the peer
+whose position in the key space is 'closest' to the key of a given item.
+This peer is responsible to store the item (so both queries and insertions
+relating to the key are routed to it.) Thus,
+DHT's overlay connectivity graph is structured. On the other hand, the overlay
+connectivity graph of broadcasting approach is formed more or less (depends on
+implementation) in a random manner.
+
+When performing queries, in broadcasting approach, peer sends a query request
to a
+subset of its neighbors and these peers to their subsequent neighbors. The
+process will continue as long as query's time-to-live (TTL) value hasn't been
reached.
+In DHT approach, query request is deterministically routed towards the peer
+which hosts a specific data item. Routing is based on 'hints' (based on
+differences between data item's key and peer's key), which each peer provides
+along the routing path.
+
+Obviously, there are major differences within approaches. For the DHT
approach,
+perhaps the main difference is *what* is self-organized into a
+virtual key space. For instance, in SWAN [ref] and Skip Graph [ref], *data
+items* self-organise into a virtual address space, while in other DHT
+implementations *peers* self-organise in structured form in a virtual space.
+In the broadcasting approach, implementations' differences mostly lie in the
+*structural level* of the overlay network, i.e. super peers and peer clusters.
+
+
3. Block storage
================
-.. [Do we need a figure, which shows the overall structure of block storage
- with pointers, diffs etc ? -Hermanni]
-
In Storm, all data is stored
as *blocks*, byte sequences identified by a SHA-1 cryptographic content hash
[ref SHA-1 and our ht'02 paper].
@@ -309,11 +358,6 @@
design, not report on implementation experience.
We discuss peer-to-peer implementations in Section 7, below.)
-Storm blocks are MIME messages [ref MIME], i.e., objects with
-a header and body as used in Internet mail or HTTP.
-This allows them to carry any metadata that can be carried
-in a MIME header, most importantly a content type.
-
Storing data in immutable blocks may seem strange at first, but
has a number of advantages. First of all, it makes identifiers
self-certifying: no matter where we have downloaded a block from,
@@ -423,6 +467,15 @@
for the experimental Gzz system, a platform explicitly developed
to overcome the limitations of traditional file-based applications.
+
+3.1. Implementation
+-------------------
+
+Storm blocks are MIME messages [ref MIME], i.e., objects with
+a header and body as used in Internet mail or HTTP.
+This allows them to carry any metadata that can be carried
+in a MIME header, most importantly a content type.
+
Collections of Storm blocks are called *pools*. Pools provide
the following interface::
@@ -938,49 +991,8 @@
7. Peer-to-peer implementations
===============================
-During the last few years, there have been a lot of research efforts related
-to Peer-to-Peer (p2p) resource discovery, both in industry and academic world.
-Intensive work in p2p field has yielded two main approaches: broadcasting
-[ref: gnutella1, kazaa, limewire, shareaza] and Distributed Hash Tables (DHT)
-[refs: chord, can, tapestry, pastry, kademlia, symphony, viceroy, skip graphs,
-swan]. Both of these approaches use an application level overlay network.
-However, there are significant differences between broadcasting
-and DHT approach in scalability and efficiency properties. A DHT
-usually provides log-like bounds to *all* internal
-operations [#]_ (footnote about 'stable state' ?), while broadcasting can't
achieve
-either of these.
-
-.. [#] It's not clear whether *all* proposed DHT designs can preserve
- log-like properties when participants are heterogeneous and they
- join and leave the system in a dynamic manner.
-
-A distributed hashtable stores key/value pairs.
-In a DHT, both hashtable items and the addresses of peers
-are mapped into a single virtual key space. The form of the key space
-depends on implementation (for example, Chord uses a circle).
-A distance metric (e.g. numerical, XOR) is used to find the peer
-whose position in the key space is 'closest' to the key of a given item.
-This peer is responsible to store the item (so both queries and insertions
-relating to the key are routed to it.) Thus,
-DHT's overlay connectivity graph is structured. On the other hand, the overlay
-connectivity graph of broadcasting approach is formed more or less (depends on
-implementation) in a random manner.
-
-When performing queries, in broadcasting approach, peer sends a query request
to a
-subset of its neighbors and these peers to their subsequent neighbors. The
-process will continue as long as query's time-to-live (TTL) value hasn't been
reached.
-In DHT approach, query request is deterministically routed towards the peer
-which hosts a specific data item. Routing is based on 'hints' (based on
-differences between data item's key and peer's key), which each peer provides
-along the routing path.
-
-Obviously, there are major differences within approaches. For the DHT
approach,
-perhaps the main difference is *what* is self-organized into a
-virtual key space. For instance, in SWAN [ref] and Skip Graph [ref], *data
-items* self-organise into a virtual address space, while in other DHT
-implementations *peers* self-organise in structured form in a virtual space.
-In the broadcasting approach, implementations' differences mostly lie in the
-*structural level* of the overlay network, i.e. super peers and peer clusters.
+XXX remove this section: p2p should be discussed in the
+relevant sections above (2-6).
.. (Probabilistic access to documents may be ok in e.g. workgroups,
but does not really seem desirable. (At the ht'02 panel, Bouvin
@@ -1004,8 +1016,11 @@
the location through the DHT? This might be related to p2p publishing.
-Review of the use cases: what does storm in each?
--------------------------------------------------
+8. Experience and future directions
+===================================
+
+Review of the use cases: what does storm in each? --
+
(where&how to put this, if use cases are used like this at all?
agreed with benja on irc that we might try this approach - hinting about the
use cases early on and taking a detailed look later, in light of the design.)
@@ -1045,9 +1060,6 @@
7. When B reconnects, can check comments to the Document etc? How does that
happen? Index?
-
-8. Experience and future directions
-===================================
Open issue: Tree hashing, also possibly needed for (OceanStore-like?)
distribution of shares
- [Gzz-commits] manuscripts/storm article.rst, (continued)
- [Gzz-commits] manuscripts/storm article.rst, Toni Alatalo, 2003/02/06
- [Gzz-commits] manuscripts/storm article.rst, Toni Alatalo, 2003/02/07
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/07
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/07
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/07
- [Gzz-commits] manuscripts/storm article.rst, Toni Alatalo, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Toni Alatalo, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Toni Alatalo, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst,
Benja Fallenstein <=
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/08
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/09
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/09
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/09
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/09
- [Gzz-commits] manuscripts/storm article.rst, Benja Fallenstein, 2003/02/09
- [Gzz-commits] manuscripts/storm article.rst, Tuomas J. Lukka, 2003/02/10