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

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

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

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

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

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