Subject: Re: [P2PSIP] Section 9 of RELOAD - Comments

From: Bruce Lowekamp <[email-masked]>
Date: Fri, 10 Jul 2009 14:01:44 -0400

The next revision should address the issues raised in this thread.  A
couple responses inline.

2009/5/11 Bruce Lowekamp <[email-masked]>:
<snip>
>>   "Note that a malicious node can return a success response but not
>>   store the data locally or in the replica set.  Requesting peers that
>>   wish to ensure that the replication actually occurred SHOULD [[Open
>>   Issue:  SHOULD or MAY?]] contact each peer listed in the replicas
>>   field of the Store response and retrieve a copy of the data."
>>
>> The above text is not just relevant for redundant copies of data stored - it is true for even the actual resource-id owner.  Also, in light of not waiting for the replica responses, the STORE response will not contain a list of replicas - so, this needs to be corrected.
>>
>
> Yes, that last text doesn't apply just to replicas.  Will reword.
>
> The responsible peer can, however, include the peerids of the peers on
> which it will place replicas, even if it doesn't wait to confirm their
> responses.
>

I think it's a bit too much to cover that issue in that section, and
the real issue (and defense) is already in the security section.
Instead, the text here now reads:

The sequential replicas used in this overlay algorithm
        protect against peer failure but not against subversive peers.
        Additional replication from the Usage is required to protect
        resources from such attacks, as discussed in
        <xref target="sec-residual-attacks"/>

>> Joining (Section 9.5):
>> ----------------------
>> It is not clear why the join procedure requires all neighbor and finger connections to be established prior to sending the JOIN message itself.  To be functional in the overlay, only the immediate successor relationships must be correctly in place.  The other successors, predecessors and fingers can be established subsequently.  This also doesn't cause nodes to establish unnecessary connections unless the node has successfully joined.  There is also the question of whether a JP is supposed to establish a TLS connection to the BP to send messages through it, which is presently not addressed in the draft.  It seems to me that a more streamlined join process can be defined as follows:
>>
>
> You're right that it's just an optimization to have finger table
> entries, but it's not completely clear to me that adding a new peer
> without finger table entries provides a benefit to the overlay.  I can
> see that being a SHOULD, though.
>

Strictly speaking, the algorithm describing joining is not written in
normative language.  We need a full pass over the entire doc to figure
out what needs to be normative and what doesn't, and this is
definitely one of those places where some of it needs to be normative.
 What I did for now, however, was add a paragraph that says the JP
MUST NOT send an Update placing itself in the overlay until it has
Attached to all of the peers in its neighbor table.  That's the real
MUST requirement, and while I still believe it's better to do it in
the order described currently, it allows other implementations if
there is a motivation for them.

>> Updates (Section 9.7):
>> ----------------------
>> Section 9.7.1. states that every time a connection is lost, the peer should remove it from its neighbor table and find a different peer.  Section 9.7.3. talks about attempting to re-establish connections when a neighbor is detected to be invalid.  These are at odds.  It seems to make sense that the peer would always try to re-establish connections and only remove that neighbor if the connection cannot be re-established.
>>
>
> Working on some new text along these lines for the next revision.
>

The text in 9.7.3 didn't belong there.  I removed that, renamed 9.7.1
to describe handling neighbor failure and added a new section on
handling finger table entry failures.

Along with that, some new text was added that says a peer MAY
re-establish connections, but it's not required to do so.

The sections were also reworded slightly to make the reactive behavior
optional.  They now say "if using reactive recovery..."

>> Finger entries (Section 9.7.3 and elsewhere):
>> ---------------------------------------------
>> The draft requires 16 finger table entries - at first, I took those to mean 16 different resource ids that will be probed per formula.  After reading 9.7.3, it appears that it is talking about 16 different fingers that a node should maintain.  In a small overlay, that's ridiculously large.  The text is also unclear on what happens when the overlay shrinks.  Further, the text states that a peer SHOULD consider the finger table entry valid if it is in the range [n + 2^(numBitsInNodeId-i), n + 1.5 x 2^(numBitsInNodeId-i)]. For small overlays, there may be no entries in this range for every i in [0, 127].
>>
>
> The text was left the way it is in an effort to make it simpler, but I
> think there may be an issue in there where too many MUSTs are
> prohibiting common optimizations.  Definitely need to take a look at
> that.  I think the right answer here is to check the existing text for
> being too pedantic and compare its length & complexity with the
> optimization you describe (which I agree is how this should really be
> implemented).
>
>
>> A node should only need log N fingers to route in OlogN hops.  What we need to specify is an algorithm that uses the same pattern in resource ids to probe - the fingers corresponding to multiple of those will collapse to the same node in a small overlay.  In our implementation, the algorithm works as follows:
>>
>> A node looks at the list of resource-ids corresponding to f=(n+2^i), for all values of i=[0,127].  Let's say that it first probes n+2^0 and obtains a finger of f0.  It checks f0 against the next set of resource-ids to probe and determines the next larger resource-id to probe from the list.  It populates the finger table entries for all other fingers f for which n < f < f0, with f0 as the corresponding finger.  Depending on the number of nodes in the overlay, this should result in approximately logN fingers in the finger table at any time.  Periodic stabilization should adjust the number of fingers automatically.  In fact, the number of fingers a node has should provide a rough estimate (with accuracy in the order of log N) of the size of the overlay.  The current text suggests that the number of fingers should be decided based on the overlay size, which does not seem intuitive or necessary.
>>

OK, so after reading this closer, you're not describing what I
thought.  First, it's a bit confusing since the draft indexes the
finger table entries backwards so that finger[0] is halfway around the
overlay.  That's not how it's done in the original Chord paper, but it
makes it a lot easier to think about variable size finger tables.

Secondly, we need to limit the amount of traffic this produces and
time it takes.  I'm not convinced that walking through the finger
table space is a good idea, even though obviously you'll skip a lot of
potential slots.

To try to improve this section, I've made these changes:
- I realized that the stabilization section said that updates are sent
to all peers in the routing table.  Should have been neighbor table.
Though there
- Suggest a couple approaches to identifying which peers to Probe for
new finger table entries, but leave this mostly tunable.

I completely rewrote much of this section to make it more readable.

Bruce