3 ms·

Is there anything blockchains can do in less time complexity than traditional computations?

by mtreis86 5y ago

wmf 5y ago
Inherently no; consensus requires redundant computation.
- 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 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 ago
      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.pdf http://www.cs.albany.edu/~maniatty/teaching/os/bft/lectnotes...
noxer 5y ago
DTLs aren't "computers" its just that some build a computer into it to create a decentral computer. In its raw form a DTL does not compute an output but ofc all participants compute signatures and such stuff to validate input and reach consensus. This is not a competition to a single computer as load is no distributed its the exact opposite. Everyone checks the rules of the system. (not to be confused with mining that does nothing, its just a puzzle to decide who can write the next block)
- wcoenen 5y ago
  What is DTL? Did you mean DLT (distributed ledger technology)?

Is there anything blockchains can do in less time complexity than traditional computations?

wmf 5y ago

Inherently no; consensus requires redundant computation.

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 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 ago
    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.pdf http://www.cs.albany.edu/~maniatty/teaching/os/bft/lectnotes...

noxer 5y ago

DTLs aren't "computers" its just that some build a computer into it to create a decentral computer. In its raw form a DTL does not compute an output but ofc all participants compute signatures and such stuff to validate input and reach consensus. This is not a competition to a single computer as load is no distributed its the exact opposite. Everyone checks the rules of the system. (not to be confused with mining that does nothing, its just a puzzle to decide who can write the next block)

wcoenen 5y ago
What is DTL? Did you mean DLT (distributed ledger technology)?