ref celestiaorg/celestia-core#1145

Currently when the proposer creates a block, it will send each block part over the internal message queue. This can actually take a some time. The gossip routine doesn't account for that and will start gossiping immediately, which results in sending the same block parts to all peers instead of sending them randomly.

This is why when we trace the block parts, we often see them downloaded in order. This also defeats the purpose of using block parts entirely, as we end up gossiping the entire block to all peers.

below we can see a diagram that illustrates block propagation for a given height that shows this occuring. on the y axis we have block part indexes, and on the x axis

If we simply wait for the block to go over the internal message queue before gossiping, it fixes the issue and we gossip all of the block parts randomly!

There's still quite a bit of room to optimize which parts we send to each peer. One simple non-breaking change would be to not gossip block parts entirely randomly. Instead, we should keep track of which parts have been sent to any peer, and prefer to send a part to a peer if it has been sent to fewer peers.

While I'm convinced that this was one of the bottlenecks, it certainly isn't the only one since this change still doesn't increase throughput on its own. ATM, I think there's quite a lot of backup occurring, because we frequently end up receiving block parts super late.