5 ms·

As an alternative to Paxos-related consensus algorithms, some projects may want to take a look at the Raft consensus protocol: https://www.brianstorti.com/raft/

As an alternative to Paxos-related consensus algorithms, some projects may want to take a look at the Raft consensus protocol: https://www.brianstorti.com/raft/ https://www.brianstorti.com/raft/ Whereas Paxos tries to maintain a fully distributed consensus state, Raft instead proposes a protocol for automatically electing a leader node from a group of follower nodes, and coordinating the replication of the write log through that leader node. I haven't had the pleasure of experimenting with either one though and would love to hear from people who have.

killjoywashere 8y ago
Isn't raft the default for Bitcoin?
- deathanatos 8y ago
  No. Raft and Bitcoin's algorithms for agreeing on what the blockchain is are completely different. AIUI, Bitcoin's "consensus" is just whoever has the longest valid blockchain is the winner. The algorithm tunes the difficulty s.t. it takes ~10 minutes to find a block, so the chance of two blockchains continuing to have the same length for any long amount of time is unlikely. That is, one chain will find the next block before the other, and in the meantime, be able to distribute that fact to the other nodes and thus "win". From https://en.bitcoin.it/wiki/Block_chain https://en.bitcoin.it/wiki/Block_chain: > Honest generators only build onto a block (by referencing it in blocks they create) if it is the latest block in the longest valid chain. "Length" is calculated as total combined difficulty of that chain, not number of blocks, though this distinction is only important in the context of a few potential attacks.
- narrator 8y ago
  No. Bitcoin uses its own protocol. Raft could not be used for a secure cryptocurrency bevause Raft does not handle byzantine faults[1]. It assumes nodes are not run by malicious actors and messages sent are unaltered in transit. [1] https://en.m.wikipedia.org/wiki/Byzantine_fault https://en.m.wikipedia.org/wiki/Byzantine_fault
  - hugofirth 8y ago
    True. Though in tradeoff it has massively increased throughput. I'm always frustrated when I see blockchains recommended as a solution for a consensus problem in anything but a zero-trust scenario
    - parasubvert 8y ago
      Even in a zero trust scenario, you need a majority of nodes to be good faith, non-colluding actors. Even anarchy breaks down in the face of unequal power.
- kccqzy 8y ago
  Bitcoin consensus is extremely simple: the chain with the most accumulated difficulty. Furthermore blocks aren't removed or changed, so consensus is in fact a monotonic process. You don't need either Paxos or Raft or any other sophisticated algorithm; just broadcast every block you believe to be part of the most difficult chain and consensus will be achieved.
- RcouF1uZ4gsC 8y ago
  Bitcoin consensus is what is called Byzantine consensus - that is your consensus still has to work with some nodes actively trying to send bad information to mess up the protocol. Raft and Paxos are non-Byzantine. They assume that the nodes are actively trying to follow the protocol though there me be such things as network partitions and crashes.
zzzcpan 8y ago
It's not that simple. Here's an overview on paxos/raft consensus algorithms: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ and even that is incomplete and not necessarily describes trade-offs well. Submitted generalized solution is a better point to start experimenting from.
Vervious 8y ago
Raft is arguably more difficult to understand at a deep level. After extensive study, I've noticed that Raft hides all of its complexity under its leader election setup. There's nuance after nuance. With Paxos, the complexity is explicit and at the forefront, which is actually better, when trying to reason about a distributed system and its invariants.
- ccleve 8y ago
  That was my experience as well. The rules around leader election, terms, voting, timeouts and the like are very subtle.
- pests 8y ago
  Raft is basically a fixed leader elected by a single round of Paxos.
ccleve 8y ago
It took me months to do a reliable Raft implementation. The author of the Raft paper, Diego Ongaro, wrote in a comment on a Raft mailing list that it could take weeks. The Raft paper is really easy to read and understand, but the actual code is very tricky.
- justinjlynn 8y ago
  What did you find most difficult about the implementation?
  - Matheus28 8y ago
    Not OP, but it is very easy to make mistakes while implementing it and end up with something that is not actually reliable. You have to have the paper opened and write code line by line looking at it. I implemented it a while ago so that's the most I remember, but it did a bit of fuzzing to nail down every bug.
    - isbvhodnvemrwvn 8y ago
      Also not OP, I think I went through the paper 10 times over during the implementation. There's a lot of cross-references all over the place.
    - karl-police 8y ago
      Could I ask you something, or maybe on Steam?
    - karl-police 8y ago
      Or I could ask you here one of the questions. Do you host diep.io on cloudflare, heroku, linode etc.? or do you have own servers? Because I'm interested about developing something.
  - ccleve 8y ago
    To make it work with any kind of performance, all message passing needs to be asynchronous, and you need an event loop to process messages one at a time. Things are much simpler if your code is effectively single-threaded when processing an inbound message. That took me a while to figure out. Futures and promises are very helpful. It took a while to get the building blocks together: the log file, which can be traversed, read, and rolled back/truncated (use a kv store for this, trust me), and the transport mechanism to deal with sending complex objects and handling errors and timeouts. Tracking terms, states (leader, follower, candidate), rejecting out of date terms, voting, elections -- it's all very complex. You'll have to build some really, really good multi-threaded tests that simulate out-of-order and dropped messages, then really pound away at the system. And good logging to find that odd corner case that keeps coming up and throwing mysterious messages. I haven't even tried membership changes yet.
DannyBee 8y ago
This paper is deliberately a generalization of all of them, actually. Raft can also be explained in terms of the rules/system she provides. She happens to use PaxOS as examples to show they are non-optimal, in part because Raft is already deliberately non-optimal. The other reason is that Raft is completely trivial in her framework. It is equivalent to only having one thing decide the registers (and all the hard work is in deciding which thing).
- thecupisblue 8y ago
  Exactly this, not sure why people think it's a different thing - just wrap nodes into a higher level of abstraction. I believe Raft might be a better approach to scalable consensus tho but there needs to be more layers to a network so the network can be more self-balancing and localised. If we we call "heartbeat" the frequency at which a node is synced to the network (achieves consensus) - lower heartbeat nodes need to stay close only to nodes with a "heartbeat" faster than theirs and elect leaders in that group. The leaders in that group are also in a group of other leaders of that layer and listening to their leader, which belongs to a group above (like zooming out from a group and the group becoming a node in a larger graph). In the end, there is only one state after all and the graph is the ultimate leader with the highest heartbeat. We wouldn't need many layers to cover all nodes, assuming laws of nature and all. Then just go a layer up/down if the network is getting too large, use a karmic system to position new/reactivated nodes. Seems scalable enough. Sorry OP, it might be too early and I'm just thinking out loud in a comment box.
- yxhuvud 8y ago
  Can the framework model the leader election though?
  - DannyBee 8y ago
    They do, effectively. They show what is necessary for quorums, and show that a large number of algorithms meet these requirements. Hence, the single leader election is not actually necessary (and this is one of their points - the existing algorithms require much stronger quorum guarantees than are actually necessary for correctness)

killjoywashere 8y ago

Isn't raft the default for Bitcoin?

deathanatos 8y ago
No. Raft and Bitcoin's algorithms for agreeing on what the blockchain is are completely different. AIUI, Bitcoin's "consensus" is just whoever has the longest valid blockchain is the winner. The algorithm tunes the difficulty s.t. it takes ~10 minutes to find a block, so the chance of two blockchains continuing to have the same length for any long amount of time is unlikely. That is, one chain will find the next block before the other, and in the meantime, be able to distribute that fact to the other nodes and thus "win". From https://en.bitcoin.it/wiki/Block_chain https://en.bitcoin.it/wiki/Block_chain: > Honest generators only build onto a block (by referencing it in blocks they create) if it is the latest block in the longest valid chain. "Length" is calculated as total combined difficulty of that chain, not number of blocks, though this distinction is only important in the context of a few potential attacks.
narrator 8y ago
No. Bitcoin uses its own protocol. Raft could not be used for a secure cryptocurrency bevause Raft does not handle byzantine faults[1]. It assumes nodes are not run by malicious actors and messages sent are unaltered in transit. [1] https://en.m.wikipedia.org/wiki/Byzantine_fault https://en.m.wikipedia.org/wiki/Byzantine_fault
- hugofirth 8y ago
  True. Though in tradeoff it has massively increased throughput. I'm always frustrated when I see blockchains recommended as a solution for a consensus problem in anything but a zero-trust scenario
  - parasubvert 8y ago
    Even in a zero trust scenario, you need a majority of nodes to be good faith, non-colluding actors. Even anarchy breaks down in the face of unequal power.
kccqzy 8y ago
Bitcoin consensus is extremely simple: the chain with the most accumulated difficulty. Furthermore blocks aren't removed or changed, so consensus is in fact a monotonic process. You don't need either Paxos or Raft or any other sophisticated algorithm; just broadcast every block you believe to be part of the most difficult chain and consensus will be achieved.
RcouF1uZ4gsC 8y ago
Bitcoin consensus is what is called Byzantine consensus - that is your consensus still has to work with some nodes actively trying to send bad information to mess up the protocol. Raft and Paxos are non-Byzantine. They assume that the nodes are actively trying to follow the protocol though there me be such things as network partitions and crashes.

zzzcpan 8y ago

It's not that simple. Here's an overview on paxos/raft consensus algorithms: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ and even that is incomplete and not necessarily describes trade-offs well. Submitted generalized solution is a better point to start experimenting from.

Vervious 8y ago

Raft is arguably more difficult to understand at a deep level. After extensive study, I've noticed that Raft hides all of its complexity under its leader election setup. There's nuance after nuance. With Paxos, the complexity is explicit and at the forefront, which is actually better, when trying to reason about a distributed system and its invariants.

ccleve 8y ago
That was my experience as well. The rules around leader election, terms, voting, timeouts and the like are very subtle.
pests 8y ago
Raft is basically a fixed leader elected by a single round of Paxos.

ccleve 8y ago

It took me months to do a reliable Raft implementation. The author of the Raft paper, Diego Ongaro, wrote in a comment on a Raft mailing list that it could take weeks. The Raft paper is really easy to read and understand, but the actual code is very tricky.

justinjlynn 8y ago
What did you find most difficult about the implementation?
- Matheus28 8y ago
  Not OP, but it is very easy to make mistakes while implementing it and end up with something that is not actually reliable. You have to have the paper opened and write code line by line looking at it. I implemented it a while ago so that's the most I remember, but it did a bit of fuzzing to nail down every bug.
  - isbvhodnvemrwvn 8y ago
    Also not OP, I think I went through the paper 10 times over during the implementation. There's a lot of cross-references all over the place.
  - karl-police 8y ago
    Could I ask you something, or maybe on Steam?
  - karl-police 8y ago
    Or I could ask you here one of the questions. Do you host diep.io on cloudflare, heroku, linode etc.? or do you have own servers? Because I'm interested about developing something.
- ccleve 8y ago
  To make it work with any kind of performance, all message passing needs to be asynchronous, and you need an event loop to process messages one at a time. Things are much simpler if your code is effectively single-threaded when processing an inbound message. That took me a while to figure out. Futures and promises are very helpful. It took a while to get the building blocks together: the log file, which can be traversed, read, and rolled back/truncated (use a kv store for this, trust me), and the transport mechanism to deal with sending complex objects and handling errors and timeouts. Tracking terms, states (leader, follower, candidate), rejecting out of date terms, voting, elections -- it's all very complex. You'll have to build some really, really good multi-threaded tests that simulate out-of-order and dropped messages, then really pound away at the system. And good logging to find that odd corner case that keeps coming up and throwing mysterious messages. I haven't even tried membership changes yet.

DannyBee 8y ago

This paper is deliberately a generalization of all of them, actually. Raft can also be explained in terms of the rules/system she provides. She happens to use PaxOS as examples to show they are non-optimal, in part because Raft is already deliberately non-optimal. The other reason is that Raft is completely trivial in her framework. It is equivalent to only having one thing decide the registers (and all the hard work is in deciding which thing).

thecupisblue 8y ago
Exactly this, not sure why people think it's a different thing - just wrap nodes into a higher level of abstraction. I believe Raft might be a better approach to scalable consensus tho but there needs to be more layers to a network so the network can be more self-balancing and localised. If we we call "heartbeat" the frequency at which a node is synced to the network (achieves consensus) - lower heartbeat nodes need to stay close only to nodes with a "heartbeat" faster than theirs and elect leaders in that group. The leaders in that group are also in a group of other leaders of that layer and listening to their leader, which belongs to a group above (like zooming out from a group and the group becoming a node in a larger graph). In the end, there is only one state after all and the graph is the ultimate leader with the highest heartbeat. We wouldn't need many layers to cover all nodes, assuming laws of nature and all. Then just go a layer up/down if the network is getting too large, use a karmic system to position new/reactivated nodes. Seems scalable enough. Sorry OP, it might be too early and I'm just thinking out loud in a comment box.
yxhuvud 8y ago
Can the framework model the leader election though?
- DannyBee 8y ago
  They do, effectively. They show what is necessary for quorums, and show that a large number of algorithms meet these requirements. Hence, the single leader election is not actually necessary (and this is one of their points - the existing algorithms require much stronger quorum guarantees than are actually necessary for correctness)