You might say "well, gossip helps with this!" or something, but it doesn't.
Bluesky *strongly emphasizes* in their documentation that they are aiming for "no missed message replies". Without directed message delivery, everyone needs to *receive* every message.
Regardless of how the messages are distributed, It's O(n^2) in best case if everyone fully self hosts and there is no directed delivery.