2 ms·
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 m
by billytetrud 5y ago
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).
- wespiser_2018 5y agoBecause 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.pdf http://www.cs.albany.edu/~maniatty/teaching/os/bft/lectnotes...