[UX/UI] As a Developer, I want to understand network topology, so I can debug Kademlia, Gossipsub

[lukasimrich]

Overview

This task closely relates to Libp2p, and its implementation Goal

• Lean libp2p implementation - only essential parts that are relevenat for MINA
• State machine/Testing framework support
• OCaml node compatibility

Front End / UI

• Understand whether the implementation works as intended
• Observe and Debug Discoverabiliy/Connectivity
  • Nodes have too few/many connections
  • Spectral Analysis - how well is graph connected
• Observe Data availability
  • How long it takes to bootstrap
  • At any point what message(Tx, Snark, Pool, Frontier) is available at what nodes
  • Show message flow for selected data

Tasks

Initial Steps

• FE: Mockup a network of 30 nodes with dedicated seed nodes and limit of max 4 connections per node
• Cover a scenario of bootstrapping a mina rust node network

Later

• Time travelling, option to go back in time and replay state of graph
• Filters based on data availability, eg select a message and see what nodes do have it
• Graphs that show data propagation, interactions between nodes

[lukasimrich]

Week 2

Discovery & Research

DONE

• Kademlia and DHT
• Gossipsub and Full Message, Metadata Network
• Adjacent, Laplacian matrixes, Spectral gap for creating/maintaining connections

UI Concept

• Network Topology with filters for KAD, Gossipsub
• Detailed views for a specific node
• Filters to select nodes based on limit connections

[lukasimrich]

Week 3

• Explored Spectral Layout & Filters
• Explored ChatGPT Wolfram for Generating Graphs, Insights

UI

• Spectral gap Informs about graph connectivity
• Options to choose layout - Spectral / Spring
• Filters/Distributions for Degree, EigenValues

[lukasimrich]

Week 5

Focus on Expander Graphs

• Showing key metrics Degree, Laplacian spectral gap, Cheegers constant
• Showing range for values to see how close we are to ideal expander graph
• Prepare mockup data, render data and iterate UI

Main Thesis: Expander graphs are desired, we want to check how close our network topology to an expander graphs is.

Expander graphs have small sets of vertices that are incredibly well connected to the rest of the graph. They are characterized by having a large spectral gap, which means they don’t have obvious “weak points” where they can be easily split. Expander graphs are fascinating because, despite their sparse appearance (not many edges), they boast strong connectivity properties

So we need a way to identify expander graphs, the very key metric is spectral gap. The reason why is cheegers inequality:
The Cheeger inequality bridges the gap between this concept and the spectral properties of the graph, specifically relating the
Cheeger constant to the second smallest eigenvalue (λ2) of the graph’s Laplacian matrix. It essentially tells us that you can infer how hard it is to “cut” the graph by looking at λ2. If λ2 is small, the graph has a significant bottleneck, making it easier to cut it into two big pieces with a small boundary. This is astonishing because it links a purely combinatorial property (the difficulty of making a cut) to a spectral property (an eigenvalue).

Now lets go to UI part, based on the above, we should have:
Degree distribution
expander graphs have sparse appearance (not many edges), vertices have relatively small degree
expander graphs typically have a relatively uniform degree distribution, meaning most nodes have a similar number of edges
Spectral gap - the second smallest eigenvalue (λ2) of the graph’s Laplacian matrix
For irregular graphs, the expansion properties are closely related to the second-smallest eigenvalue of the normalized Laplacian matrix, λ2
Cheegers constant - quantifies the “bottleneck” of the graph - hard it is to separate the graph into disjoint components without cutting a significant number of edges
Cheeger constant in interlinked with λ2, due to Cheeger inequality, so it is somehow repeating metric but still might be useful to have it and might be able to provide extra details
Ramanujan graphs - special class of expander graphs that are considered optimal with respect to their expansion properties.
they are regular, not sure how closely we can be with our topology to regular
I guess, we can have them as a pinnacle of what is possible to achieve
There is a ramanujan property check to see whether a graph is ramanujan, first the graph needs to be regular

Now UI shows hierarchically:
How close we are to be an exapnder graph -> This is the strongly connected message in top left corner with key values backing it up
Spectral cut - this should draw graph in such way, that if there are clear bottlenecks, human eye should be able to spot them - having bottlenecks mean, being less expander graph
Right Panel showing Degree Distribition, the second smallest eigenvalue and other eigenvalues, cheegers contanst

[lukasimrich]

Week 7

Focus on KAD DHT

• Overview of all peers and their DHT
• Exploring tree and similar views to display DHT
• Table showing DHT

[lukasimrich]

Week 8

• Peer distances scale reworked to make it simpler
• Infographics for building an DHT, step by step from network genesis

Peer Distances Table

Peer Distances Graph

Inforgraphic