RainTree Spec Doc Version 1.0.1 Changes

[jeremybeal11]

Overview

These are just notes on what i'm planning on changing in the spec doc. I wanted to outline what I think should be changed before aping into the doc itself.

@Olshansk and CC: @BenVanGithub

Terminology:

"Max possible layers" should be removed

Reason:
- Determining the max layer isn't necessary for the node to begin working. all that is needed is to know where to start which is calculating the top layer and working itself down.

Remove distance base metric(DBM) from the doc

Reason:
- It is confusing to the readers to see that the tree is built via the DBM when really it's it's the Target List Size(TLS) that dictates and changes the structure based on the peers that are constantly being updated.

Example from the doc:
"RainTree requires that the peer list/neighbors list be sorted based on the distance metric."
- Really it's just the logical position on the peer list. so saying DBM confuses the reader so taking it out can help clear up a lot of confusion.

change level to layers:

Reason:
- Reduce confusion for readers since they are used interchangeably

Formula

Remove the node position from the left and right branch formula:

Reason:
- as of now the formula has it as: Node position + targetListSize/3 (rollover if needed) since it doesn't have a numerical value I think it will be best to just remove it and update the formula to be: Left branch = targetListSize/3 (rollover if needed)

Note: should the left branch be the smaller number and the right branch be the higher? if so, then the formula needs to be swapped to be: Left branch = targetListSize/1.5 (rollover if needed) and Right Branch = targetListSize/1.5 (rollover if needed)

Update formula for target list size

Reason:

• After crunching the numbers in multiple scenarios using the formula: (topLayer - currentLayer) x 0.666 x Size of full list the answer kept coming out as 1 which concludes that we can replace the: (topLayer - currentLayer) to just be 1 as shown below:
  • 1 x 0.66 x full list size

Additional Notes:

• need to clarify that layer 0 is when it's alone in the peer list
• never said in the spec that it removes not only the peer chosen but the peers below it from the 66% branch after every demotion process.
• so if a node on the peer list is at a higher level than the origination node who's sending the ACK message, the higher level node will receive it anyway but not act upon that message, but if everyone is on the network is building their own tree and gossiping then why would it matter where peer X is on the list?
• CTA: add a link to the current visual to the Spec seeing RT in action

[Olshansk]

"Max possible layers" should be removed
Reason:

• Determining the max layer isn't necessary for the node to begin working. all that is needed is to know where to start which is calculating the top layer and working itself down.

Rather than saying rmeove max possible layers, I would say that our goal is to consolidate the terms for top layer number, starting layer and max possible layers which is all roundUp(Log3(numNodes)).

If you have a paragraph in the beginning explaining these terms are interchangeable and then specifying "we will use term X moving forward`, that is the best of all worlds.

Remove distance base metric(DBM) from the doc

Agreed.

change level to layers:

We use level in the code, so lets use level evewyere.

You should also make a note that level is the opposite of height in traditional tree structures.

E.g. the root in trees is at height 0, but for us, it is the max level. Ideally, we'll align this, but I believe it is out of scope for now (just improve and iterate).

Remove the node position from the left and right branch formula:

The node position is defined as follows: Assuming all the nodes are geographically sorted based on their addresses, the node's position is its index.

Does that clarify it? If so, I believe we should simply add that.

Left branch = targetListSize/1.5 (rollover if needed) and Right Branch = targetListSize/1.5 (rollover if needed)

Those two look the same to me.

Left should be * 1/3 * and right should be `* 2 / 3*

After crunching the numbers in multiple scenarios using the formula: (topLayer - currentLayer) x 0.666 x Size of full list the answer kept coming out as 1 which concludes that we can replace the: (topLayer - currentLayer) to just be 1 as shown below

What if we have a 10 layer tree and 5 demotions we are at layer 5?

Additional Notes:

I think there's opportunity to just cleanup some of the text and overflow flow of the document.

---

cc @derrandz for context.