Return to Question

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 leutenants.(round 0)

2. Each leutenant: forwards each message he receives to the other leutenants:
   don't forward messages that already have your name (eg you are b and receive 'cb1')
   dont 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 leutenant:
   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 leutenants one of whom is a traitor. I have assigned the leutenants 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?

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?

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 leutenants.(round 0)

2. Each leutenant: forwards each message he receives to the other leutenants:
   don't forward messages that already have your name (eg you are b and receive 'cb1')
   dont 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 leutenant:
   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 leutenants one of whom is a traitor. I have assigned the leutenants 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 they were 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'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 leutenants.(round 0)

2. Each leutenant: forwards each message he receives to the other leutenants:
   don't forward messages that already have your name (eg you are b and receive 'cb1')
   dont 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 leutenant:
   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 leutenants one of whom is a traitor. I have assigned the leutenants 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?

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 leutenants.(round 0)

2. Each leutenant: forwards the messages he receives to the other leutenants:
   don't forward messages that already have your name (eg you are b and receive 'cb1')
   dont 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 leutenant:
   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?)

EXAMPLE

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

Here are the messages received at a node in rounds 1 & 2, (the messages in brackets are redundent 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  ,     >

I'm assuming to take the majority in each vector of round 2 (ie left to right), and then take the majority of these.
BUT that 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'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 leutenants.(round 0)

2. Each leutenant: forwards each message he receives to the other leutenants:
   don't forward messages that already have your name (eg you are b and receive 'cb1')
   dont 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 leutenant:
   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 leutenants one of whom is a traitor. I have assigned the leutenants 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 they were 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?