2
$\begingroup$

Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in n generals.

I perfectly understand why for n=4, m=1 there is consensus trough a majority vote. Lets suppose (like in Leslies proposal) there are three type of messages for different attack time (A1, A2, A3). If no majority is reached the default action is retreat (r).

So even if the commander is a traitor and send different messages A1,A2,A3 to the three loyal lieutenants they will get (trough the recursive algorithm) to state (A1,A2,A3). In this case no majority is reached and the default action is taken (r). Thereby consensus is reached.

Leslie stated, that no consensus cannot be reached with n=3, m=1. Nonetheless if we apply the upper algorithm to the scenario with n=3, m=1 for the example that the commander is a traitor, isn't there the same consensus reached? The commander sends A1, A2 to the two loyal lieutenants, they both will reach the state (A1, A2) and thereby take the default option r. There is my mistake?

$\endgroup$
  • 1
    $\begingroup$ The original paper (of which Lamport is just one of the authors) contains a proof of impossibility in Section 2. Run this proof on your algorithm, and see what happens. $\endgroup$ – Yuval Filmus Jun 19 '18 at 14:44
  • $\begingroup$ I already read this paper. This is exactly where I'm stuck. In section 2 is stated that lieutenant 1 has to follow the attack command. But in the next section a default action is introduced. Furthermore in section 2 there is also no communication from lieutenant 1 to lieutenant 2. So from my point of view consensus can be reached if there is a default action (like in section 3) and a communication from lieutenant 1 to lieutenant 2. This is why I don't understand why no consensus can be reached for n=3, m=1 $\endgroup$ – j0hn Jun 19 '18 at 16:23
  • $\begingroup$ If the original paper is too hard to follow, try Ben-Ari's textbook Principles of Concurrent and Distributed Programming (Second edition). $\endgroup$ – Kai Jun 20 '18 at 10:06

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.