synchronization - 两将协议(protocol)

Question

我正在尝试在不可靠的 channel 上制定协议(protocol)协议(protocol)。基本上两方(A 和 B)必须同意做某事，所以它是 two generals' problem .

由于没有防弹解决方案，我正在尝试这样做。

A 连续发送一条序列为 1

的消息

当 B 收到 seq 1 时，它会不断回复序列 2

此时 A 收到 seq 2 所以它开始发送 seq 3

...

我的问题。双方何时可以断定他们可以采取行动？显然，我不能设置条件:“在收到 10 条消息后执行”，因为最后一个发件人无法确定消息 10 是否到达 - 回到第一格。

另一个想法怎么样:

在预定的时间内保持这样的沟通。在那个时期结束时，双方都对 channel 的可靠性有了一个想法。那可以接受吗？

Answer 1

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

该算法有一个明确的终点，其中每个将军可以是 99.(可变的九)百分比确定另一个将提交。它基于为表示 promise 的沉默选择了多少时间。使冒着生命危险的信使数量降至最低。

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)重复百分比确定每个将军另一个将在那里。它可能失败的唯一方法是，如果所有的信使总是被拦截，并且两位将军花费无限的时间将信使发送到无法通过的危险区域。

只需要一个信使通过并繁荣，实现通知，沉默被用作双方提交的双向确认。

冒着风险的 Assets 或“生命”的数量在 3 到 8 之间，有 50/50 的机会使其通过危险区。