3 ms·
It's so incredibly redundant I think people lack a mental model for just how many messages need to be sent for every node participant to ensure all others are r
by wespiser_2018 5y ago
It's so incredibly redundant I think people lack a mental model for just how many messages need to be sent for every node participant to ensure all others are reliable (byzantine fault tolerance).
The number of messages is is about n^3, so that's like asking 5 people to go to lunch with 125 emails.
https://scholar.harvard.edu/files/mickens/files/thesaddestmoment.pdf https://scholar.harvard.edu/files/mickens/files/thesaddestmo...
- billytetrud 5y agoLol, 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...