Having just read through Lamport's paper, I was hoping someone could clarify a few things on the Oral and Signed message algorithms.
- 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?
- 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!