We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that can be tolerated in this system.

One upper-bound that I have derived on the number of failures $f$ is from the fact that consensus cannot be solved in a system if

  1. connectivity of the graph $G$ i.e. $conn(G) > 2f$
  2. $n > 3f$

Since the connectivity of an m-dimensional hypercube is $m$, this gives us that $$f < \min\left(\frac{2^m}{3}, \frac{m}2\right)$$

But I am unable to show that this upper-bound is tight. This bound is tight for $m = 2$ since then the topology is a ring and $0$ failures can be tolerated in a ring topology.

I need pointers to show that this bound is tight (I think that too show this we need to give an algorithm that solves consensus under these conditions) or show some tighter upper bound (probably by reduction?)

Also why are conditions 1 and 2 necessary and sufficient only for the weak Byzantine consensus as proved in Nancy Lynch's Distributed Algorithms Theorem 6.30? My intuition is that if the connectivity of the graph is $\ge 2f+1$ then we have $2f+1$ disjoint paths between any two pair of nodes due to Menger's Theorem. Since there are only $f$ Byzantine nodes, they can corrupt at most $f$ paths and thus the majority of the paths should communicate reliably and we can solve consensus as if it were for a complete subgraph consisting of only the non-faulty processors.


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.