Having just read through Lamport's paper, I was hoping someone could clarify a few things on the Oral and Signed message algorithms.

  1. Why do we have to run $OM()$, recursively by $m$? If a majority of the Lieutenants are loyal, do they not get the correct value by the first round of exchange?
  2. I'm not exactly clear on step 2 of the $SM()$ algorithm:
  • If Lieutenant $i$ receives a message of the form $v : 0 :j_1 : \ldots : Jk$
    and $v$ is not in the set $V_i$, then
    • he adds v to $V_i$;
    • if $k < m$, then he sends the message $v:0 :j_1 :\ldots:j_k : i$ to every
      lieutenant other than $j_1 \ldots j_k$.

Does Lieutenant $i$ only sign a message if $v$ is not already in $V_i$? Does that mean, there is only one message per value getting $m$ signatures on the system? Is that what Lamport means, when they prove that a Lieutenant knows when there are no more messages because there can only be one form of each?

Any tips and help is much appreciated!


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.