Codex Swarm Overlays
1 Context
As we evolved an understanding on what needs to be understood about our swarm protocol, we realized there might be questions that are more important and more within reach than expected.
2 Graph Structure
Our protocol works by having a node join the network and ask a bootstrap node for a random subset of size \(d\) of the nodes that are currently in the swarm. Absent any dynamics, this should intuitively converge into a variant of a \(G(n, p = 1/d)\), Erdös-Rényi model, whose connectivity and diameters are well-studied.
For instance, we know that if \(p > (1+ \varepsilon )\ln n/n\), then \(G\) is connected almost surely. Almost surely, however, means that the graph might be disconnected, particularly for small \(n\).
The diameter of such graphs, on the other hand, is relatively poorly understood, with numeric results being published only relatively recently, for certain values of \(p\) [1], and with no publicly available data or code for us to study the problem further.
Furthermore, it is clear that our graphs will have a different degree distribution from Erdös-Renyi graphs as the generating game for the graph is different – nodes that enter the network early will tend to have higher degrees than nodes that enter the network late. This can lead to load imbalances, which we also intend to look into.
3 Initial Questions
Given a network \(N = \left\{o_1, \cdots, o_n\right\}\) with \(n\) nodes:
- How often will there be disconnected clusters?
- What is the degree distribution for these graphs?
- How fast should we expect a block to percolate over the network as we vary the proportions of storage nodes vs. downloader nodes?
We can provide preliminary answers to these questions by means of simple simulations.
3.1 Generating Overlay Samples
The algorithm for generating overlay graphs – which will be used throughout our experiments – is shown below. The key is the node_edges procedure, where we simulate a node being bootstrapped from a replicated tracker with a subset of the nodes already in the swarm as its neighbors:
swarm_overlay <- function(n, d, names = FALSE, directed = FALSE) {
swarm_overlay_edgelist(n, d) |>
as_overlay_graph(names = names, directed = directed)
}
as_overlay_graph <- function(edge_list, names = FALSE, directed = FALSE) {
igraph::graph_from_data_frame(
edge_list,
directed = directed,
vertices = if (names) tibble(name = 1:max(edge_list$from)) else NULL
)
}
swarm_overlay_edgelist <- function(n, d) {
map(2:n, function(i) node_edges(i, d)) |> bind_rows()
}
node_edges <- function(i, d) {
# When i <= d, we have to connect everything we have.
if (i <= d) {
return(tibble(from = i, to = 1:(i - 1)))
}
tibble(
from = i,
to = sample(1:(i - 1), d, replace = FALSE)
)
}Fig 3.1 shows a sample overlay generated using the algorithm. Note that, as expected, nodes that enter the network earlier (have a lower id number) tend to exhibit higher degrees.
swarm_overlay(15, 2, directed = TRUE) |>
ggraph(layout = "stress") +
geom_edge_link(
arrow = arrow(length = unit(0.1, "inches")),
end_cap = circle(3, 'mm')
) +
geom_node_point(size = 8) +
geom_node_text(aes(label = name), col = "white") +
theme_graph() +
set_graph_style(face = "bold")
Figure 3.1: A sample of \(G(15, 2)\).
3.2 How Often Will There Be Disconnected Clusters?
Theory from Erdös-Renyi graphs puts the connectivity threshold at \(\frac{(1 + \epsilon) \ln n}{n}\), but our graphs are different enough that we can make more precise statements.
Theorem 1. If edges are undirected, then \(G(n, d)\) is always connected. If edges are directed, on the other hand, then \(G(n, d)\) is never strongly connected.
For part 1, the reasoning is inductive: assuming that \(G(n - 1, d)\) forms a connected component, then \(G(n, d)\) must also form a connected component as the \(n^{th}\) node will have undirected edges into \(G(n - 1, d)\).
Part 2 on the other hand follows trivially from the fact that node \(1\), the first node in the network, has no outbound edges, and is therefore will always be out of the strongly connected component in the graph. \(\blacksquare\)
Because of the way we propose the protocol to work, we can assume our graphs to be undirected for the time being.
3.3 What is the degree distribution for these graphs?
To try to get a grip on degree distributions, will look into graphs \(G_{i,j} = (V_i, E_j)\) where:
\[ |V_i| = 10 \times 2^i \] this means we start with a graph of size \(10\) and then double its size for \(i = \{0, \cdots, 7\}\).
We will then look at values for \(d\) which range from \(1\) to the critical threshold for percolation in Erdös-Renyi graphs, meaning:
\[ 1 \leq d \leq \left\lceil\ln |V_i|\right\rceil \]
with \(d \in \mathbb{N}\).
Although more sophisticated sampling approaches are definitely possible [2], we will simply generate \(100\) graphs for each configuration, and compute their empirical CDF. We can then use that to get percentiles. To make things a bit more efficient, we will pre-generate the edge lists. The simulation code is pasted next, and Figure 3.2 shows the percentiles of the degree distributions as a function of swarm size, faceted by \(d \in \{1, 2, 3, 4\}\).
parameters <- chain(
map(0:8, function(i) product(v = v_i(i), d = d_i(i)) |> as.list())) |>
as.list() |>
list_c()dataset(
edge_lists,
storage = 'csv.bz2',
map(parameters, function(parameter) {
parallel::mclapply(
1:n_samples,
mc.cores = 8, # Works On My Machine (tm)
mc.set.seed = TRUE, # make sure to re-seed the forked processes
function(i) {
swarm_overlay_edgelist(parameter$v, parameter$d) |> mutate(
v = parameter$v,
d = parameter$d,
instance = i
)
}
) |> bind_rows()
}) |> bind_rows()
)dataset(
edge_degrees,
edge_lists |>
group_by(v, d, instance, to) |>
count(name = 'degree') |>
group_by(v, d) |>
reframe(quantile_df(degree, c(0, 0.1, 0.25, 0.50, 0.75, 0.9, 0.95, 1))) |>
rename(degree = val)
)plotly::ggplotly(ggplot(edge_degrees |> filter(d < 5)) +
geom_line(aes(x = v, y = degree, col = formatted_factor(quant, function(x) glue('{x*100}')))) +
scale_x_log10() +
xlab('swarm size') +
theme_playax() +
labs(colour = "percentile") +
facet_grid(cols=vars(d)))Figure 3.2: Edge degrees distribution percentiles as a function of swarm size, faceted by \(d \in \{1, 2, 3, 4\}\).
We can make three main conclusions from this:
- that the median (\(50^{th}\) percentile) degree in the graph converges to \(d\) and stays constant, regardless of the size of the swarm;
- that that the variance increases with \(d\), but marginally or not at all with the size of the swarm;
- that the maximum degree increases rapidly with \(d\).
For completeness, the data is shown in Table 3.3.
Figure 3.3: Vertex degrees.
This is all, to a certain degree, obvious, as the probability that a node gets selected as a neighbor is biased by its swarm lifetime, and points to the need of creating some type of counterweight to reverse that bias. The obvious choice would be to make older nodes less likely to be chosen on bootstrap, but this could make the swarm easy to hijack (think adversary flooding the swarm with new nodes and taking it over).
The less obvious choice would be to have nodes reject neighbor requests once a threshold is met, effectively truncating the tail of the degree distribution. This could make the bootstrap procedure more complex/slower as a node would have to request more nodes from the bootstrap service again. We will keep those in mind for the next iteration.
3.4 How fast should we expect a block to percolate over the network?
In the absence of a link capacity and/or network delay model, graph topology should dominate dissemination time. The simplest case to analyse is to assume that nodes are able to broadcast the packet to all of its neighbors. The main appeal is that this is easy to implement, and can already provide some insight.
disseminate_broadcast <- function(overlay, sources) {
dissemination_paths <- lapply(
sources,
function(source) bfs(
overlay,
root = V(overlay)[name == source],
dist = TRUE
)$dist
)
do.call(pmin, dissemination_paths)
}We will take the overlays we had from before and run a simple experiment where we pick \(1, 2, 3\) and \(4\) starting nodes chosen at random in the overlays, and compute the average dissemination times for those.
# Pre-generates graphs as otherwise this will murder simulation performance.
dataset(
graphs,
storage = 'rds',
map(parameters, function(parameter) {
pbmclapply(
1:n_samples,
function(instance) {
list(
d = parameter$d,
v = parameter$v,
instance = instance,
g = edge_lists |>
filter(d == parameter$d, v == parameter$v, instance == !!instance) |>
as_overlay_graph()
)
},
mc.cores = 2 # don't go overboard or it will suck up your RAM and crash your machine :-)
)
}) |> list_c()
)dataset(
latency_stats,
storage = 'csv',
map(parameters, function(parameter) {
graph_instances <- graphs |> filter(v == parameter$v & d == parameter$d)
map(1:n_sources_max, function(n_sources) {
raw_latencies <- map(graph_instances, function(graph) {
sources <- sample(1:graph$v, size = n_sources, replace = FALSE)
disseminate_broadcast(graph$g, sources)
}) |>
list_c()
raw_latencies |>
quantile_df(c(0, 0.1, 0.25, 0.50, 0.75, 0.9, 0.95, 1)) |>
rename(stat = quant) |>
bind_rows(
tibble(
stat = c('mean', 'variance', 'sd'),
val = mean(raw_latencies), var(raw_latencies), sd(raw_latencies)
)
) |>
mutate(
d = parameter$d,
v = parameter$v,
sources = n_sources
)
}) |> bind_rows()
}) |> bind_rows()
)Fig. 3.4 shows a grid in which each cell contains a latency \(\times\) swarm size (log scale) subplot filtered by a combination of latency percentile (columns) and initial bootstrap degree, or \(d\) (rows). This means that at cell percentile: 0.5 \(\times\) d: 2 we should see the median (\(50^{th}\) percentile) latencies for swarms with bootstrap degree \(d = 2\). Lines are then coloured based on the number of cache nodes present in the swarm (\(1\), \(2\), \(3\), or \(4\)).
With that in mind, what we see is that:
- dissemination times appear to increase logarithmically with swarm size at all percentiles, as evidenced by the straight lines in the log plots;
- increasing \(d\) changes the slope of that increase (base of the log), with the most visibly dramatic change happening from \(d = 1\) to \(d = 2\). In particular, latencies stay below \(10\) hops for all swarm sizes once \(d \geq 2\), and the median latency is below \(5\) hops;
- adding cache nodes appears to shift the intercept of the curve, even when considering a very small amount of nodes.
ggplot(latency_stats |> rename(percentile = quant)) +
geom_hline(yintercept = 5, lty = 2, col = 'orange') +
geom_line(aes(x = v, y = val, col = as.factor(sources)), lwd = 1.1) +
facet_grid(d ~ percentile, labeller = label_both) +
xlab("swarm size (log)") +
ylab("latency (hops)") +
theme_playax() +
theme(legend.position = "bottom") +
labs(col = 'cache nodes') +
scale_x_log10() +
big_fonts(15)
Figure 3.4: (click to zoom) Latency percentiles as a function of swarm size and bootstrap degree (d).
Assuming a small block size and an RTT of \(s\), this would mean a propagation time proportional to \(5 \times s\) for a single block in the absence of congested links. Finally, we see that this loosely tracks the shape of the curves for the diameters of graphs of a given size (3.5), which is unsurprising.
dataset(
graph_diameters,
storage = 'csv',
map(graphs, function(graph)
tibble(d = graph$d,
v = graph$v,
instance = graph$instance,
diameter = diameter(graph$g))
) |>
bind_rows()
)ggplot(
graph_diameters |> group_by(d, v) |> reframe(quantile_df(diameter, probs = c(0, 0.1, 0.25, 0.50, 0.75, 0.9, 0.95, 1)))
) +
geom_line(aes(x = v, y = val, col = as.factor(d))) +
facet_grid(.~quant) +
xlab("swarm size (log)") +
ylab("diameter") +
scale_x_log10() +
theme_playax() +
theme(legend.position = 'bottom') +
labs(col = 'bootstrap degree (d)')
Figure 3.5: Swarm diameter percentiles as a function of their size.
4 Next Steps
There are a few things that we could do next:
- tweak the bootstrap protocol so that it mitigates swarm age bias – where older nodes get selected more often as neighbors as part of the bootstrap procedure – thus reducing degree imbalances. This involves adding some intelligence to the DHT tracker so that it biases samples towards nodes that have been sampled less;
- run simulations with more realistic proportions of cache nodes. We constrained this to \(1--4\) for efficiency and to get results out faster, but having swarm percentages may yield more interesting numbers;
- add more sophisticated network dynamics (e.g. churn, link delays + multi-block simulations) to have more accurate estimates of performance and load.
Other issues potentially worth exploring:
- performance of compressed bitsets vs. other set reconciliation data structures like inverted Bloom filters;
- techniques for achieving Byzantine fault tolerance on random overlays.