Running Time of Oral Messages Algorithm OM(m) for Byzantine Generals Fault Tolerance

Let us consider a byzantine generals problem assuming:

  • less than 1/3 of generals are traitors

  • Oral messages

  • No Crypto

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 !