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

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

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

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

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

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

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

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

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

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

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

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

נניח ש-A1 שולח שליח ל-A2 עם ההודעה: "בואו נתקוף היום בחצות!". גנרל A1 אינו יכול לתקוף ללא אישור מגנרל A2. אם השליח מ-A1 הגיע, אז האלוף A2 שולח אישור עם ההודעה: "כן, בוא נמלא את הלבנים היום". אבל עכשיו גנרל A2 לא יודע אם השליח שלו הגיע או לא, אין לו ערובות אם ההתקפה תהיה בו זמנית. כעת גנרל A2 שוב זקוק לאישור.

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

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

הצגת הרעיון של מערכות מבוזרות

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

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

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

תכונות של מערכות מבוזרות

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

מודלים של תקשורת בין צמתים במערכות מבוזרות

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

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

מושג הקונצנזוס במערכות מבוזרות

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

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

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

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

מאפייני אלגוריתם הקונצנזוס

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

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

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

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

דוגמה לאיך פועל אלגוריתם הקונצנזוס

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

1. הכל מתחיל בהצעת נישואין (Propose). נניח שלקוח מתחבר לצומת שנקרא "צומת 1" ומתחיל טרנזקציה, מעביר ערך חדש לצומת - O. מעתה, נקרא "צומת 1" הצעה. איך המציע "צומת 1" צריך עכשיו להודיע ​​לכל המערכת שיש לו נתונים טריים, והוא שולח הודעות לכל שאר הצמתים: "תראה! קיבלתי את הערך "O", ואני רוצה לרשום אותו! אנא אשר כי תרשם גם "O" ביומן שלך."

   

2. השלב הבא הוא הצבעה עבור הערך המוצע (Voting). לשם מה זה? יכול לקרות שצמתים אחרים קיבלו מידע עדכני יותר, ויש להם נתונים על אותה עסקה.

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

   בכל מקרה אחר, הצמתים יכולים להגיב ל"צומת 1": "תשמע! יש לי נתונים עדכניים יותר על העסקה הזו. לא "אוי", אלא משהו טוב יותר."

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

3. אם סבב ההצבעה הצליח, וכולם היו בעד, אז המערכת עוברת לשלב חדש - קבלת הערך (Accept). "צומת 1" אוסף את כל התגובות מצמתים אחרים ומדווח: "כולם הסכימו על הערך 'O'! עכשיו אני מכריז רשמית ש"O" היא המשמעות החדשה שלנו, זהה לכולם! כתוב את זה במחברת שלך, אל תשכח. כתוב ליומן שלך!"

   

4. שאר הצמתים שולחים אישור (מקובל) שהם רשמו לעצמם את הערך "O", שום דבר חדש לא התקבל במהלך הזמן הזה (מעין commit דו-פאזי). לאחר אירוע משמעותי זה, אנו רואים שהעסקה המופצת הושלמה.
   

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

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

אלגוריתם קונצנזוס במערכת אסינכרונית

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

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

התשובה הנכונה והרציונל מאחורי הספוילר.התשובה הנכונה היא: 0. אם אפילו צומת אחד במערכת אסינכרונית יורד, המערכת לא תוכל להגיע לקונצנזוס. הצהרה זו מוכחת במשפט FLP הידוע (1985, פישר, לינץ', פטרסון, קישור למקור בסוף המאמר): "חוסר האפשרות להגיע לקונצנזוס מבוזר אם לפחות צומת אחד נכשל."

חבר'ה, אז יש לנו בעיה, אנחנו רגילים לזה שהכל אסינכרוני אצלנו. והנה זה. איך להמשיך לחיות?

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

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

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

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

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

אלגוריתם Paxos פותר בעיות קונצנזוס

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

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

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

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

תפקידים בפאקסוס

לאלגוריתם Paxos יש מושג של תפקידים. שקול שלושה עיקריים (ישנם שינויים עם תפקידים נוספים):

1. מציעים (ייתכנו גם מונחים: מנהיגים או רכזים). אלו הם החבר'ה שלומדים על איזו משמעות חדשה מהמשתמש ולוקחים על עצמם את תפקיד המנהיג. המשימה שלהם היא להשיק סבב הצעות לערך חדש ולתאם פעולות נוספות של הצמתים. יתרה מכך, Paxos מאפשרת נוכחות של מספר מנהיגים במצבים מסוימים.
2. מקבלים (מצביעים). אלו הם הצמתים שמצביעים לקבל או לדחות ערך מסוים. תפקידם חשוב מאוד, כי ההחלטה תלויה בהם: לאיזה מצב המערכת תעבור (או לא תעבור) לאחר השלב הבא של אלגוריתם הקונצנזוס.
3. לומדים. צמתים שפשוט מקבלים וכותבים את הערך המקובל החדש כאשר מצב המערכת השתנה. הם לא מקבלים החלטות, הם רק מקבלים נתונים ויכולים לתת אותם למשתמש הקצה.

צומת אחד יכול לשלב מספר תפקידים במצבים שונים.

מושג המניין

אנו מניחים שיש לנו מערכת של N צמתים. ורובם F צמתים עלולים להיכשל. אם צומת F נכשלים, אז אנחנו צריכים לפחות 2F+1 צמתי מקבל.

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

רעיון כללי של אלגוריתם הקונצנזוס של Paxos

אלגוריתם Paxos מניח שני שלבים גדולים, אשר בתורם מחולקים לשני שלבים כל אחד:

1. שלב 1א: הכנה. בשלב ההכנה מודיע המנהיג (המציע) לכל הצמתים: "אנחנו מתחילים שלב הצבעה חדש. יש לנו סיבוב חדש. המספר של סיבוב זה הוא n. נתחיל להצביע עכשיו". עד כה, הוא רק מדווח על תחילתו של מחזור חדש, אך אינו מדווח על הערך החדש. המשימה של שלב זה היא ליזום סבב חדש ולהודיע ​​לכל אחד על המספר הייחודי שלו. המספר העגול חשוב, הוא חייב להיות גדול מכל מספרי ההצבעה הקודמים מכל המנהיגים הקודמים. מכיוון שבזכות המספר העגול, צמתים אחרים במערכת יבינו עד כמה הנתונים של המנהיג טריים. כנראה לצמתים אחרים כבר יש תוצאות הצבעה מסבבים מאוחרים הרבה יותר ופשוט יגידו למנהיג שהוא בפיגור בזמן.
2. שלב 1ב: הבטחה. כאשר צמתי המקבל קיבלו את המספר של שלב ההצבעה החדש, שתי תוצאות אפשריות:
   • המספר n של ההצבעה החדשה גדול ממספר כל אחת מהקולות הקודמות שבהן השתתף המקבל. ואז המקבל שולח הבטחה למנהיג שהוא לא ישתתף עוד בהצבעות עם מספר קטן מ-n. אם המקבל כבר הצביע עבור משהו (כלומר, הוא כבר קיבל ערך כלשהו בשלב השני), אז הוא מצרף להבטחתו את הערך המקובל ומספר ההצבעה שבה השתתף.
   • אחרת, אם המקבל כבר יודע על ההצבעה עם מספרים גבוהים, הוא יכול פשוט להתעלם משלב ההכנה ולא להגיב למנהיג.
3. שלב 2א: קבל. המנהיג צריך להמתין לתגובה מהמניין (רוב הצמתים במערכת) ואם יתקבל מספר התגובות הנדרש, יש לו שתי אפשרויות להתפתחות אירועים:
   • חלק מהמקבלים הגישו ערכים שהם כבר הצביעו עבורם. במקרה זה, המנהיג בוחר את הערך מההצבעה עם המספר הגבוה ביותר. בואו נקרא לערך הזה x, ונשלח הודעה כזו לכל הצמתים: "קבל (n, x)", כאשר הערך הראשון הוא מספר ההצבעה משלב ההצעה שלו, והערך השני הוא מה שכולם התאספו לשם כך, כלומר. ערך שבשבילו, למעשה, אנחנו מצביעים.
   • אם אף אחד מהמקבלים לא שלח ערכים, אלא הם פשוט הבטיחו להצביע בסיבוב הזה, המנהיג יכול להזמין אותם להצביע בעד הערך שלהם, הערך שבגללו הוא בכלל הפך למנהיג. בואו נקרא לזה י. הוא שולח לכל הצמתים הודעה בנוסח: "קבל (n, y)", באנלוגיה לתוצאה הקודמת.
4. שלב 2ב: התקבל. יתרה מכך, הצמתים המקבלים, עם קבלת ההודעה "קבל (...)", מהמנהיג מסכימים איתה (שלח אישור לכל הצמתים שהם מסכימים עם הערך החדש) רק אם הם לא הבטיחו לחלק (אחר) את מנהיג להשתתף בהצבעה עם מספר הסיבוב n' > nאחרת הם מתעלמים מהנחיית האישור.

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

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

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

קישורים לחומרים להמשך לימוד

רמת מתחילים:

• כיצד פועל קונצנזוס מבוזר?, Preethi Kasireddy, מאמר בבלוג על Medium
• פאקסוס עשוי פשוט. באמת, עדי קנצ'רלה, כתבה בבלוג על מדיום
• מחשבות מבוזרותבלוג איתי אברהם
• סנכרון, אסינכרוני וסנכרון חלקי, איתי אברהם, מאמר בבלוג

רמת לסלי למפורט:

• חוסר אפשרות של קונצנזוס מבוזר עם תהליך אחד שגוי (חוסר אפשרות FLP)פישר, לינץ' ופטרסון, עבודת מחקר, 1985
• הפרלמנט במשרה חלקית, לסלי למפורט, עבודת מחקר, 1998
• פאקסוס עשוי פשוט, לסלי למפורט, עבודת מחקר, 2001

מקור: www.habr.com