Let us consider a byzantine generals problem assuming:
less than 1/3 of generals are traitors
One solution is the Oral Message algorithm OM(m), m being the maximum number of traitors we tolerate.
For n Generals and m = 0, the number of messages sent is in O(n) For n Genrals and m = 1, we have O(n^2) total messages sent in OM(m) solution My reading indicates that for m = 2, we have O(n ^3) and for m = 3 O(n^4). Can someone explain to me how we have O(n^3) and O(n^4) for m = 2 and 3 respectively ? Thanks in advance !