[Gzz] Available overlays PEG

[Benja Fallenstein]

> ==========================================================================
> PEG available_overlays--hemppah: Available overlays
> ==========================================================================
>
> :Authors:  Hermanni Hyytiälä
> :Date-Created: 2003-06-18
> :Last-Modified: $Date: 2003/07/31 12:56:11 $
> :Revision: $Revision: 1.39 $
> :Status:   Current
> :Scope:    Major

(I agree that the scope of this PEG is major, but it doesn't actually 
fit the definition of "Major:" it's not true that "most code needs a 
touchup." ``pegboard_format--tjl`` should probably be changed to say 
something like, "A fundamental change" or something.)

> :Type:     Architecture

I don't agree with this: While changing the used overlay would be a big 
change, it's still an implementation change, not an architectural change.

> :Stakeholders: tjl, benja
> .. Affect-PEGs:

Please fix the syntax here (line missing, see the compiled version for 
error msg). Actually, I think "current" PEGs shouldn't have any 
commented out fields like this-- the ".. Affect-PEGs" field should 
simply be removed.

> The purpose of this PEG document is to give a short overview of existing 
> structured
> P2P overlays which have an open source implementation. 

Not true: At the end, you specify that we shall change to Tapestry. You 
should say so at this point, already.

If you intend this PEG to make a no decision, only a recommendation, 
then you could e.g. say,

    This PEG gives an overview of existing P2P overlays which have
    an open source implementation. Based on the overview, it
    recommends the Tapestry_ overlay to be used in Storm.

(link to review of Tapestry)

> The reason for creating this PEG document is that the current implementation 
> of GISP [5]_ seems to have (too) many obvious security exploits. Therefore we need 
> to examine other available structured overlays which have an open source 
> implementation in hope for finding a more mature P2P platform. 

s/ in hope for finding/in the hope to find/

> The list of implemented overlays is as of July 2003.
>
> Issues
> ======
>
> None.
>
> Terminology
> ===========
>
> This section briefly covers the terminology used in this document. 
>
> Abstractions
>     The following text for the abstraction definitions is taken from 
>     `Towards a Common API for Structured P2P Overlays`_ by Frank Dabek et al.
>
> .. _DHT: 
>
>     DHT
>         The DHT abstraction provides the same functionality as a 
>         traditional hashtable, by storing the mapping between a
>         key and a value. This interface implements a simple store
>         and retrieve functionality, where the value is always stored
>         at the live overlay node(s) to which the key is mapped by
>         the KBR layer. Values can be objects of any type. For ex-ample, the DHT 
>         implemented as part of the DHash inter-face in CFS stores 
>         and retrieves single disk blocks by their content-hashed keys.

s/ex-ample/example/
s/inter-face/interface/

> .. _DOLR:
>
>     DOLR
>         The DOLR abstraction provides a decentralized direc-tory

s/direc-tory/directory/

>         service. Each object replica (or endpoint) has an
>         objectID and may be placed anywhere within the system.
>         Applications announce the presence of endpoints by pub-lishing

s/pub-lishing/publishing/

>         their locations. A client message addressed with
>         a particular objectID will be delivered to a nearby end-point

s/end-point/endpoint/, I think.

>         with this name. Note that the underlying distributed
>         directory can be implemented by annotating trees associ-ated
>         with each objectID; other implementations are pos-sible.

assoc-iated, pos-sible.

>         One might ask why DOLR is not implemented on
>         top of a DHT, with data pointers stored as values; this is
>         not possible because a DOLR routes messages to the near-est
>         available endpoint providing a locality property not
>         supported by DHTs. An integral part of this process is the
>         maintenance of the distributed directory during changes
>         to the underlying nodes or links.

near-est

It's not clear to me from the above if and how a DHT can be implemented 
on top of a DOLR. Since we need a DHT for indexing, this is important. 
(For downloading blocks, we can use DOLR.)

> Redundancy
>     What techniques are used for redundancy     
>
> Fault tolerance against hostile nodes
>     What techniques are used against hostile nodes    

These aren't useful definitions. Either provide a definition that's not 
only the words reordered, or don't provide any definition at all :-)

As a reader, I don't like to read lots of definitions before the actual 
content of the document starts, so define only what you really think has 
to be defined :-)

What do you *mean* by "redundancy," though? Maybe you should use "Fault 
tolerance against node failures?"

> Implemented overlays
> ====================
>
> In this section we list the structured P2P overlays which have an open source
> implementation. Please notice

s/notice/note/

> that features described for each implementation 
> are deliberately kept as short as possible.

"that the description of each implementation's features is"

> For more depth information about the 
> overlays we suggest reading the original publications.

s/depth/in-depth/

> Chord [1]_
> ----------

I'd prefer if, instead of using a footnote, you simply gave the homepage 
of a project as one point below, i.e., "Abstraction, home page, 
redundancy..."

> Abstraction
>     DHT_/DOLR_
>
> Redundancy
>     Replication, backup links.

What is "backup links?"

> Fault tolerance against hostile nodes
>     (undefined)

What do you mean by "undefined"???

> Activity of development

It would be good if you put language and license before this, because 
they're most important in evaluating the applicability of an overlay.

> Developer
>     MIT (research community)

What do you mean by "(research community)"? You use this again, below, 
but you never explain what you mean by it.

> License
>     BSD-like

`Advertisement clause`__ or not?

__ http://www.gnu.org/licenses/license-list.html#OriginalBSD

> Other notes
>     No support for network locality- do not take network latencies into account
>     when building neighbor links.

s/-/--/
s/do not/does not/

How does it implement DOLR if it doesn't support locality?

> Tapestry [2]_
> --------------
>
> Abstraction
>     DOLR_
>
> Redundancy
>     According to `Tapestry: A Resilient Global-scale Overlay for Service
>     Deployment`_:
>
>         Tapestry is highly resilient under dynamic conditions,
>         providing a near optimal success rate for requests
>         under high churn rates, and quicly recovering from
>         massive membership events in under a minute.

This doesn't list *techniques* (as per your defn above), it says how 
useful the developers believe their techniques to be. You should 
probably change the defn (or leave it out).

s/quicly/quickly/, or add "[sic]"
>     
>     According to the Tapestry [2]_ website:
>
>         Tapestry offers fault-resilient mechanisms for both object 
>         location and point to point message delivery.  For object location, 
>         Tapestry generates a small number of deterministic and independent 
>         GUIDs for each object.  An object server publishes an object's 
>         availability on all of its GUIDs, and a client issues Tapestry locate 
>         requests for all of the object GUIDs in parallel.  This greatly 
>         increases availability under fault conditions, while improving 
>         general performance and reducing performance variability.  For point 
>         to point message delivery, Tapestry provides pre-calculated backup 
>         routes at each overlay hop.  UDP soft-state beacons measure up-to-date 
>         link conditions. Tapestry uses such information and simple fault-avoidance 
>         protocols to route messages around failures, providing successful 
>         delivery with high probability if a path between the endpoints exists.

I think the stuff about message delivery doesn't apply to us, so you 
could edit that out.

> Fault tolerance against hostile nodes
>     * PKI is used while creating node identifiers
>     * MACs are used to maintain integrity of overlay traffic
>     * Monitoring system for maintaining neighbor links

Explain how this helps against hostile nodes, which is the most 
important part of this PEG after all.

> Activity of development
...
>      According to the Tapestry [2]_ website, Tapestry Version 2.0 contains the 
>      following new functionality::

How is this relevant for "Activity of development"?

> Language
>     Java (Sun JDK 1.3 or a compatible Java Development and Runtime environment).
>     The Java interface libraries for the BerkeleyDB database 

How about Kaffe?

Can Tapestry run without JNI?

> Other notes
>     Support for network locality when building neighbor links.
>
>     Why Oceanstore_ uses Tapestry [2]_? 

Don't pose rethorical questions like this-- it doesn't look good. Say 
"Reasons why Oceanstorage uses Tapestry:" instead.

>     See http://www.oceanstore.org/info/whytapestry.html 

This page is entitled, "Why Do We Need Locality?", though, not "Why do 
we use Tapestry."

> Kademlia [3]_
> -------------
>
> Abstraction
>     DHT_
>
> Redundancy
>     No simulation or test results published (not even in the original 
> publication)

Replace ")" by ")."

>     In *theory*, however, the "free-choice" feature
>     gives peers freedom to adapt different conditions. However, the
>     author of SharkyPy says:

Link "SharkyPy" to the product, and if possible, link "says" to the 
source of the quote.

>         Kademlia has (in my taste, that's why I decided to drop it) a bad
>         hole which makes it's use in remote querying for packets pretty useless:

Don't  indent first line of blockquote.

>         When you have key->value mappings, which have an equal key, in even in
>         semi-large networks it gets very unprobable that you get all mappings,
>         the more hosts there are, the less probable it is, and the more mappings
>         there are, the less probable it is too. I've tried to remedy this in a
>         later implementation, at the cost of lookup speed, but have never
>         managed to get all entries when the network had over 100 nodes. (the
>         later implementation is based on my own server-framework and uses no
>         threads, btw.) This made it unusable for me, as basically I basically
>         had to change the lookup-algorithm to query all nodes (back to gnutella,
>         then...), to get all answers. And that's what is important in the
>         network I designed it for.

Wow. That's pretty much a killer for us.

Any response from the authors?

> Activity of development
>     Java development discontinued, C++ version
>     is under development.

Not released, right?

> GISP [5]_
> ---------
>
> Abstraction
>     DHT_/DOLR_
>
> Redundancy
>     Chord [1]_-like (since GISP uses similar routing tables as Chord)

If that only boils down to saying, "Replication, backup links," then I 
think replicating that here is shorter than saying it's Chord-like ;-)

> Fault tolerance against hostile nodes
>     Based on our own initial experiments: the fault tolerance
>     is relatively weak - no specific techiques used.

Uh, which experiments?

> Other notes
>     Uses 10x more cache as Chord [1]_ for routing table.

Why does it? Source?

> MLDonkey [8]_
> -------------
>
> Abstraction
>     DHT_ (Kademlia [3]_ algorithm)
>
>     (MLDonkey [8]_ is compatible with Overnet_, and Overnet claims that it does 
>     Kademlia [3]_ and multisource downloading)

As you discuss the two Pastry impls together, you should probably do the 
same with Overnet.

> Redundancy
>     Not known (we can imagine that redundancy is relatively high since MLDonkey
>     is widely deplyed)
>
> Fault tolerance against hostile nodes
>     Not known (we can imagine that fault tolerance is relatively high since 
> MLDonkey
>     is widely deplyed)

I don't think that we can just assume that...

BTW, the author of Overnet was very unhappy about MLDonkey deploying the 
protocol because they thought it slowed down the network or something, 
and they called MLDonkey machines "rogue peers." So such "rogue peers" 
can apparently cause problems, even if they are programmed by a benign 
(but ignorant) programmer.


> Language
>     Objective-Caml (a compiler, not a interpreter)

s/a compiler, not a interpreter/compiled, not interpreted/

Objectiv-Caml is a language, not a compiler.

Other notes: It would be good to know how hard it would be to use 
MLDonkey's DHT routing mechanism separately (ask programmers?).

> SharkyPy [9]_
> -------------
>         This implementation is heavily based on threads, which makes it
>         pretty resource-intensive on the computer it is running on. I never

Don't indent first line, please.

> Changes
> =======
>
> While reviewing the different features of open source implementations of 
> structured P2P overlays we can conclude that Tapestry seems to be the most
> mature currently available. Specifically, other implementations
> lack of features w.r.t. redundancy and fault tolerance that the Tapestry
> implementation currently supports. Other reasons for choosing Tapestry in order of 
> importance:
>
> - The license
> - The activity of development
> - The implementation language
>
> As a result, we recommend using Tapestry's open source implementation with 
> Storm.
> For detailed changes and information about using Tapestry with Storm, please
> see the `storm_with_tapestry--hemppah` PEG document.

s/with Storm/for use in Storm/. Use double backticks for the PEG name.

The meaning of "For detailed changes please see" isn't clear to me. Does 
acceptance of this PEG mean that storm_with_tapestry--hemppah is also 
accepted? Maybe say, "For a detailed list of changes necessary to use 
Tapestry in Storm, see..."

``storm_with_tapestry--hemppah`` isn't an accepted PEG; maybe should 
refer to it as "pending PEG" or something...

Link the PEG, don't just give its name.

> .. _`Towards a Common API for Structured P2P Overlays`: 
> http://www.cs.berkeley.edu/~ravenben/publications/pdf/apis.pdf
> .. _`Tapestry: A Resilient Global-scale Overlay for Service Deployment`: 
> http://www.cs.berkeley.edu/~ravenben/publications/pdf/tapestry_jsac.pdf

You don't need the back-ticks here.

For reading as text, it would be good to have the link URIs closer to 
the actual links in the document.

- Benja