[Gzz-commits] manuscripts/storm article.rst

[Benja Fallenstein]

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