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 !



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.