Author Topic: Raft consensus algorithm, how does it compare and contrast to DPoS?  (Read 2062 times)

0 Members and 1 Guest are viewing this topic.

Offline yellowecho

I would be very interested in starting with a well-studied and clean protocol like Raft, and then adding only the necessary missing DPOS-like features on top of it for ensuring the right economic incentives needed for consensus within a profitable DAC.
+5%!  Please do this
696c6f766562726f776e696573

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
Raft looks extremely interesting and I very much want to do an analysis comparing/contrasting with DPOS. Even the very fact that Raft has a rigorous specification which has been formally reviewed (at least in an academic sense) and has numerous different implementations are both important strengths which DPOS is sorely lacking at present. I would be very interested in starting with a well-studied and clean protocol like Raft, and then adding only the necessary missing DPOS-like features on top of it for ensuring the right economic incentives needed for consensus within a profitable DAC.
Sounds good to me .. can I join?

Offline vikram

Raft looks extremely interesting and I very much want to do an analysis comparing/contrasting with DPOS. Even the very fact that Raft has a rigorous specification which has been formally reviewed (at least in an academic sense) and has numerous different implementations are both important strengths which DPOS is sorely lacking at present. I would be very interested in starting with a well-studied and clean protocol like Raft, and then adding only the necessary missing DPOS-like features on top of it for ensuring the right economic incentives needed for consensus within a profitable DAC.

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
basically the modifications for raft to be dpos are not so many:

- there is a package every 10 secs
- every package the next master is chosen from a list
- if a master misses its spot .. the updates is missing
- whenever all nodes have been master in a round, a new list is randomly drawn

tada: DPOS :-)

That's what I'm seeing as well. Maybe something they've done is an improvement on DPoS? So far I haven't found any which is a credit to Dan but usually when two different people invent the wheel you do see some slightly different innovations in each wheel. Specifically I was looking for optimizations which could apply to DPoS.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
basically the modifications for raft to be dpos are not so many:

- there is a package every 10 secs
- every package the next master is chosen from a list
- if a master misses its spot .. the updates is missing
- whenever all nodes have been master in a round, a new list is randomly drawn

tada: DPOS :-)

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
sounds like DPOS without the 10 secs synchronization ... gonna read over it.. looks interesting

//edit: ui .. nice algorithm .. it seems each node has its own timer (randomly chosen) and whenever a timer goes to zero that nodes becomes the master node .. unless it received a message from the current master node .. then the counter is reset. I think it it a totally different problem .. It is more like having a master DPOS node and having multiple distributed nodes that serve as a entry point to the network maybe (just like a seed node) and the master node updates all the seed nodes .. once the master node fails .. one of the seed nodes takes over ..

IMHO this is more a backup procedure for a centralized consensus .. not the other way round ..

Still a nice find .. learn something new every day :-)

That is true but innovation can be found anywhere. Often people solve problems for you inadvertently while trying to do something else. I think whenever there is technical overlap there is potential for novel solutions to be found.

If we look at it as a pure algorithm maybe something within it is an improvement on DPoS.

In my opinion it's similar to DPoS in that DPoS does select a leader temporarily in the form of a delegate. 1 delegate is selected to verify a block, am I right? I will have to review this algorithm thoroughly and ask anyone else with a technical proclivity and spare time to do the same.
« Last Edit: September 13, 2014, 12:33:14 pm by luckybit »
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
sounds like DPOS without the 10 secs synchronization ... gonna read over it.. looks interesting

//edit: ui .. nice algorithm .. it seems each node has its own timer (randomly chosen) and whenever a timer goes to zero that nodes becomes the master node .. unless it received a message from the current master node .. then the counter is reset. I think it it a totally different problem .. It is more like having a master DPOS node and having multiple distributed nodes that serve as a entry point to the network maybe (just like a seed node) and the master node updates all the seed nodes .. once the master node fails .. one of the seed nodes takes over ..

IMHO this is more a backup procedure for a centralized consensus .. not the other way round ..

Still a nice find .. learn something new every day :-)
« Last Edit: September 13, 2014, 12:25:22 pm by xeroc »

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
This whitepaper and these implementations are for technical minds.
Is there anything within them which could improve DPoS?

https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
https://raftconsensus.github.io
http://ramcloud.stanford.edu/raft.pdf
https://raftconsensus.github.io/#implementations
https://en.wikipedia.org/wiki/State_machine_replication

Quote
Paxos requires a single leader to ensure liveness.[6] That is, one of the replicas must remain leader long enough to achieve consensus on the next operation of the state machine. System behavior is unaffected if the leader changes after every instance, or if the leader changes multiple times per instance. The only requirement is that one replica remain leader long enough to move the system forward.

The above quote is similar to the DPoS. Only with DPoS there is a pool of 101 possible leaders who can propel the state of the Bitshares network forward.

Quote
Conflict Resolution
In general, a leader is necessary only when there is disagreement about which operation to perform,[11] and if those operations conflict in some way (for instance, if they do not commute).[12]
When conflicting operations are proposed, the leader acts as the single authority to set the record straight, defining an order for the operations, allowing the system to make progress.
With Paxos, multiple replicas may believe they are leaders at the same time. This property makes Leader Election for Paxos very simple, and any algorithm which guarantees an 'eventual leader' will work.

Step by step simplified versions for the less technically inclined:
http://thesecretlivesofdata.com/raft/
https://speakerdeck.com/abailly/the-raft-protocol-distributed-consensus-for-dummies
« Last Edit: September 13, 2014, 12:53:32 pm by luckybit »
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads