בעיית שני הצבאות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
עריכה |
|||
שורה 10:
== הוכחה שאין פתרון ==
כיצד?
• נניח בשלילה שיש אלגוריתם , ונריץ
Ei−1 vv1 Ei or Ei−1 vv2 Ei
• נניח שכל 2 הרצות עוקבות דומות (ע”פ האבחנה) כלומר לכל {k, ...., 1 ∈ {i:
• נשים לב שחובה שיהיה validity ,ואנו נוכיח (בה”כ):
–
• נתחיל לצור רצף הרצות דומות:▼
–
– E1 : עדיין שהקלטים הם 0 ־אחרת ישימו לב להבדל ־ ונאמר שההודעה האחרונה של v , נפלה באמצע הדרך ־ כעת▼
▲• נתחיל לצור רצף הרצות דומות:{{ש}}
– E0 שני הקלטים 0 ,כל ההודעות מגידות ־ מהvalidity : יפלטו שניהם 0) הסכמה){{ש}}
– E2 :עדיין הקלטים הם 0 , כעת נוריד גם את ההודעה האחרונה ששלח u) בנוסף להודעה של vשלא הגיעה) , וכעת▼
▲– E1 : עדיין שהקלטים הם 0 ־אחרת ישימו לב להבדל ־ ונאמר שההודעה האחרונה של v , נפלה באמצע הדרך ־ כעת מבחינת u הכל זהה, כי הוא שלח את ההודעה שלו, ואמנם הוא לא קיבל הודעה, אבל אין לו איך להודיעה על כך ל v
– נמשיך כך עד הריצה E2T בה אין הודעות בכלל, וכפי שהראנו E2T v ... v E1 v E0▼
▲E0 vu E1 ⇐ – E2 :עדיין הקלטים הם 0 , כעת נוריד גם את ההודעה האחרונה ששלח u) בנוסף להודעה של vשלא הגיעה) , וכעת E1 vv E2
– כעת בגלל שאין הודעות, גם לא משנה מה הקלטיםלכן נוכל להגדיר:▼
▲– נמשיך כך עד הריצה E2T בה אין הודעות בכלל, וכפי שהראנו E2T v ... v E1 v E0 {{ש}}
E2t vu E2t+1 ועדיין vin = 1 E2t+1ב∗▼
E2t+1 vv E2t+2 ועדיין uin = 1 E2t+2ב∗▼
▲– כעת בגלל שאין הודעות, גם לא משנה מה הקלטיםלכן נוכל להגדיר:{{ש}}
▲E2t vu E2t+1 ועדיין vin = 1 E2t+1ב∗ {{ש}}
▲E2t+1 vv E2t+2 ועדיין uin = 1 E2t+2ב∗ {{ש}}
11
– כעת בהדרגתיות נתחיל להחזיר הודעות, עד שנגיע ש 1 = uin = vin וגם כל ההודעות מגיעות
{{קצרמר|מדעי המחשב}}
| |||