Propagating to all peers would lead to O(nm) messages being sent, where n is the number of nodes and m the number of peers per node - this devolves to O(n^2) in a fully connected network.
If we propagate to sqrt(m) peers, then in a fully connected network we send O(n * sqrt(n)) messages, which grows much slower.
Is a fully-connected network a desired/desirable goal? It surprised me that that it was a consideration.
@holiman @karalabe I tried to compare progpow verification results with https://github.com/chfast/ethash.
Single Ethash verification with the best currently available compiler is 0.9 ms.
The progpow implementation was done in this fork: https://github.com/ifdefelse/proghash/commit/dc8e918aa5cf68da0b6dc049634bde596170c14c#diff-551b1d6ef147e694c203c6e9a6dacbf7R521 but does not seem to work. At least they did not update the unit tests.
The same benchmark shows absurd 1.3 us.