两位将军协议

Question

我正在尝试在不可靠的通道上制定一个协议。基本上两方（A 和 B）必须同意做某事，所以这是两位将军的问题< /a>.

由于没有万无一失的解决方案，我正在尝试这样做。

• A 连续发送序列 1 的消息
• 当 B 收到 seq 1 时，它连续回复序列 2
• 此时 A 收到 seq 2 因此它开始发送 seq 3
• ...

我的问题。双方什么时候可以断定可以采取行动？显然我无法设置一个条件：“在收到 10 条消息后执行”，因为最后一个发件人无法确定消息 10 是否已到达 - 回到第一个方块。

另一个想法怎么样：

• 在预定的时间内保持这样的沟通。在此期间结束时，双方都会了解该渠道的可靠性。这样可以接受吗？

Answer 1

这段java代码表明，对于两将军问题有一个合理的解决方案，可以最大限度地减少信使的生命风险和传输消息所花费的时间。在合理的时间范围内，重复确定性达到 99.9%。最坏的情况是，将军们花费无限的时间向对方发送信使穿过危险区域，表明他们还不确定，所有信使都被拦截，这种可能性是无限小的。在这种最坏的情况下，两位将军大多数时候都知道尚未达成协议。他们很可能不走运，其中一位将军做出了承诺，而另一位将军则犹豫不决。

该算法有一个明确的终点，其中每个将军可以有 99%（99 的数量可变）确定其他将军会承诺。它取决于选择多少时间来表示承诺的沉默。信使面临生命危险的人数被最小化。

import java.util.*;
public class Runner{
    public static void main(String[] args) {
        ArrayList<String> coordinated = new ArrayList<String>();
        int fails = 0;

        for(int x = 0; x < 1; x++){
            General a = new General("Patton");
            General b = new General("Bradley");
            a.coordinateAttack(b, "9:00");

            System.out.println("livesRisked = '" + (a.livesRisked + b.livesRisked) + "'");
            System.out.println("" + a.attackIsCoordinated  + b.attackIsCoordinated);

            if (a.attackIsCoordinated == false || b.attackIsCoordinated == false)
                fails++;
        }

        System.out.println("failed " + fails + " times");
    }
}

class General{
    public String name;
    public boolean attackIsCoordinated;
    public int livesRisked;
    public General(String name){
        this.name = name;
        livesRisked = 0;
        attackIsCoordinated = false;
    }
    public void coordinateAttack(General otherGeneral, String time){
        System.out.println("General " + name + " intends to coordinate the attack with General " + otherGeneral.name + " at " + time);
        System.out.println("");

        int tryThisManyTimes = 100;
        for(int x = 1; x <= tryThisManyTimes; x++){

            if (attackIsCoordinated == false){
                System.out.println(name + " will try " + tryThisManyTimes + " times, we still arn't sure, this is attempt number " + x);
                sendAMessageTo(otherGeneral, time);
            }
            else{
                System.out.println("General " + name + " has received a confirmation from " + otherGeneral.name + " and we are 100% certain the battle is coordinated");
                break;
            }
        }
        System.out.println("Patton is 100% sure Bradley is notified of the " + time + " attack.");
        System.out.println("Bradley is 100% sure Patton is notified of the " + time + " attack.");
        System.out.println("");
        System.out.println("This algorithm will always result in 100% assurance that each general commits to the attack and , ");
        System.out.println("is sure the other will join them.  The only way it can fail is if all messengers are always intercepted ");
        System.out.println("and the two generals spend infinite time sending messengers across an impassable dangerzone");
        System.out.println("");
        System.out.println("Given infinite time, it will always result in complete accuracy.");
        attackIsCoordinated = true;
    }
    public void sendAMessageTo(General general_to_send_to, String time){
        Random r = new Random();
        boolean madeItThrough = r.nextBoolean();
        livesRisked++;
        System.out.println("General " + name + " sends a soldier with a message across the dangerzone to " + general_to_send_to.name);
        if (madeItThrough)
            general_to_send_to.receiveMessage(this, time);
        else
            System.out.println(name + "'s messenger was intercepted!  Blast!  Life used up with no results!");
    }

    public void sendConfirmation(General general_to_send_to, String time){
        Random r = new Random();
        System.out.println(name + " is risking a life to tell " + general_to_send_to.name + " we will comply.");
        boolean madeItThrough = r.nextBoolean();
        livesRisked++;
        if (madeItThrough)
            general_to_send_to.receiveConfirmation(this, time);
        else
            System.out.println(name + "'s confirmation messenger was intercepted, but we don't know that, we know " + general_to_send_to.name + " will continue to send us messengers until he is 100% sure.");
    }
    public void receiveMessage(General general_who_sent_it, String time){
        attackIsCoordinated = true;
        System.out.println("Messenger made it!!  As agreed, General " + name + " is notified and commits 100% to the attack at " + time);
        sendConfirmation(general_who_sent_it, time);
    }
    public void receiveConfirmation(General general_who_sent_it, String time){
        System.out.println("Messenger made it!!  General " + name + " has received confirmation from " + general_who_sent_it.name + ", therefore we know he's committed 100% to the attack and we don't need to keep sending messengers.");
        attackIsCoordinated = true;
    }
}

结果，有点伪代码：

General Patton intends to coordinate the attack with General Bradley at 9:00

Patton will try 100 times, we still arn't sure, this is attempt number 1
General Patton sends a soldier with a message across the dangerzone to Bradley
Patton's messenger was intercepted!  Blast!  Life used up with no results!
Patton will try 100 times, we still arn't sure, this is attempt number 2
General Patton sends a soldier with a message across the dangerzone to Bradley
Messenger made it!!  As agreed, General Bradley is notified and will commit to
    the attack when he is certain, Bradley is not certain yet.
Bradley is risking a life to tell Patton we will comply.
    Bradley Messenger made it!!  General Patton has received confirmation from Bradley, 
    therefore Patton knows he's committed 100% to the attack and we don't need 
    to keep sending messengers.  Silence means I'm 100% sure.
General Patton has received a confirmation from Bradley and we are 100% 
    certain the battle is coordinated
    Bradley receives no additional messages from Patton, and the silence is used to
    mean Patton is 100% certain, the amount of time passed is so great that the
    odds of all messengers being intercepted approaches zero.

Patton is 99.9 repeated % sure Bradley is committed to the 9:00 attack.
Bradley is 99.9 repeated % sure Patton is committed of the 9:00 attack.

这个算法总是会得到 99。（一定数量的 9）重复百分比确定每个将军都会有另一个将军。唯一可能失败的方法是，如果所有信使总是被拦截，并且两位将军花费无限的时间发送信使穿过无法逾越的危险区域。

所需要的只是一个信使打通并发出通知，并使用沉默作为双方承诺的双向确认。

如果有 50/50 的机会穿越危险区域，则面临风险的资产或“生命”数量在 3 到 8 人之间。

Answer 2

您可以通过保存已发送的所有序列 ID 的当前状态来增加可靠性（类似于哈希函数的计算或 3DES 计算，甚至每条消息的 PKI 证书 - 后者会花费很多......）。 2个将军问题无法解决，但是有了有关该问题的更多信息，我想我可以给你一个更好的答案...

顺便说一句，无论你发送消息多少时间，可靠性问题都会在100小时后持续发生（不过，发生不良情况的可能性会降低）。这意味着您可能需要第三个对象 C，它知道 A 和 B，并且可以成为通信的见证人（类似于我提到的 PKI）。