4 ms·

Ask HN: Peer-to-peer consensus protocols / algorithms

4 points by vivegi 4y ago

If I want to architect a peer-to-peer application that needs to achieve consensus, what are some of the provably correct protocols/algorithms? I am not interested in "web3/crypto" solutions. Just pure theoretical papers that describe how one might go about solving this problem from first principles. The closest analogy would be Two Phase Commit for distributed databases. If you can cite the papers or provide links that would be great.

verdverm 4y ago
RAFT and PAXOS are the main ones I know of. There are applications which can help you with this already, like Consul https://www.hashicorp.com/resources/raft-consul-consensus-protocol-explained https://www.hashicorp.com/resources/raft-consul-consensus-pr... You might also look into the pBFT subject Hyperledger Fabric, is a blockchain framework but not web3 / crypto that might be interesting too, if you are surveying widely
- minhmeoke 4y ago
  +1 for RAFT, Paxos is quite complex and easy to mess up. If you're lazy, you can just throw Zookeeper at the problem (this is what many Big Data systems like Spark and Kafka often use for synchronization and consensus): - https://zookeeper.apache.org/ https://zookeeper.apache.org/ - https://zookeeper.apache.org/doc/current/zookeeperInternals.html https://zookeeper.apache.org/doc/current/zookeeperInternals....
acuozzo 4y ago
> If I want to architect a peer-to-peer application that needs to achieve consensus, what are some of the provably correct protocols/algorithms? None. Ever.¹ Proof: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf [1] Assuming that peers in your application can crash.
- vivegi 4y ago
  Thanks. Interesting paper. > THEOREM 2. There is a partially correct consensus protocol in which all nonfaulty processes always reach a decision, provided no processes die during its execution and a strict majority of the processes are alive initially. This seems to be the silver lining from the paper for practitioners.
  - acuozzo 4y ago
    > This seems to be the silver lining from the paper for practitioners. Indeed. Of course, the hard (impossible?) part is ensuring that no peers die.

4 points by vivegi 4y ago

verdverm 4y ago

RAFT and PAXOS are the main ones I know of. There are applications which can help you with this already, like Consul https://www.hashicorp.com/resources/raft-consul-consensus-protocol-explained https://www.hashicorp.com/resources/raft-consul-consensus-pr... You might also look into the pBFT subject Hyperledger Fabric, is a blockchain framework but not web3 / crypto that might be interesting too, if you are surveying widely

minhmeoke 4y ago
+1 for RAFT, Paxos is quite complex and easy to mess up. If you're lazy, you can just throw Zookeeper at the problem (this is what many Big Data systems like Spark and Kafka often use for synchronization and consensus): - https://zookeeper.apache.org/ https://zookeeper.apache.org/ - https://zookeeper.apache.org/doc/current/zookeeperInternals.html https://zookeeper.apache.org/doc/current/zookeeperInternals....

acuozzo 4y ago

> If I want to architect a peer-to-peer application that needs to achieve consensus, what are some of the provably correct protocols/algorithms? None. Ever.¹ Proof: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf [1] Assuming that peers in your application can crash.

vivegi 4y ago
Thanks. Interesting paper. > THEOREM 2. There is a partially correct consensus protocol in which all nonfaulty processes always reach a decision, provided no processes die during its execution and a strict majority of the processes are alive initially. This seems to be the silver lining from the paper for practitioners.
- acuozzo 4y ago
  > This seems to be the silver lining from the paper for practitioners. Indeed. Of course, the hard (impossible?) part is ensuring that no peers die.