בעיית שני הצבאות

הצבאות A1, A2 צרים על העיר B

בעיית שני הצבאות (נקראת גם בעיית ההתקפה המתואמת או בעיית שני הגנרלים) היא בעיה קלאסית בתחום החישוב המבוזר המציגה את הבעייתיות בתקשורת על גבי ערוץ לא אמין.

הבעיה עוסקת בשני צבאות הצרים על עיר אחת. העיר חזקה מכל אחד מהצבאות בנפרד, אך לא משניהם גם יחד. לכן, על מנת לנצח, על שני הצבאות לתקוף את העיר בעת ובעונה אחת. שני הצבאות מסוגלים לתקשר באמצעות שליחים בלבד, אך אלה עשויים להיתפס על ידי שומרי העיר, כך שהצבא אשר שלח אותם אינו מסוגל לדעת האם הודעתו הגיעה ליעדה או לא.

ניתן להוכיח שאין כל שיטה אשר תאפשר לאחד הצבאות לצאת להתקפה בוודאות מוחלטת שהצבא השני יצא להתקפה בו זמנית.


הוכחה שאין פתרוןעריכה

כיצד? • נניח בשלילה שיש אלגוריתם, ונריץ T סיבובים (אם האלגוריתם קצר מדי, נוסיף הודעות ריקות).

Ei−1 vv1 Ei or Ei−1 vv2 Ei

• נניח שכל 2 הרצות עוקבות דומות (ע”פ האבחנה) כלומר לכל {k, ...., 1 ∈ {i:

• נשים לב שחובה שיהיה validity ,ואנו נוכיח (בה”כ):

– E0 ־ בה כל הקלטים הם 0 + כל ההודעות מגיעות לכן פולט 0

– וEk בה כל הקלטים הם 1 + כל ההודעות מגיעות לכן נפלוט 1 ־ וזו סתירה

• נתחיל לצור רצף הרצות דומות:

– E0 שני הקלטים 0 ,כל ההודעות מגידות ־ מהvalidity : יפלטו שניהם 0) הסכמה)

– E1 : עדיין שהקלטים הם 0 ־אחרת ישימו לב להבדל ־ ונאמר שההודעה האחרונה של v, נפלה באמצע הדרך ־ כעת מבחינת u הכל זהה, כי הוא שלח את ההודעה שלו, ואמנם הוא לא קיבל הודעה, אבל אין לו איך להודיעה על כך ל v E0 vu E1 ⇐ – E2 :עדיין הקלטים הם 0, כעת נוריד גם את ההודעה האחרונה ששלח u) בנוסף להודעה של vשלא הגיעה), וכעת E1 vv E2 – נמשיך כך עד הריצה E2T בה אין הודעות בכלל, וכפי שהראנו E2T v ... v E1 v E0

– כעת בגלל שאין הודעות, גם לא משנה מה הקלטיםלכן נוכל להגדיר:

E2t vu E2t+1 ועדיין vin = 1 E2t+1ב∗

E2t+1 vv E2t+2 ועדיין uin = 1 E2t+2ב∗

11 – כעת בהדרגתיות נתחיל להחזיר הודעות, עד שנגיע ש 1 = uin = vin וגם כל ההודעות מגיעות ומה-validity, שניהם יפלטו 1 וכאן הגענו לסתירה, כנדרש

  ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.