infinity0

\section{Background}
\paragraph{Gossip} In a peer-to-peer gossip network we have to figure out how the nodes connect to each other. Two possibilities are a r-regular random graph and the SlimFly topology.

For the current assignment you can assume that the full list of peers is known, and available to each peer. (Networks where this is not the case, are vulnerable to the Sybil attack, which is out-of-scope for the time being.)

The topology should work for any sized network. Some topologies are optimised for particular network sizes (e.g. n = k ^ 2 for some k) and degrade for other sizes. This is bad.

There should be an efficient algorithm that each node can run to figure out its own neighbours. For example, for r-regular random graphs the only known way of doing this[1] is for everyone to generate the whole graph, whose computation costs O(n^3). This is not ideal. For our purposes, anything below O(n^2) can be considered reasonably efficient.

[1] (The naive method of selecting r random outgoing neighbours