Consider the following problem:

We have an extremely large set of nodes, $\pi_0, \ldots, \pi_{N - 1}$ with $N$, e.g., in the order of millions. Each node has a boolean variable $b_0, \ldots, b_{N - 1}$. Some of the nodes will have $b_i = \top$, others will have $b_i = \bot$.

Now, I need a procedure that can scale to that extremely large amount of nodes, that is guaranteed to rapidly converge to a situation where either $b_0 = \ldots = b_{N - 1} = \top$ or $b_0, \ldots, b_{N - 1} = \bot$. It is not absolutely fundamental that, if at the beginning the majority of the boolean values is $\top$, we converge to $\top$, and vice versa.

In the set of nodes, there is a fraction of malicious nodes whose purpose is to make the consensus protocol to never converge.

What solutions are there to achieve this? What is the fastest algorithm that achieves consensus? What is the maximum fraction allowed of malicious nodes for that algorithm?


Your Answer

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

Browse other questions tagged or ask your own question.