4

What kind of a Consensus Algorithms does ripple use? Is that a leader or leaderless distributed consensus algorithm? Then what?

2

It's leaderless.

A validator begins a consensus round when it has either at least one unconfirmed transaction it thinks is valid, the idle time has expired, or it sees enough validators it trusts have begun a consensus round. Each participating validator makes an initial proposal listing the transactions it believes should be applied in the current round. The servers avalanche to consensus.

If there are conflicting transactions, all cases are handled. If just one gets in the round, it is applied and the other is forever invalid. If both do, a determinstic algorithm determines which is applied first and the other fails. If neither do, a deterministic algorithm determines which is announced in the next round so there should be an agreement in that round.

Because Byzantine failure is possible, validators build the next ledger at the end of the round and then broadcast a signed validation of that ledger. Seeing a supermajority of trusted validators sign validations for the same ledger assures that an actual consensus was reached. (If there was no real consensus due to Byzantine failure, the network simply tries again.)

The avalanche algorithm is designed so that minimal overlap of trust is required. Essentially, if there's no reason a transaction shouldn't be included, every honest node should agree to include it. If there's any reason a transaction shouldn't be included, there's no harm done in excluding it. (So long as it's included in the next round if it's still valid.)

  • 1
    Due to my knowledge, it is very difficult to achieve the performance in the consensus algorithm, since all the verification nodes needs to contribute their own votes, how does Ripple provide the performance of transaction verification? – tdumidu May 12 '14 at 10:23
  • 4
    Network propagation times are quite fast. Most of the time, there's no disagreement anyway. (Everyone proposes, everyone waits two seconds for propagation, everyone realizes there's no significant disagreement. Done.) And the network is willing to tolerate a failed consensus round in exchange for speed 99.5% of the time. In addition, a "bow out" algorithm allows under-performing nodes to avoid causing problems. The network balances not being as slow as the slowest node (for performance reasons) with not being as fast as the fastest node (for security reasons). – David Schwartz May 12 '14 at 10:24
  • Why can't it use a algorithm like Paxos which have a leader? – tdumidu May 15 '14 at 10:52
  • 1
    How would you choose a leader that everyone agreed on? How would you prevent someone from gaming the leader selection and preventing the network from making forward progress? What would happen to nodes that the leader didn't wish to listen to? Would they be shut out of an entire round? – David Schwartz May 19 '14 at 13:14
  • 2
    @Gracchus There are two waits that are a minimum of 2 seconds, one to give each server a chance to make an initial proposal (so nobody declares a consensus reached without hearing from everyone) and one to give each server a chance to process the final consensus transaction set (to keep servers from getting left behind). These are just minimums though, the actual timing is adaptive. – David Schwartz May 20 '14 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.