Stephen's thread yesterday, as well as discussion on Avalanche's Discord today, inspired me to write this thread on message complexity on the Avalanche network.

: https://twitter.com/stephenbuttolph/status/1337471823106236424

TL;DR: Avalanche's message complexity scales really, really well relative to the transaction volume on the network, and relative to the size of the validator set size.
This is what allows Avalanche to achieve high throughput while having a large validator set.

Message complexity describes the number of messages that have to be sent back and forth between nodes in the network. In many classical consensus protocols, message complexity grows very rapidly relative to the number of validators.

As such, they can only support small validator sets before the number of messages grows so large as to be unmanageable. By far, most of the messages sent in Avalanche are consensus-related. As such, the complexity of these consensus messages is of the most concern.

(There are other kinds of messages sent back and forth between nodes, but ignore those for now.)

Consensus message complexity in Avalanche grows very slowly relative to transaction volume on the network and relative to the size of the validator set.

You can double transaction throughput and a given node will have to send significantly less than double the amount consensus messages. You can double the number of validators and, if all validators have equal stake, a given node won't have to handle additional consensus messages.

How is this possible? First, a primer on Avalanche consensus. (Disclaimer: this is somewhat simplified.)

When a node learns about a vertex (a block, basically; more on that later), it does a series of network polls to determine whether the vertex should be accepted or rejected.

The node randomly samples 𝑘 validators from the validator set, weighted by stake, where 𝑘 is some small constant (20 right now.) It asks each of those validators, "Do you think this vertex should be accepted?"

If a sufficient portion of those validators respond "yes," this a successful poll. The node does this until either it performs β consecutive successful polls, in which case the vertex is accepted, or until the node accepts a conflicting vertex, and so the vertex is rejected.

Avalanche achieves low message complexity relative to transaction volume by using poll amortization and by using a DAG (directed acyclic graph, a kind of data structure.) Unlike a linear blockchain, where every block has one parent, a vertex in the DAG may have multiple parents.

A successful poll for a vertex implies a successful poll for all of the vertex's ancestors. Suppose all the vertices in this graph are processing. A successful poll for vertex 4 implies a successful poll for vertices 0, 1, 2, 3, and the ancestors of those vertices.

A node doesn't need to do beta polls for vertex 0, vertex 1, and so on. It can just do β polls for vertex 4. So we get 5 vertices accepted for the price of one, so to speak. This is the amortization that I mentioned.

The upshot is that during times of high transaction throughput, the number of additional polls required for each additional vertex is very small.

What about message complexity relative to validator set size? The number of consensus messages a node sends to process a vertex is constant relative to the validator set size. Constant! Because each time a node does a poll, it samples a constant number (𝑘) of validators.

What about non-consensus messages? Again, they comprise a much smaller share of messages, so they're less of a concern. It turns out that they also scale linearly or better with transaction volume and validator set size.

Now, the Avalanche network is young and imperfect. As someone pointed out on our Discord today, network I/O (in bytes) is higher than it needs to be right now.
There are optimizations that we'll implement to reduce network I/O on Avalanche nodes.

Perhaps most notably, we've started work on implementing state summaries and "fast sync" bootstrapping. At present, when a node bootstraps (gets up to speed on the network state) it has to download and execute every transaction that has happened since the network began.

Naturally, this takes up quite a bit of bandwidth.
State summaries will allow a bootstrapping node to download only the current network state. (State summaries also allow old data to be removed from the disk, reducing storage requirements, but that's for another thread.)

There are other, less glamorous optimizations we'll do to reduce network I/O, like being more clever about what
data gets gossiped to which nodes, but that's somewhat less exciting.

That's the thread! If I made a mistake or something is unclear, please point it out so I can correct/clarify it.

Will gladly take any questions here or on the Avalanche Discord ( https://chat.avalabs.org ).