בעיית שני הצבאות
בעיית שני הצבאות (נקראת גם בעיית ההתקפה המתואמת או בעיית שני הגנרלים) היא ניסוי מחשבתי המציג את הבעייתיות בתקשורת על גבי ערוץ לא אמין[1].
הבעיה עוסקת בשני צבאות או גנרלים הצרים על עיר. העיר חזקה מכל אחד מהצבאות בנפרד, אך לא משניהם יחד. לכן, על מנת לנצח, על שני הצבאות לתקוף את העיר בעת ובעונה אחת. שני הצבאות מסוגלים לתקשר באמצעות שליחים בלבד, אך אלה עשויים להיתפס על ידי שומרי העיר בדרכם לצבא האחר, והצבא ששלח אותם אינו מסוגל לדעת האם הודעתו הגיעה ליעדה או שונתה בדרך.
כלומר בעיה זו מכילה שני אתגרים עיקריים:
מהימנות המידע - שתוכן המידע שנשלח אכן הגיע בשלמותו ולא שונה בדרכו אל היעד.
אישור הגעת המידע - שהמידע אכן הגיע לצבא השני.
ניתן להוכיח שאין כל שיטה אשר תאפשר לאחד הצבאות לצאת להתקפה בוודאות מוחלטת שהצבא השני יצא להתקפה בו זמנית[2][3][4].
הבעיה הוצגה לראשונה בשנת 1975 בצורה של שתי קבוצות גנגסטרים המנסות לתאם פעילות[5].
יישומים ושימושים
[עריכת קוד מקור | עריכה]למרות שלא קיים פתרון לבעיה בצורתה המקורית, ניתן לפתור גרסה דומה עם הנחות מקלות, ובכך להציג פתרון הולם מספיק לבעיות בעולם האמיתי[6][7].
דוגמה לאחת מבעיות אלו היא תקשורת נתונים, אשר פרוטוקולים מסוימים (בדרך כלל בצורה אסינכרונית) פותרים בצורה חלקית.
כאשר משתמש ושרת מנסים לתקשר זה עם זה על גבי ערוץ לא מאובטח, המשתמש והשרת נמשלים לגנרלים המנסים לתקשר זה עם זה, בעוד שהערוץ הלא מאובטח נמשל למקום שבו נמצאת העיר.
מהימנות המידע ניתנת לפתרון במקרה זה אם נשתמש בהנחות מסוימות, דוגמה לאחת מהן היא שימוש בפרוטוקול דיפי-הלמן (ההנחה שהגנרלים החליפו מראש מפתחות ציבוריים), איתם יוכלו לתקשר באופן בטוח על גבי רשת לא מאובטחת[8][9][10].
במילים אחרות, ניתן לבצע הנחה מקלה שלצבאות קיים ידע מקדים מראש שהוא חסוי, מוגן ומהימן (כגון מפתחות פרטיים), אשר בעזרתו הם יכולים ליצור ערוץ תקשורת עם חשש זניח להאזנה או שינוי המסרים (בהינתן בחירת פרוטוקול איכותי).
אישור הגעת המידע ניתן גם לפתור על ידי הסכמה מראש על מספר קבלות אישור על הודעה שנשלחה, דוגמה לפרוטוקול כזה הוא פרוטוקול בקרת שידור (TCP)[11].
כלומר, ההנחה המקלה שמבצעים בדוגמה זו היא שקיימת מוסכמה אוניברסלית על מספר שליחות ואישורי קבלה חזרה שהצבאות יבצעו בעת קבלת/שליחת מסרים (כמו כן מה לעשות במידה ולא מתקבל מסר או במקרי קצה נוספים), ובכך להשיג סיכוי טוב להגעה וקבלה של המסר, או זיהוי של תקלות בהעברתו.
אלו לא פתרונות שמבטיחים את הגעת הפרטים או נכונותם בוודאות מוחלטת, הם רק מעלים את הסיכויים להגעת המסר ולמהימנות תוכנו, מה שיביא את הצדדים המתקשרים לביטחון טוב מספיק כדי להשתמש בערוץ התקשורת.
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- דעת יפה, פוסט בנושא באתר "מבוא לכלכלה – ג"
The Two Generals’ Problem, סרטון בערוץ "TomScott", באתר יוטיוב (באנגלית)
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ Michael Swift, Byzantine Generals, wisc.edu, UNIVERSITY of WISCONSIN-MADISON Computer Sciences Department, 15/03/2012 (באנגלית)
- ^ Two Generals and Time Machines, mwhittaker.github.io
- ^ Leslie Lamport, The Weak Byzantine Generals Problem, acm.org, Journal of the ACM, 01/07/1983
- ^ LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE, The Byzantine Generals Problem, lamport.azurewebsites.net, ACM Transactions on Programming Languages and Systems SRI International, 03/07/1982 (באנגלית)
- ^ E. A. Akkoyunlu K. Ekanadham R. V. Huber, SOME CONSTRAINTS AND TRADEOFFS IN THE DESIGN OF NETWORK COMMUNICATIONS, State University of New York at Stony Brook, 1975
- ^ Seth Archer Brown, The Two Generals Problem, LinuxBlog.io, 2024-05-17 (באנגלית אמריקאית)
- ^ jakub, Two Generals’ Problem – Finematics, 2018-02-05 (באנגלית בריטית)
- ^ Discrete Logarithms and Diffie–Hellman, math.brown.edu, 20/03/2008
- ^ Ralph C. Merkle, Secure communications over insecure channels, Commun. ACM 21, 1978-04-01, עמ' 294–299 doi: 10.1145/359460.359473
- ^ W. Diffie, M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22, 1976-11, עמ' 644–654 doi: 10.1109/TIT.1976.1055638
- ^ Information Sciences Institute, University of Southern California, TRANSMISSION CONTROL PROTOCOL, ietf.org, September 1981