Raft algorithm computational complexity?

[okmanek okmanek]

Hello,

I am currently doing a project for my college where I am comparing different consensus algorithms. I tried to find what is raft algorithm computational complexity, but I could not find anything on this subject. Can you help me?

[Philip Haynes]

Okmanek,

Look at the different steps in the algorithm both in normal operation and in catchup this then tells you the computational complexity.

Philip 

[okmanek okmanek]

Ok, but I am afraid to make a mistake calculating this. Does anyone know the answer?

[Philip Haynes]

Show your working and we will tell you if you got it right or not.

[John Ousterhout]

It sounds like you are trying to get people on this distribution list to do your course work for you. Does your instructor know that you have made this request?

On Mon, Jun 6, 2016 at 2:55 PM, Philip Haynes <haynes...@gmail.com> wrote:

Show your working and we will tell you if you got it right or not.

--
You received this message because you are subscribed to the Google Groups "raft-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to raft-dev+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[okmanek okmanek]

No, he doesn't. And I don't care if he does. BTW, course objective isn't learning to calculate complexity, rather searching for information. Information which raft documentation doesn't contain (and I thing it should).

Ok, I supose you don't know the answer. Too bad. But I'm still hoping that someone does and will answer.

--
You received this message because you are subscribed to a topic in the Google Groups "raft-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/raft-dev/bCEmN5fDniI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to raft-dev+u...@googlegroups.com.

[Jordan Halterman]

I think Professor Ousterhout does know the answer.

Even if you can't find information on the complexity of Raft specifically, there is plenty of information on how to calculate it. Presumably your instructor didn't give you a question that's impossible to answer. I'd be interested to see your work if you do have it, but aside from that I don't have the answer for you either.

[Diego Ongaro]

okmanek,

I'm probably to blame for not including Raft's computational complexity in its documentation. What does computational complexity mean for a consensus algorithm? The FLP impossibility result says that we can't guarantee termination with any upper bound: https://en.wikipedia.org/wiki/Consensus_(computer_science)#Solvability_results_for_some_agreement_problems . So is that O(infinity)? The marketing people aren't going to like this.

-Diego

[okmanek okmanek]

Thank you Diego, this is useful answer for my question.

[M Rodriguez]

Hi okmanek,

I am really interested in your work on comparing different consensus algorithms. Is there any way you can tell me what you got, as i'm looking for a consensus algorithm that is low in computational complexity and communication overhead for a IoT network with limited resources.

As it turns out this kind of information is still hard to get.

Thank you for your answer!

Kind regards

Marlon