Two generals' agreement

Question

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 ?

Crowberry

Could be that you will get better responses on security.stackexchange.com – Capper

@Capper I don't think it's about security, it's more about reliability. – Crowberry

It's the same line of thinking. And an "agreement protocol on an unreliable channel" is a) common requirement for security protocols, b) something that has been solved before. – Capper

@Capper You seem to have a solution for this. Would you answer If I moved this over to security.se :-) ? – Crowberry

What are they agreeing to do? – Collaboration

@Collaboration It could be anything. In this case both have to send two entities that must meet. – Crowberry

How about A keeps on sending its entity to B. Then B processes both entities or sends them on to their final destination. B then repeatedly sends an 'OK' message back to A, for t seconds. If, after this time, B receives the same entity again (i.e. the OK message never got through to A), B sends the 'OK' for another t seconds. And so on. This will work as long as the entity is not expensive to send. – Collaboration

@Collaboration That entity could be something like a rocket. – Crowberry

In the conceptual General's Problem, yes. I'm not trying to solve that, because we can't. Hence why we need to know what your actual problem is. – Collaboration

@Collaboration Actually you don't need to know / do anything. I am just asking how to add reliability to the communication. – Crowberry

@Collaboration My last comment might have seemed harsh. Please understand I am looking for a general (sic) solution. Also, downvoting someone with 3 rep is pretty useless :-) – Crowberry

No worries. I hope someone can help you. – Collaboration

Answer 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.

Rating

This seems like it will fail in the case where Patton's messenger gets through before all subsequent messengers fail. Bradley has no way to know his messenger failed to reach Patton and erroneously assumes the subsequent silence means confirmation. Patton never receives Bradley's confirmation, and will send 99 more messengers that won't reach Bradley. Patton's not committed, while Bradley is. – Ehman

Answer 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).

Kirovograd

If there is no more information, than I'll give an analysis: for every successful message the probability of a bad occurance decreases, since the probability of a bad occurance is 0.5^t (good/bad), t is the number of messages passed through the given period. One more thing: you can set a reasonable timeout between A and B, and that will increase the probability of revealing a good occurance (meaning decreasing the prob. of a bad occurance). From your data, I don't know whether you can use a timeout. If timeout passes, it means initialization of communication. – Kirovograd