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

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

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

כלומר בעיה זו מכילה שני אתגרים עיקריים:

מהימנות המידע - שתוכן המידע שנשלח אכן הגיע בשלמותו ולא שונה בדרכו אל היעד, והגיע מהמקור הרצוי.

אישור הגעת המידע - שהמידע אכן הגיע לצבא השני.

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

הבעיה הוצגה לראשונה בשנת 1975 בצורה של שתי קבוצות גנגסטרים המנסות לתאם פעילות.

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

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

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

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

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

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

 קישורים חיצוניים 
 דעת יפה, פוסט בנושא באתר "מבוא לכלכלה – ג"


הערות שוליים

קטגוריה:ניסויים מחשבתיים
קטגוריה:תקשורת מחשבים