החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון ספטמבר 1995, עמודים 49-55

לא ניתן לעשות שימוש מסחרי בחומר זה ללא רשות בכתב מן המחברים או מערכת כתב העת

הגנרלים הביזנטיים

צוות מגוון – מחקר ופיתוח בהוראת מדעי המחשב

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

תודה לפרופ' עזריה פז על הרעיון למדור, ולפרופ' מיכאל רבין על ההצעה לטפל במקרה של 4 גנרלים.

תודה לפרופ' בני שור, רינת חדשי, יעל אברבנאל, שולי וינטר ואופיר רחמן על הסיוע בכתיבת המאמר.

 

מבוא

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

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

 

בעיית ההסכמה במערכת מבוזרת

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

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

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

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

 

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

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

 

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

 

תאור הבעייה במונחים מטפוריים

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

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

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

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

 

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

 

בעיית הגנרלים הביזנטיים

מפקד צריך לשלוח פקודה ל- (N-1)  סגניו, כך שתתקיימנה שתי הדרישות הבאות:

[IC1] כל הסגנים הנאמנים יבצעו את אותה הפקודה בדיוק.

[IC2] אם המפקד נאמן, אזי כל הסגנים הנאמנים יצייתו לפקודה ששלח.

 

הערה: ברור שאם המפקד הוא נאמן, אז [IC1] נובע ישירות מ-[IC2]. אבל לא ניתן להסתמך על כך כיון שהמפקד יכול להיות גם בוגד.

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

 

פתרון שגוי

אחד הפתרונות שיכולים לעלות במחשבה ראשונה, הוא: "שְאל כל אחד מהגנרלים, מה היתה ההודעה המקורית שקיבל מהמפקד. אם תקבל רוב של תשובות זהות, תוכל לפעול לפיו."

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

 

פרוטוקול לפתרון בעיית הגנרלים הביזנטיים

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

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

 

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

 

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

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

 

הפרוטוקול לפיו יתנהגו הגנרלים הוא זה:

א.      לאחר שקיבלת את ההודעה המקורית מהמפקד, שלח לכולם את ההודעה שקיבלת.

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

 

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

 

מדוע האלגוריתם עונה על הבעייה?

נבחין בין שני מקרים: במקרה הראשון נניח שהמפקד הגון (ואחד הסגנים בוגד) ובמקרה השני נניח שהמפקד בוגד (וכל סגניו נאמנים).

 

מקרה ראשון: המפקד הגון

הואיל והמפקד הגון, הוא מעביר הודעה זהה (x) לכל סגניו.

נניח שסגן א' הוא הבוגד. לפיכך, הוא ישלח הודעות סותרות: הודעה y לסגן ב' והודעה z לסגן ג' (x¹y).

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

סגן ב' קיבל את ההודעה x מהמפקד והודעה נוספת x מסגן ג'. לכן הוא קיבל שני x-ים ולא חשוב מה ישלח לו א'.

באופן דומה גם סגן ג' מקבל שני x-ים.

מסקנה: הסגנים הנאמנים ב' וג' יחליטו על x ששלח המפקד והסגן הבוגד א' לא יצליח לגרום להם להגיע להחלטה שגויה.

 

 

מקרה שני: המפקד בוגד

הואיל והמפקד בוגד, הוא יכול לשלוח הודעות שונות לכל אחד משלושת סגניו. כלומר, הוא ישלח 3 הודעות  x1 x2 x3  שאינן זהות בהכרח.

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

 

נניח שהמפקד שלח את הערך x1 לסגן א', את הערך x2 לסגן ב', ואת הערך x3 לסגן ג'.

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

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

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

 

 
גרסאות שונות לבעיית ההסכמה

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

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

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

בכל הפרוטוקולים ההסתברותיים יש שימוש בזריקת מטבעות וההבדלים ביניהם נובעים מאופן השימוש במטבעות.

התרומה העיקרית של הפתרון ההסתברותי של רבין היתה בהמחשת היעילות של "מקור לאקראיות" הניתן לצפייה על-ידי כל המשתתפים. בהנחה שקיימת פרוצדורה כזו של זריקת מטבעות COIN TOSS, הפרוטוקול של רבין (עבור מערכת סינכרונית ובתנאי ש- n>=8t+1, כאשר n הוא מספר המשתתפים ו- t הוא מספר הבוגדים), מאפשר להגיע להסכמה ביזנטית בזמן קבוע!

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

 

מטפורת הגנרלים והשפעתה על בעיית ההסכמה המבוזרת

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

כך, למשל, ההסכמה האלבנית עוסקת במועד ההתקפה והיא מושגת אם מתקיימים שני התנאים הבאים:

[IC1D] כל הגנרלים הנאמנים תוקפים בהפרש של 10 דקות זה מזה לכל היותר.

[IC2D] אם המפקד נאמן, אזי כל הגנרלים הנאמנים תוקפים בהפרש של 10 דקות לכל היותר מהזמן שניתן בפקודה.

 

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

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

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

 

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

 

נספח: הפרוטוקול של רבין לבעיית ההסכמה הביזנטית

1.      Procedure RABIN AGREEMENT (vote) :

2.      low ¬ ën/2û + t + 1

3.      high ¬ ën/2û + 2t + 1

4.      do forever

5.      broadcast vote

6.      receive votes from all processors

7.      Let majority value be that value occurring most frequently in the votes received

8.      Let tally be the number of occurrences of majority value

9.      coin ¬ COIN TOSS

10.    if  coin=1

11.                       then threshold ¬ low

12.                       else  threshold ¬ high

13.    if  tally ³ threshold

14.                       then vote ¬ majority value

15.                       else vote ¬ 0

16.    if  tally ³ n-t  then decide majority value 

17.    od


מקורות:

1.      Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols. In Proc. 2nd Annual ACM Symp. Principles Distributed Computing, pp. 27-30.

2.      Chor, B., Dwork, C. (1989). Randomization in Byzantine Agreement. In Advances in Computing Research, Vol. 5, Randomness and Computation (Micali  S. ed.), pp. 443-498.

3.      Dolev, D. (1982). The Byzantine Generals Strike Again. In Journal of algorithms 3, pp. 14-30.

4.      Lamport, L., Shostak, R., Pease, M. (1982). The Byzantine Generals Problem. In ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, pp. 382-401.

5.      Pease, M., Shostak, R., Lamport, L. (1980). Reaching Agreement in the Presence of Faults. In JACM, Vol. 27, No. 2, pp. 228-234.

6.      Rabin, M. (1983). Randomized Byzantine Generals. In Proc. 24th Annu. Symp. Foundations Computer Sci, pp. 403 - 409.

 


אתר הבטים

תוכן לפי נושאים

תוכן לפי גליונות

גליון ספטמבר 95

חזרה לתחילת העמוד