信頼できないチャネルで合意プロトコルを見つけようとしています。基本的に二者（AとB）が何かをするのに同意しなければならないので、それは2人の将軍の問題です.
防弾ソリューションがないため、これを実行しようとしています。
私の質問。両当事者は、いつ行動を起こすことができると結論付けることができますか? 明らかに、条件を設定することはできません。「10 件のメッセージを受信した後に実行する」というのは、最後の送信者はメッセージ 10 件が到着したという確実性を持たないためです。振り出しに戻ります。
別のアイデアはどうですか：
この Java コードは、危険にさらされるメッセンジャーの命とメッセージの転送にかかる時間の両方を最小化する、2 つの将軍の問題に対する合理的な解決策があることを示しています。妥当な時間が与えられた場合、99.9% の繰り返しの確実性に達します。最悪のケースは、将軍が危険地帯を越えて他の人にメッセンジャーを送る無限の時間を費やして、すべてのメッセンジャーが傍受されたことをまだ確信していないことを示す可能性が非常に小さいことです. この最悪のケースでは、ほとんどの場合、2 人の将軍は合意に達していないことを知っています。彼らが不運で、一方の将軍がコミットし、もう一方の将軍が躊躇している可能性はわずかです。
アルゴリズムには明確な終点があり、各将軍が 99.(9 の可変数) パーセントで他の将軍がコミットする可能性があります。これは、コミットメントを示す沈黙のために選択された時間に基づいています。危険にさらされるメッセンジャーの数は最小限に抑えられます。
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) という結果になります。それぞれの将軍に対して、もう一方の将軍が存在することを確認するパーセントが繰り返されます。それが失敗する唯一の方法は、すべてのメッセンジャーが常に傍受され、2 人の将軍が通過不可能な危険ゾーンを越えてメッセンジャーを送信するのに無限の時間を費やした場合です。
必要なのは、1 つのメッセンジャーが通過してブームになるだけで、通知が行われ、両方がコミットするための双方向の確認として沈黙が使用されます。
危険にさらされる資産または「命」の数は、危険ゾーンを通過する可能性が 50/50 の場合、3 から 8 の間です。
送信されたすべてのシーケンス ID の現在の状態を保存することで、信頼性を高めることができます (ハッシュ関数の計算、3DES 計算、またはメッセージごとの PKI 証明書のようなもの - 後者には多くの費用がかかります...)。2 将軍の問題は解決できませんが、この問題についての情報があれば、より良い答えが得られると思います...
ところで、メッセージをどれだけ送信しても、信頼性の問題は 100 時間後に発生します (ただし、問題が発生する可能性は低くなります)。つまり、A と B を認識し、一種の通信の証人となることができる 3 番目のオブジェクト C が必要になる可能性があります (前述の PKI のようなもの)。