Tough love: 2. Routing

These questions are addressed at all MaidSafe developers, and community members. I will count myself among those community members and also look to find the answers, but let’s start the discussion somewhere.

What is the current definition of a close group and can we point to the implementation details too?

As a starting note, during my time reviewing and rewriting routing I worked to formalise first this definition and I found that the definition David used was incorrect, and hence I formalised a correction to it where there is the definition of a close group and an effective close group needed to correctly reason about the SAFE network proposal.

3 Likes

Zero content OP = spam.

What is the question, what is the contribution… just reads like OP with an ego.

2 Likes

I think somebody is looking for a ban desperately

There’s a question in this one:

7 Likes

hmmm - no …everybody is allowed to ask questions and asking for a ban is just ridiculous @Chuki

i don’t know if it is important to answer this question right now - but clearly there is a question that can be addressed and i am curious if there is an answer i get

10 Likes

That is a bit misleading, the code in routing was wrong (you can do git history to see where it was wrong and if you wish see who wrote it, you may remember :wink: ), it did not work and routing had to be rewritten, no need to harp on though, we fixed that as we will fix many bugs. The dns on our docs is updating, but if you wish to read the definitions please run cargo doc -open in a clone of kademlia_routing_table.

I have a copy paste here, which may help you, since you asked a bit of a question here.


This crate uses the Kademlia mechanism for routing messages in a peer-to-peer network, and generalises it to provide redundancy in every step: for senders, messages in transit and receivers. It contains the routing table and the functionality to decide via which of its entries to route a message, but not the networking functionality itself.

It also provides methods to decide which other nodes to connect to, depending on a parameter bucket_size (see below).

Addresses and distance functions

Nodes in the network are addressed with a Xorable type, an unsigned integer with B bits. The XOR distance between two nodes with addresses x and y is x ^ y. This distance function has the property that no two points ever have the same distance from a given point, i. e. if x ^ y == x ^ z, then y == z. This property allows us to define the k-*close group* of an address as the k closest nodes to that address, guaranteeing that the close group will always have exactly k members (unless, of course, the whole network has less than k nodes).

The routing table is associated with a node with some name x, and manages a number of contacts to other nodes, sorting them into up to B buckets, depending on their XOR distance from x:

If 2B > x ^ y >= 2B - 1, then y is in bucket 0.
If 2B - 1 > x ^ y >= 2B - 2, then y is in bucket 1.
If 2B - 2 > x ^ y >= 2B - 3, then y is in bucket 2.
...
If 2 > x ^ y >= 1, then y is in bucket B - 1.
Equivalently, y is in bucket n if the longest common prefix of x and y has length n, i. e. the first binary digit in which x and y disagree is the (n + 1)-th one. We call the length of the remainder, without the common prefix, the bucket distance of x and y. Hence x and y have bucket distance B - n if and only if y belongs in bucket number n.

The bucket distance is coarser than the XOR distance: Whenever the bucket distance from y to x is less than the bucket distance from z to x, then y ^ x < z ^ x. But not vice-versa: Often y ^ x < z ^ x, even if the bucket distances are equal. The XOR distance ranges from 0 to 2B (exclusive), while the bucket distance ranges from 0 to B (inclusive).

Guarantees

The routing table provides functions to decide, for a message with a given destination, which nodes in the table to pass the message on to, so that it is guaranteed that:

If the destination is the address of a node, the message will reach that node after at most B - 1 hops.
Otherwise, if the destination is a k-close group with k <= bucket_size, the message will reach every member of the k-close group of the destination address, i. e. all k nodes in the network that are XOR-closest to that address, and each node knows whether it belongs to that group.
Each node in a given address' close group is connected to each other node in that group. In particular, every node is connected to its own close group.
The number of total hop messages created for each message is at most B.
For each node there are at most B * bucket_size other nodes in the network that would accept a connection, at any point in time. All other nodes do not need to disclose their IP address.
There are bucket_size different paths along which a message can be sent, to provide redundancy.
However, to be able to make these guarantees, the routing table must be filled with sufficiently many contacts. Specifically, the following invariant must be ensured:

Whenever a bucket n has fewer than bucket_size entries, it contains all nodes in the network with bucket distance B - n.

The user of this crate therefore needs to make sure that whenever a node joins or leaves, all affected nodes in the network update their routing tables accordingly.

Resilience against malfunctioning nodes

The sender may choose to send a message via up to bucket_size distinct paths to provide redundancy against malfunctioning hop nodes. These paths are likely, but not guaranteed, to be disjoint.

The concept of close groups exists to provide resilience even against failures of the source or destination itself: If every member of a group tries to send the same message, it will arrive even if some members fail. And if a message is sent to a whole group, it will arrive in most, even if some of them malfunction.

Close groups can thus be used as inherently redundant authorities in the network that messages can be sent to and received from, using a consensus algorithm: A message from a group authority is considered to be legitimate, if a majority of group members have sent a message with the same content.

As for code for the routing table specifically that is here https://github.com/maidsafe/kademlia_routing_table

Routing itself is here

I hope this helps

21 Likes

open several threads looking for a fight with irvine maybe it is not reason for a ban - you are right - BUT it is a reason to put an eye on this boy and his clearly not good intentions

2 Likes

yeah - he tried to get as much attention as possible (after having been pretty silent for so long :-\ ) … not the kindest way to do it

i don’t like if someone questions my favorite project too - but if there would come up a reasonable question/problem that would prove the concept can’t work like this - the team would be able to alter the concept or we wouldn’t waste our time following a dream that can by definition never come true :wink:

(thats why i’m pro questions - if they Can (!) be answered and it does make sense to answer them at this stage of development)

3 Likes

To be useful, it needs to be more than a simple request for definition… and titling as “Tough Love” is just silly.

2 Likes

Thanks @dirvine, this is a very good start. We indeed during Rust 1-5 not touched the routing table, so very interesting to learn that the routing table has split off in a repository and has been rewritten.

I will need time to review the new routing table code, so in the interest of progress I am open to a discussion on what has changed as I need to catch.

Maybe someone from the community can jump in here to and help me through the new changes, as to not put all the weight on David!

5 Likes

yeah but questions like “how do i get this running” make more sense …?
or “is safecoin divisible?”

and why the judging with the title …? for this becoming a useful discussion we have to isolate the questions / problematic points and then find a reasonable answer … not making it personal and derailing the topic …

@benjaminbollen yeah … not me … sorry … i’m just furniture in this forum … don’t know details …
[and to be honest i’d prefer david and the rest having the time to prepare the next testnet or more before you get your questions answered …? … ]

1 Like

http://www.zerohedge.com/news/2016-06-03/european-union-declares-war-internet-free-speech

Can we stop with this high school crap and get on with more important things? Like releasing a product that saves us from this Orwellian nightmare? Seriously… TPTB are accelerating and we need this product like yesterday! Apologize for the hyperbole.

7 Likes

Creating a time soak is not constructive… this is not a noob. This appears to be someone who wants others to do the work for him… and then take all the credit for knowing the errors. zzz.

3 Likes

The world is filled with people of both good and ill intention, sadly both converge at times like these. Dont let curiosity provide a platform for the latter.
Good intention is seldom conveyed in such a negative manner.

3 Likes

For any logical argument to work we first need to align ourselves on a common definition.

1 Like

What is the problem, exactly?

4 Likes

@benjaminbollen do you believe that close groups alone are not sufficient, and that an “effective close group” is needed in addition to a close group; or are these “effective close groups” a replacement for close groups?

3 Likes

We are not in a rush here. I have said I have a full time work, and David and the core developers have a more than fulltime work, and many of our community members have a full time occupation.

I dont need all answers right here and right now. I don’t claim that I have any of the answers. What I do want is for starting open discussions at a calm steady pace, progressing the thinking in this project and in this field.

Im not expecting love for this initiative, but I do hope that I can assume people will trust me that despite the history I still keep our collective success first.

Hello, Ben.

I’ve a fair bit of respect for you, but your statements above really tell the tale, along with the other posts. You are expressing that you are really ignorant of what’s going on, but started in with a chip on your shoulder. Not a good start if wishing to truly participate.

Starting with a request from those in the community to help get you up to speed would have been an honorable approach. Doing so after making “Tough Love” judgement-type posts and finding yourself shut down does not make you seem trustworthy at this pass.

I really have no clear idea of what happened between you and MaidSafe. But we’re here now, and wish to move forward.

Bringing critical perspective to the code, etc., is not a bad thing, welcome, I’m sure. But your first step with “compassionate criticism” which is not in sync with the scene leaves me feeling cautions about your intentions.

15 Likes

The need for an “effective close group” came from wanting to formalise that a “close group” is well-defined as a logical concept. In this effort I found I could only do this for an additional extended concept - which I called, but whats in a name - and “effective close group”. The reason for this is in that the logic needs to be constructed from a local perspective (every node acts on its own perception of the network and there is no global consensus mechanism; the big contrast to blockchains)

So a close group is defined from the perspective of a given node; given his routing table it calculates what the close group of a given destination address is. However, again there is no direct consensus mechanism or knowledge of the full (or even local address space) - which btw is the exquisite beauty of the SAFE network proposal; what makes it stand out from all others; because it allows for efficient scaling.

So from that it follows, that a node far away will have likely a less accurate perception of what the close group is, as compared to an ideal, global knowledge of the close group - again nodes in the network only have a local perspective and no access to the global ideal is available to a node.

And so firstly the “close group” can be then defined as “the close group of a node as seen by itself”;

Secondly, a piece of data living in this address space does not maintain a routing table, so we can’t define “the close group of a piece data as seen by that piece of data”, for obvious reasons.

What we can define for both a node and a piece of data equally is the “effective close group”, as the nodes that are reached when trying to swarm to a given address and those nodes that will deem themselves part of that effective close group.

I base the above “english” on my recollections of my efforts to formalise, and in my opinion successful proof (although deliberately uncompleted), of the swarming algorithm employed by the routing layer. So I could proof the validity of swarming (although that does not speak yet of efficiency, but optimisations should come later). It first needs to be understood under which conditions swarming works, and as such I formalised those assumptions.

I attach that draft where I made that attempt again here. I posted it to the forum last summer too.

draft formalisation of swarming with need for effective close group

1 Like