Number Duplicate Messages in Ethereum's Gossipsub Network

The total number of links that are not used to propagate a specific message is indeed l-n=\frac{n(k-2)}{2}, which makes k-2 per node on average. However each of these links will transport a duplicate in each direction. Hence, on average nodes will both send AND receive k-2 duplicates.

It is so in theory because if a message m that was received on a connection c was considered to be a duplicate, it means that m was already received on another connection. And since m was received before, it has already been sent over all connections, including c. We could say that the two duplicates of m sent over c (one in each direction) would cross paths somewhere in the internet.

This assumes that nodes have zero processing time (e.g no validation before forwarding a message). A positive processing time implies less duplicates, since a node could 1) receive m, and 2) while processing m, receive a duplicate of m on a connection c so 3) it wouldn’t send m over c, hence slightly limiting the overall number of duplicates in the network.

In Ethereum, with k=8, we get than k-2=6, so nodes are expected to both receive AND send 6 duplicates for each message. On average they are sending and receiving 7 messages. It is essential that a node receives the original message once, the other 6 received message (on average) are duplicates. On average, a node will provide 1 other node with an original message, and 6 other nodes with duplicates.

1 Like