Data propagation with unstructured P2P

[2022-05-18] #p5Js #p2p

Consider a P2P network with, for any instant T, each node are connected to perhaps 25% of the nodes (to reducing the global bandwidth).

Also consider that the network is open. A new node can spawn in the network, and connect itself to 25% of the nodes (ex: in a geographic zone). Any nodes at T can create a new data to be propagated through network.

Note: That kind of network can be any P2P model or any nodes configuration. We can imagine a multitude of cell-phone sending notifications to each others with bluetooth connections. Or a client based online video game that use a kind of consensus, with a weak leader and weak node connections. Or a blockchain network with poor connectivity between nodes.

How to propagate the information through the network?

Straightforward

The simplest tactic is sending the data that we received to every neighbors once. And send the data that we produce to every neighbor once.

The “algorithm” is very basic but works well with no surprise. But looking at the workflow of an information. We understand that a node will receive the information from a kind of random amount of distant nodes. And more the network grow up, more he will receive a lot of useless batches of data.

In the worst case the data is really taking a lot of place in our bandwidth 😨

Solutions of accumulated evidences

The solution cut the transfers of the data in two part, the first discussion between the nodes contains only a hash of the data. And then, the distant node choose by itself if getting the full buffer or not.

Sending the full body with the information is taking time and bandwidth because of the size of that one. In fact, the straightforward tactic of propagation is good enough for small data, but not for a large buffer.

So nodes are receiving hash/ids of the data and increment locally the number of times a node say “Hi! I get that data, by the way”.

// On receive a hash key, increment a counter in the `this.known`
// structure ('known' because we heard about that data)
insertOpKey(key) {
    // return if we already have the full data locally
    if (this.owned.findIndex(e => e == key) > - 1) return;

    const index = this.known.findIndex(e => e[0] === key);
    index === -1
        ? this.known.push([key, 0]) // create a counter
        : this.known[index][1]++; // increment the counter
    this.known.sort((a, b) => a[1] > b[1])
},

So, the last sort is very useful for the second and last part of the algorithm! It gave me that strategical order.

The table this.known looks like that:

Actually, more we heard about a data, more it will be easy to find it. But we could also ask to the latest senders of the ids directly when we want to get the data!

peek() {
    if (this.known.length === 0) return;

    const i = this.known.pop();
    // the following two lines must be replaced with a logic
    // that "find" the data in your real network. Here I just
    // simulate that :-)

    // if (this.owned.contains(i[0])) return;
    this.setStatus(i[0]);
    this.owned.push(i[0]);
},

Thank’s!

Thank you for reading! If you appreciate that little P2P introduction. You can find the full code of the preview on my blog repository in the following paths:

.
├── assets
│   ├── js
│   │   ├── constants.js # some constants for the mocked network configuration
│   │   ├── graphical.js # Drawing tools
│   │   ├── node.js      # Nodes behaviors
│   │   └── sketch.js    # p5js configuration and main loop