1
$\begingroup$

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!

$\endgroup$

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.