Lamport's Byzantine Generals Algorithm 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:


The commander sends a value to each of the lieutenants.(round 0)
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')
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 &amp; 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.):

&lt;(b1) ,c0   ,d0   ,eX   ,f1   ,g1   &gt;

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


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?
----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,

&lt;(b1) ,c0   ,d0   ,eX   ,f1   ,g1   &gt;  

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


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

&lt;(b1) ,c0   ,d0   ,eX   &gt;  

&lt;     ,(cb1),(db1),(ebX)&gt;   1  
&lt;(bc0),     ,dc0  ,ecX  &gt;   0  
&lt;(bd0),cd0  ,     ,edX  &gt;   0  
&lt;(beS),ceS  ,deS  ,     &gt;   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)?