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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
הצבאות A1, A2 צרים על העיר B

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

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

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

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