Add documentation for advanced DiscoveryStrategy use

[qstokkink]

This documentation should include the following.

Configuring Peer discovery:

• A pointer to the basics of DiscoveryStrategies.
• How the RandomWalk works and when to use it.
• How the EdgeWalk works and when to use it.
• How the RandomChurn works and when to use it.
• How to parameterize the walk sizes. The default node degree (20-30) makes sense for most use cases, see for example The Role of Network Topology for Distributed Machine Learning by Giovanni Neglia, Gianmarco Calbi, Don Towsley and Gayane Vardoyan. Add notes on creating a new Network() when mixing with communities of unequal parameters.
• Caution on combining node removal strategies.

Convergence of the connected Peers:

• How the Network class actually works and when peers are added, hooking into the peer discovery basics documentation. EDIT: Out of scope. Add a note on sharing peers between communities.
• How the DiscoveryCommunity consolidates peers and how blocking introduction requests and responses balances peers over communities. EDIT: Out of scope.

[qstokkink]

This should also integrate the everything-you-need-to-know-about-overlay-scaling paper (more formally know as Structure Management for Scalable Overlay Service Construction by Kai Shen).

This is one of the closest papers to our overlay construction.

This paper may also be interesting: 0 to 10k in 20 seconds: Bootstrapping Large-scaleDHT networks by Jae Woo Lee et al.

[qstokkink]

[Failed attempt] I attempted to start by explaining the Network class. However, it became apparent that knowing about walkers and peer discovery is a prerequisite to understand the Network. Essentially, this old Dispersy documentation needs to be rehashed to fit IPv8 in order to understand the Network: https://dispersy.readthedocs.io/en/devel/system_overview.html#peer-selection

[qstokkink]

Looking at this again: the basics of #977 should really be written before we jump into the advanced stuff. In essence, this documentation is really an extension of #977 for enthusiasts. I'll put this on hold until that is done.

[qstokkink]

With #1027 merged, this can be taken off "on hold".

[qstokkink]

Ok, text containing heavy statistical analysis and code is not going to cut it to build intuition for new readers. Having .gif images that show how networks evolve is probably going to be much easier to digest. A movie/gif says more than a 1000 words after all.

For example, how long does it take for information to go from node 1 to node 2 in an (a) line topology, (b) ring topology or (c) random regular graph:

[Of course, the image would have to contain more nodes as the random regular graph looks a bit like a fully connected graph now.]

Another example, seeing what happens when you set your Community max_peers equal to your walk's target_peers:

This should scream: "Looks like a line; not good!"

[qstokkink]

There is of course an alternative to explaining this ourselves and that is to just point at existing books on this topic. For example, slide 20 of the chapter 2 slides for "Introduction to Parallel Computing" by Grama, Gupta, Karypis and Kumar perfectly lists the diameters of various network constructions. Offering free courses on parallel processing and distributed systems might be a bit too much for our documentation's scope..

[drew2a]

FYI: the link slide 20 of the chapter 2 slides for "Introduction to Parallel Computing" by Grama, Gupta, Karypis and Kumar is broken

[qstokkink]

Some backup links for network diameters:

• Page 78: https://books.google.nl/books?id=iNQLBwAAQBAJ&lpg=PA85&dq=Introduction%20to%20Parallel%20Computing%20diameter&pg=PA78#v=onepage&q=Introduction%20to%20Parallel%20Computing%20diameter&f=false

• Page 44: https://books.google.nl/books?id=B3jR2EhdZaMC&lpg=PA43&dq=Introduction%20to%20Parallel%20Computing%20diameter&pg=PA44#v=onepage&q=Introduction%20to%20Parallel%20Computing%20diameter&f=false

I would've loved to link to Wikipedia for further reading, but their explanation of network diameter is.. a bit short, to say the least: https://en.wikipedia.org/wiki/Network_science#Diameter_of_a_network 🤔 Wikipedia has a lot of text on network science, but very little tangible information to really explain the spread of data in different types of networks.

[qstokkink]

[Random rambling/brain dump (not sure how much of this should go into the docs)]

The core issue of creating network topologies for open-entry systems and trustless communication lies in ensuring a lack of network partitioning. The +-20 years of buzzwords like DHTs, publish-subscribe, CC(O)N, Semantic Overlays, super peers, etc., but also targets like mixing time or choosing node degrees, all have to do with methods of optimization for the latency of information retrieval. These optimizations can (and should) be superimposed over the core networking framework (like IPv8) that solves the core problem of guaranteeing a lack of network partitions. None of the buzzword solutions serve to deliver messages to nodes in a partitioned network.

Ensuring that all (honest) nodes in a system are connected goes back to the 1950's. Roughly starting with---though this is not the only work---"On Random Graphs" (1959) Erdős and Rényi start to address connectivity for random graphs. In the following decades, the mathematical bounds on information retrieval would be derived. A quick potpourri of works: "Stochastic rumours" (1965) by Daley and Kendall, "Random exchanges of information" (1979) by Boyd and Steele and "On spreading a rumor" (1987) by Pittel. Essentially, spreading information---and by extension also retrieving it---takes time in the order of the logarithm of the network size modulated by the maximum latency in the system. Results for Bitcoin like "after 40 seconds there still are 5% of nodes that have not yet received the block", from "Information propagation in the bitcoin network" (2013) by Decker and Wattenhofer, should come as no surprise even though Bitcoin nodes typically have "relatively huge" node degrees.

Managing complex structures to optimize information retrieval works, but don't forget randomness. I feel that randomness goes wildly underappreciated as I see many proposals to create structured p2p networks. For example, in "Structure Management for Scalable Overlay Service Construction" (2004) by Shen Figure 11 "Impact of node degree range" you can see that structured networks always outperform randomness, but become less consequential as the node degree increases. At the same time, the more efficient the structure imposed on the connections, the more complicated its management becomes (not just for the data structure itself, but also including incentive alignment). Managing a DHT's tree data structure is difficult, but managing a Hypercube structure requires Walt Disney-levels of black magic and optimism. Depending on randomness isn't all that bad if your node degrees are big enough.

Any non-binary bias in forming peer connections is a terrible idea. Ostracizing attackers on the network layer is a good idea, but balancing connection attempts based on reputation completely destabilizes your network and converges to a superpeer overlay very quickly. Once you have a superpeer overlay, your network becomes very prone to partitioning, given that connections between the cliques that form around superpeers will be sparse. Nodes around a superpeer will build reputation with other nodes around the superpeer and self-partition the clique from the remainder of the network through the lack of information from others.

Bootstrap/rendezvous nodes govern the network partitioning. If two groups of nodes have unique bootstrap nodes, they will never connect to each other. Having a large number of methods for bootstrapping is wholly inconsequential if there is no overlap between the use of these methods. Bootstrapping periodically is also vital to the health of a network overlay, given node churn. In a twist of hilarious irony, connectable bootstrap nodes are necessarily centrally governed, which essentially means that true decentralized networks will never exist unless you can replace these nodes with broadcast/multicast over WAN (blocked by essentially every ISP). IPv8 does offer bootstrap broadcasts that work over LAN.

[synctext]

Fitting 2 years of distributed systems master courses into a tutorial is probably not what we want. Simple rules: Don't invent your own crypto, don't build your own overlay, and eat your daily vegetables. We used to have the AllChannel experiment with 1000 emulated peers, worked like a charm to detect deeply hidden overlay bias bugs. Best scientific solution is to have a nightly test and resurrect AllChannels peer discovery bias detector experiment.

Would recommend the use a simple example as the opening argument. _Creating network topologies is difficult business. When you are connected to 25 others peers there might still probability of 1 in a million that you connectivity completely breaks in a given day. However, if you have a network of 1 million peers, it might break into or more partitions are you have a complete system meltdown._

On a general level, we have easily 9 comments on a documentation issue. Somehow we have a collective blockage to actually add something to the documentation. Generating it from source code headers is probably not the solution, but its a strange pattern with multiple developers.

[qstokkink]

Since we no longer have an AllChannels, for a nightly test I'd recommend running a DiscoveryCommunity and two other custom communities. If there is "no bias" (there is always bias because time and resampling are involved) all of the peer pools could be checked at the end of the experiment to see if either of the two communities is overly present (on average for all peers) in the DiscoveryCommunity peer pool. This is more of a separate issue to solve in Gumby though.

On a side note: normally documentation doesn't have this much discussion (at least in IPv8). For this particular issue, I'm just dumping information to try and find a way to convince people of the "best practices" (i.e., "how to not cause complete system meltdown") in the documentation without plowing through 2 years of master courses worth of content.

Perhaps trying to convince people is the wrong approach and this documentation should just be a list of "do's and don'ts". If you don't get it: "just get a Master's degree". Then again, some of these insights are not even taught in Master's programmes anymore. If we give too little background information, people won't be able to understand and won't be able to contribute to IPv8 anymore 😱.

[synctext]

Great point! We need to resurrect the test that detect systems meltdowns, before they happen. (differs from your DiscoveryCommunity proposal. Essential trick: with an unhealthy overlay you degrade P2P message synchronisation. If you every managed to debug your overlay, you see regression upon introducing a bias or fault) Future ToDo, after 2022 summer: resurrect AllChannel experiment. The AllChannels content dissemination community test has "unreasonable effectiveness". By plotting 1000 lines into a single plot a healthy experiment or fault shows up. Many bugs have been shows to exist using this approach. Its basically an end-to-end performance analysis, peer neighbourhood bias, and unhealthy overlay in general. AllChannels used 25 figures to depict the code health. One expert glace is sufficient to detect some new introduced bug.

Read the entire scientific test here: https://dl.ifip.org/db/conf/networking/networking2013/ZeilemakerCP13.pdf

[qstokkink]

I absolutely agree that looking at message synchronization is useful, but it does not capture network fragility/robustness (which is also one of the main points of this documentation issue). For example, the graph you just posted might have been the result of the following star network (credit to the market experiments);

Suppose the center peer (1) either left the network or became malicious: this would cause system meltdown. You would've never known if you only looked at the message synchronization graph. Therefore, I wouldn't depend solely on message synchronization.

This is a very real and insidious issue. We had a similar (albeit a bit more complex) situation when we added reciprocity-based peer discovery:

Post-mortem2: load-balancing needs to be maintained when doing non-random walks! Trust introduces a strong bias. Destructive and leads to overloading of highly-trusted nodes in a power-law setting or complete neglect of low-trust nodes.

[synctext]

you're right! One of the 25 AllChannel figures was "load" for each peer. With again 1000 lines it's easy to spot outliers for both extremes.

[xoriole]

Some graphs of Experiment_AllChannel+Channelcommunity_next from archive of 2016_09_24

[qstokkink]

I see that this issue is moving away from IPv8 documentation and moving into Gumby experiment design. There should be a separate issue for the Gumby experiment discussion in the Gumby repository instead (+1 to whomever creates that issue, edit: claimed by @devos50).

[devos50]

@qstokkink I made one: https://github.com/Tribler/gumby/issues/513 👍

[qstokkink]

In order to finally get this documentation out, I placed the nitty gritty details of peer convergence out of scope for this issue (updated O.P.).

Memo (mostly for myself 😃): WIP branch here https://github.com/qstokkink/py-ipv8/tree/add_adv_discstrategy