This package contains an abstract protocol simulator for the gossipsub family of protocols, supporting gossipsub v1.0, v1.1, and the experimental episub extensions (gossipsub v1.2).
The simulator is written in Gerbil using actor orient programming.
Note: This repo originally contained the first abstract gossipsub implementation, before it was deployed in production. Since then, gossipsub has evolved significantly and is in production use in several blockchains (Filecoin, ETH2, Celestia, etc…).
The original README contained a literal presentation of the gossipsub protocol, and has been preserved here as it is still a pretty good read and introduction to gossipsub.
You can install simsub using gxpkg, the Gerbil package manager:
gxpkg install github.com/vyzo/gerbil-simsub
Note that simsub requires Gerbil v0.17 or newer.
The simulator creates a random network, using parameterized connectivity and link latency with jitter. The simulator creates the topology and uses a user supplied script to drive the simulation. The simulation is traced so that the results and behaviour of the protocol can be analyzed.
For the simulator core, see simsub/simulator.ss. The default included simulator driver and script script is in simsub/scripts.ss. The simulator is parameterized using keyword arguments; see `simple-simulation` and `start-simulation!` for the relevant keywords.
Protocols are implemented as actors. The following protocols are currently supported:
- floodsub as a baseline; see simsub/floodsub.ss.
- gossipsub v1.0, the original gossipsub protocol; see simsub/gossipsub-v1_0.ss.
- gossipsub v1.1, the currently deployed protocol in production; see simsub/gossipsub-v1_1.ss. Note that the scoring function is not implemented here, although it should be straightforward to do so if you want to study its properties using the simulator framework.
- gossipsub v1.2, aka episub. This is the next generation evolution of gossipsub, currently in development. See simsub/episub.ss.
Here is an example, running simulations using gossipsub v1.0 and gossipsub v1.1. Note the explicit use of the rng to ensure that the underlying topology and source selection is the same for both runs and that we compare apples to apples.
By default, the simulation creates a network of 100 nodes, with each node randomly connected to 20 other nodes. There are 5 (randomly selected) sources, which send a total of 10 messages, 1 per second. All these parameters can be changed for longer and bigger simulations, using keyword arguments.
> (import :vyzo/simsub/scripts :vyzo/simsub/env)
> (def rng (make-rng))
> (simple-gossipsub/v1.0-simulation rng: rng)
=== simulation summary ===
nodes: 100
messages: 10
sources: 5
publish: 10
deliver: 1000
!!pubsub.publish: 10
!!gossipsub.iwant: 44
!!pubsub.message: 6280
!!gossipsub.graft: 372
!!pubsub.connect: 2000
!!gossipsub.prune: 7
!!gossipsub.ihave: 7212
=== delivery latency histogram ===
0-100ms 156 ***************
100-200ms 722 ************************************************************************
200-300ms 112 ***********
> (simple-gossipsub/v1.1-simulation rng: rng)
=== simulation summary ===
nodes: 100
messages: 10
sources: 5
publish: 10
deliver: 1000
!!pubsub.publish: 10
!!gossipsub.iwant: 30
!!pubsub.message: 6738
!!gossipsub.graft: 372
!!gossipsub.prune: 7
!!pubsub.connect: 2072
!!gossipsub.ihave: 9516
=== delivery latency histogram ===
0-100ms 527 ****************************************************
100-200ms 463 **********************************************
Note that it is generally desirable for a simulation framework to produce reproducible artifacts. This is however is very tricky when dealing with a real-time multi-threaded simulation, as even if you completely nail down the random number generators, you will still have to deal with non-determinism stemming from concurrency of messages, down to the quantum of computation.
The simulation framework takes several steps to ensure that simulations are as close to reproducible as possible, at least when it comes to the underlying network topology. The system uses a root rng as a template, ie this rng is not used directly, but rather its state is used as a template for deterministically constructing all the other rngs in the system. Starting from the template, an rng is derived for every actor in the system, so that different threads don’t interfere with each other in random number generation. Furthermore, the router derives (lazily) an rng for every actor pair that communicates, so that the base latency and jitter are deterministic. And finally, every operation that works with peer sets for selection is shuffled after normalizing, so that small deviations from concurrent events are corrected to the extent possible.
Despite all that, the fractal nature of these networks ensures that even small timing deviations in some message may result in large behavioural deviations; completely deterministic simulations are practically impossible and that’s the best we can do.
By default, simsub will run simulations in real time, using the core Gerbil/Gabit scheduler. This provides great fidelity to simulations, but it also limits the scalability of the simulation. As you run bigger simulations will, you will notice that the simulator is compute-bound and begins to lag, which invalidates results.
In order to avoid this issue, and provide scalable simulations, simsub provides an alternate scheduler that implements virtual time. The scheduler is implemented by redefining a number of thread system primitive, such that thread state is tracked, and time advances when there are no active threads. This allows the simulation to scale bound only by available memory. The downside is that actual computations take 0 virtual time, which may have some effects in the concurrency factors of the simulation. Nonetheless, this should not affect the fidelity of simulations because all observable actions (messages) take time, as dictated by the router, and hence heartbeats and timeouts will not be starved.
In order to use the virtual time scheduler, use the following code before running a simulation. “` (import :vyzo/simsub/scheduler) (enable-virtual-time-scheduler!) “`
If you want to reset the clock and throw away intermediate state you can reset between simulation runs: “` (virtual-time-scheduler-reset!) “`
MIT; © 2018-2022 vyzo