Lol, nice link. Why do you think number of messages is n^3? Each message only needs to be sent once to each network participant, that's n messages. Additional messages will be needed to tell their connections which messages they've received, but this can be a single metadata message talking about many primary messages. So if you send 1000 messages through a network of 3000 people, that's not 3000^3*1000 messages, it's 1000*3000 + a*3000 where a is how many metadata messages are sent per message (which likely would be more related to the rate at which messages are sent, rather than any kind of constant).
Because that's how many messages are required to solve for consensus given byzantine failures, at least with relatively simple algorithms like pratical byzantine fault tolerance (p-BFT).
The exact bound is O(m*N^2) for pBFT, where m is the number of rounds, at up to 1/3 of N. Blockchains use a different consensus mechanism, but the consensus mechanism is still incredible inefficient compared to something like 2PC which drives Paxos, and can make decisions in O(N) messages like you said.
http://www.cs.albany.edu/~maniatty/teaching/os/bft/lectnotes...
