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