Two generals' agreement

I am trying to figure an agreement protocol on an unreliable channel. Basically two parties (A and B) have to agree to do something, so it's the two generals' problem.

Since there is no bullet-proof solution, I am trying to do this.

A continuously sends a message with sequence 1
When B receives seq 1 it continuously replies with sequence 2
At this point A receives seq 2 so it starts sending seq 3
...

My question. When can the two parties conclude that they can take the action ? Obviously I can't set a condition: "do it after receiving 10 messages" since the last sender won't have any certainty that message 10 arrived - back to square one.

How about another idea:

Keep communicating like this for a predefined amount of time. At the end of that period both parties have an idea about the reliability of the channel. Would that be acceptable ?

回答1:

This java code demonstrates that there is a reasonable solution to the two generals problem that minimizes both messenger lives risked and time taken to transfer the message. Given a reasonable amount of time, 99.9 repeated % certainty is reached. The worst case is an infinitely small chance that the generals spend infinite time sending messengers to the other across the dangerzone indicating that they are not yet sure, all messengers intercepted. In this worst case, most of the time the two generals know an agreement has not been reached. There is a tiny chance that they were unlucky and one general commits while the other hesitates.

There is a definite end-point to the algorithm where each general can be 99.(variable number of nines) percent certain the other will commit. It is based on how much time is selected for silence indicating commitment. The number of messenger lives risked is minimized.

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;
    }
}

Result, and kinda Pseudocode:

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.

This algorithm will always result in 99.(certain number of nines) repeated percent sure for each general that the other will be there. The only way it can fail is if all messengers are always intercepted and the two generals spend infinite time sending messengers across an impassable danger zone.

All it takes is for one messenger to get through and boom, notification is achieved and silence is used as a the bi-directional confirmation for both to commit.

The number of assets or "lives" risked is between 3 and 8 given a 50/50 chance of making it through the danger zone.

回答2:

You can add reliability by saving the current state of all sequences IDs that were sent (something like a calculation of a hash function or 3DES calculation or even a PKI certificate per message - the latter would cost a lot...). The 2 generals problem cannot be solved, but with more information about the problem, I think I can give you a better answer...

BTW, no matter how much time would you send message, the reliability problem would stay event after 100 hours (the probability of a bad occurance will decrease, though). That means maybe you need a third object C, that knows A and B, and can be a kind of a witness for the communication (something like PKI that I've mentioned).