4
$\begingroup$

I've stumbled at the first OralMessage algorithm in Lamport, et al's paper.

I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping me.

Lamport claims the algorithm can handle (n-1)/3 traitors, and works when the commander is a traitor.

My restatement of the algorithm:

  1. The commander sends a value to each of the lieutenants.(round 0)

  2. Each lieutenant: forwards each message he receives to the other lieutenants:
    don't forward messages that already have your name (eg you are b and receive 'cb1')
    don't forward messages if they already have (N - 1)/3 names. (eg N=10 and you receive 'gcd0')
    add your name to front of message before forwarding (eg you are b and receive 'c0', send 'bc0')

  3. after all messages have been sent, each lieutenant:
    examines the received messages and makes their decision.
    if its a tie, then decide 0.

    I'm not sure how to do 3, the paper says the algorithm "assumes a sequence of [majority] functions" (nested?)
    In the example, I'm assuming to take the majority in each vector of round 2 (ie left to right), and then take the majority of these.

EXAMPLE

Commander is a traitor, N=7, M=(7-1)/3=2, so 6 lieutenants one of whom is a traitor. I have assigned the lieutenants letters b-g.

Here are the messages received at each node in rounds 1 & 2, assuming a node can send to itself. (the messages in brackets are redundant from B's point of view. I don't know if this is important.):

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >
<(beX),ceX  ,deX  ,     ,feX  ,geX  >
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >

Note:
'dc0' is sent to everyone by 'd' (because 'd' was the last to prepend their name)
'X' indicates an unreliable message. 'e' is a traitor and always sends unreliable messages

BUT 'step 3' gives 1,0,0,X,1,1 which is no better than round 1.
AND the majority of these is 1 if X is 1, and 0 if X is 0. So the traitor can confound us.

What am I doing wrong?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ interestingly/related, this "byzantines generals" is the same problem "solved" by the bitcoin protocol.... note there may be some expertise on this on Cryptography or Bitcoin $\endgroup$
    – vzn
    Commented Mar 6, 2014 at 17:26
  • $\begingroup$ In your example, which lieutenant is the traitor and which lieutenant are you considering? $\endgroup$
    – hengxin
    Commented Mar 7, 2014 at 13:53
  • $\begingroup$ A more comprehensible explanation of synchronous Byzantine General problem can be found in James Aspnes, Yale, CS465 Course notes. I find it easier to understand this algorithm by "unfolding" its recursion in term of "Exponential Information Gathering" (EIG) and then proving its correctness recursively. $\endgroup$
    – hengxin
    Commented Mar 8, 2014 at 12:17
  • $\begingroup$ @hengxin I've cleaned the question so hopefully it is a bit clearer. EIG is basically what I'm doing, except (1) I'm using a table instead of a tree (2) I 'prepend' at the send stage instead of 'appending' at the receive stage. I'm assuming all messages sent and received. My problems are I'm not sure I've got the algorithm correct. And the value I get at the end doesn't seem useful. $\endgroup$
    – mattrix
    Commented Mar 9, 2014 at 6:25
  • $\begingroup$ I have checked your example but found noting wrong. Here is my current opinion: your understanding is not wrong; it is not done yet. The specification (correctness) of IC1 is that "All loyal lieutenants obey the same order". $1,0,0,X,1,1$ seems not good for lieutenant $b$. BUT, it does not matter. Any other loyal lieutenant will get the same vector of $1,0,0,X,1,1$ (see the last paragraph of the proof of Theorem 1). That is to say, $X$ will be the same for all loyal lieutenants and the agreement is still satisfied. Please check another loyal lieutenant besides $b$ and let me know. $\endgroup$
    – hengxin
    Commented Mar 9, 2014 at 8:09

1 Answer 1

Reset to default
2
$\begingroup$

----I'm not sure if this should be my answer. Many thanks to hengxin. It does explain my confusion, and may be helpful to others seeing the question----

I failed to realise that there are 2 types of unreliable messages,
- some are different for each lieutenant, (eg 'eX' in round 1)
- others are the same for all lieutenants (I will denote these as 'S')

the amended example is,

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >  

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>   1  
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >   0  
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >   0  
<(beS),ceS  ,deS  ,     ,feS  ,geS  >   S  
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >   1  
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >   1

now the result from 'round 2' is different to 'round 1', and allows agreement.
however, we could have acheived the same result with:

<(b1) ,c0   ,d0   ,eX   >  

<     ,(cb1),(db1),(ebX)>   1  
<(bc0),     ,dc0  ,ecX  >   0  
<(bd0),cd0  ,     ,edX  >   0  
<(beS),ceS  ,deS  ,     >   S

Remember we have a traitor commander, but it seems more than coincidence that there is 1 traitor lieutenant out of 4 lieutenants (3t+1)?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.