پروتكل‌های Roll-back Recovery در سيستم گذر دهی پيام

صفحه 1:
1 فصل 12 : برو تك لهاي ‎Roll-backRecovery‏ ‏در سيستم كذر دهي ييام درس طراحي سيتمهاي مطمئن 

صفحه 2:
چارچوب مطالب - @ ۴ تعاریف ۴ پروتکل‌هاي ‎checkpointing‏ ‏۴ پروتکل‌هاي بر مبناي واقعه‌نگاري ۴ مقایسه Rollback Fualt Tolerancy 

صفحه 3:
معدمه : امروزه سيستمهاي توزیع شده در همه جا موجود مي‌باشند و بدین سبب ما را قادر به انجام بسياري از کارها می‌نماید. سيستمهاي 50۳۷0۲ ۲1006) و ۱۷۷۷۷۷ و محاسبات علمي از جمله بسياري از آنها ميب " يتانسيل اين سيستمها به خاطر ۰ : تکنیکها شامل موارد زیر مي‌باشد: ‎Transactions 2‏ بر کابردهاي دده گرا مرک اد ‎Groupcommunications +‏ 0 انتزاعي از يك سيتم ارتباطي ايدهآل كه برنامه نویس مي‌تواند برنامهاش را بصورت مطمئن بر روي آن توسعه دهده ييشنهاد مي‌کند. ‎Roltback recovery 9‏ * بر روي کاربردهاي با مان اجراي طولاني تمرکزدر. ماد محاسات علمي و کابرهاي ارباطي ‎Rollback Fualt Tolerancy‏ 

صفحه 4:
مدل سیستم سیستم گذر دهي پیام (59056610 00551110 006550806) شامل تعداد ثابتي فرایند که بین آنها پیام رد و بدل مي‌شود. مي‌باشد. فرایندها براي اجراي برنامه كاربردي توزیع شده ضمن تعامل با جهان خارج با دریافت پیام ورودي و ارسال پیام خروجي: با هم همكاري مي‌کنند. Input message Output message, Outside wart Message-passing system Po 2 Figure 1. An example of a message-passing system with three proc ...سل ‎well‏ سوه سحن است بدليل لاكم لاكردن لأحللت لاموقت لأخود يا لأتوقف []اجرالابر للاساس لأمدل لاتوقف [أبه لأمحض لآخرلبى:لاد معرچار خرابي شود ‎Rollback Fualt Tolerancy‏ 

صفحه 5:
‎Rollback Recovery psgic‏ در سيستم‌هاي توزیع شده ‏*_ در سیستم فوق تحمل‌پذيري خطا با ذخیره حالت فرايندهاي سیستم در دوره‌هاي خاص. زمان اجراي عاري از خطا طبق سیاست معین. روي منبع ذخیره پایدار 500۳000 56060 و بازگشت به يكي از آن حالات هنگام بروز خرايي میسر مي‌شود. این کار سبب کاهش محاسبات از دست رفته مي‌شود. هر حالت ذخیره شده يك 66۵66001006 نام دارد. عملیات بازيافتي که فرایند به محض وقوع ‎Uns‏ ‏انجام مي‌دهد تا به يکي از این 10606۳01106) ها بازگشت نماید 26076۲۷ 0066))م مي‌گویند. 2 11600۷0۳۷ 1)060:66 با سیستم توزیع شده ب عون مجموعهواز فرلیندها که در طول‌شبکه با هودر ايتباط هسته يفتر مركت " بروتكلهاي ‎Kus 99 4 RollbackRecovery‏ تقسيم مىشوندة ‎Checkpoint-based 3‏ 7 ‏* 0 براي جلوكيري از هدر رفتن محاسبات و عملیات. بر روي هر فرایند در مواردي طبق سیاست خاص از وضعیت فرایند ۲666۳00108 گرفته مي‌شود. بسته به نحوه گرفتن 6666001108 به سه دسته هماهنگ, ناهماهنگ و وایسته به ارتباط تقسیم مي‌شود. ‏د ‎Cog-based‏ ‏علاوه بر مورد بالا رخدادهاي غيرقطمي فرايندها را نيز ثبت ميكند تا مقدار بيشتري از عمليات انجام شده را بازیافت نماید. بسته به نوع ثبت رخداد به سه فسته يذبرناتف وشبينانه. سببي تقسيم.موشوف ‎Rollback Fualt Tolerancy‏ ‎ ‎ 

صفحه 6:
چارچوب مطالب © ميمه " تعاريف * پروتكل‌هاي ‎checkpointing‏ ‏۴ پروتکل‌هاي بر مبناي واقعه‌نگاري * مقایسه مراجع Rollback Fualt Tolerancy 

صفحه 7:
حالت سازگار سراسري سیستم *_بدلیل انتقال پيام بین فرایندها در سیستم گاهي پیش مي‌آید که يك 6۵08۳018 نشان‌دهنده آن است که فرایند پيامي دريافت کرده. در حالي كه هيج 0866201816 از فرايند فيكرق : نشان‌دهنده ارسال آن پیام نیست. چنین پيامي را یتیم 000070 مي‌گویند. * در 1660۷6۳۷ به ترکیبی از ‎RoCCBack» 45 ls Checkpoint‏ بدست می‌آید. حالت سیستم مي‌گویند. . ۱ این حالت بدلیل وجود پیام یتیم به دو دسته تقسیم می‌شوند: "۲ حالتي كه در آن بيام يتيم وجود داشته باشد حالت ناسازكار 8006© 13160185656 نداشته باشد و يك اجراي درست را نشان دهد سازگار 60951516106 ۴ در ‎Gun Recovery‏ پیدا کردن تركيبي از 686600106 ها بطوري که حالت سازکار هآ محالنت ذر سیستم:مب‌باشد. سراسري سیستم را نشان دهد. و باز Rollback Fualt Tolerancy 

صفحه 8:
oa lee cen, | Inconsistent state Po > m 7 > Py () Figure 2. An example ofa consistent and inconsistent state ۳۳۲۲۲۲ EES e150 Rollback Fualt Tolerancy 

صفحه 9:
؟ مسیر 2 (مسیر زيگزاگي) دنباله خاصي از پیام‌ها است که دو 0606001106 را به هم متصل مي‌کند. ‎{m,,m,}, (m,m,}‏ * چرخه 2 مسیر 2 اي است که نقطه شروع و پایان آن یکی باشد. (بیای0] ؟ یک ‎checkpoint‏ درون چرخه 2 نمي‌تواند بخشي از یک حالت سازگار در سيستمي که فقط از ‎US ge ool checkpoint‏ باشد. ‎Z-cycle‏ Z-path Figure 3. An example execution and Z-paths. Rollback Fualt Tolerancy 

صفحه 10:
پيام‌هاي گذرا * وجود ‎play‏ گذرا بسته به لین است که کانال لّارتباطیلامن لاد لامدل سیستم فرض شده باشد يا له * فرض ارتباط لمن طراحي يروتكل را راحت ميكند اما يياده سازي را مشكل مي نمايد. User applications Reliable communication protocol Rollback-recovery protocol Unreliable communication channel 0 igure 4, Implementation of rollback-recovery (a) on top of a reliable communication protocol; (b) direetly on User applications Rollback-recovery protocol Reliable communication protocol Unreliable communication channel 6 top of unreliable communication channels, 40150 Rollback Fualt Tolerancy 

صفحه 11:
2 7 7 اطلاعات 0000600101۷۷۵ و وابستگی فرایندها ۴ در 0۵66۳00101۷08 هر فرایند حالت خود را به صورت دوره‌اي بر روي 6 6 فذخیره می‌کند. حللت ذخیره شده يك فرایند شامل اطلاعات كافي براي شروع مجدد آن فرایند مي‌باشد. در سیستم گذر دهي پیام بخاطر تبادل پیام بین فرایندها هنگام عملیات عاري از خطاء وابستگي ایجاد مي‌شود. به همین دلیل داراي ‎Rollback Recovery‏ پیچیده مي‌باشد. ۴ هر حللت سراسري سازگار از 60666001004 در سیستم مي‌تواند براي شروع مجدد فرایندها به محض وقوع خطا بکار رود. ۱ * مجموعه 0۵06(0016) هاي سراسري سازگار در سیستم يك خط ارجاع را تشکیل داده که به آن 11106 13660۷۵۲۷ گویند. لين خط هنگام ‎amie Recovery‏ و سیستم به آن حالت برمي‌گردد. Rollback Fualt Tolerancy 

صفحه 12:
۵ ۵0و09 ۲۲ ولثر دممینو ۴ فرایندها بسته به نیازشان هنگام اجرا با هم ارتباط برقرار مي‌کنند. بدینوسیله وابستگي بین آنها ایجاد مي‌شود. هنكام وقوع خرابي در يك يا چند فرایند. در زمان 10)]6006 . به خاطر وابستگي بین فرایندها علاوه بر فرايندي که در آن خرابي رخ داده. ممکن است سایر فرایندها نیز مجبور به شوند. ‎Rollback Propagation orn cy! a‏ 352 * حالت سراسري ساز كار ‎Rollback Propagation wlio checkpoint‏ ,| محدود نماید. * اگر در برخی سناريوهاي خرابی این ‎ue Rollback Propagation‏ به اين شود که همه فرايندها به حالت اوليه 055 ‎Domino Effect) guess ais Fy‏ ,€ داده است. وقوع اين يديده باعث از دست رفتن تمامي محاسبات قبل از خرابي گشته و سیستم را به حالتي که هیچ عملياتي انجام نداده بود مي‌برد. بدین جهت این پدیده نامطلوب است. Rollback Fualt Tolerancy 

صفحه 13:
براي اجتناب از اثر دومینو در سیستم. فرایندها باید 02060010011008» خود را بصورت هماهنگ انجام داده که سبب پیشرفت 106] 1660۷6۳۱ مي‌شود. يا اینکه عملیات ‎checkpointing‏ خود را با واقعه نگاري نگاري ترکیب کنند. Domino Effect Rollback = ‘Propagation Checkpoint Failure Figure $. Rollback propagation, recovery line and the domino efvet. Rollback Fualt Tolerancy 

صفحه 14:
9 ولثر دومینو * هنگامی که هر فرایند مستقلاً عملیات ‎checkpointing‏ را انجام دهد می‌تواند سبب پیدایش اثر دومینو شود( ‎checkpointing lle‏ ناهماهنگ) ‎ .‏ ۴ يكي از روشهايي که سبب مي‌شود عملیات 10006001018 هماهنگ انجام شود این است که سیستم در بعد وسیع حالت سازگار خود را ذخیره نماید. "" راه ديكر اينكه 006612011161118 بر مبناي ارتباط باشد. به اين معنى که هر فرايند را مجبور كند بر اساس اطلاعات سوار شده بر ييامهابي كه از فرايندهاي ديكر دریافت مي‌کند. 6۵۲ خود را بكيرد. 06۵66۳01 هایی که در کل سیستم به صورت سازگار گرفته شده‌اند. هميشه بر روي 516/6510۲86 وجود دارند. بنابراین از اثر دومینو اجتناب مي‌شود. Rollback Fualt Tolerancy 

صفحه 15:
تعامل با دنياي خارج يك سیستم گذردهي ‎pl‏ معمولا براي دریافت داده یا نشان دادن خروجي محاسبات با دنياي خارج در تعامل است. با اين تفاوت که اگر خرابي رخ دهد دنياي خارج نمي‌تواند به 110116006 تکیه نماید. © يتابراين بروتكلهاي 6 براي تعامل با دنياي خارج باید رفتار خاصي را بر كزيند. * قبل از ارسال خروجي به دنياي خارج ‎aS (le og piles gly places‏ خروجي از آن ارسال مي‌شود. علیرغم خرابي در آینده. قابل بدست آوردن ‎all, Casal‏ 5 صدور خروجی) ‏براي پيام‌هاي ورودی راه حل عبارت از ذخیره پیام ورودي بر روي ‎‘stable Storage‏ قبل از اينکه به برنامه كاربردي اجازه پردازش آن ‏داده شود. می‌باشد. ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 16:
Logging Protocolsvs. Checkpointing روش واقعه نگاري وقتي تعامل با دنياي خارج مکرر است. بیشتر استفاده مي‌شود. زیرا يك فرایند را قادر مي‌سازد اجرایش را تکرار کند و با لرسال خروجي به دنياي خارج بدون داشتن هزینه گران ‎checkpointing‏ قبل از ارسال خروجي سازگاري داشته باشد. Maximum recovgrable state ۱ Replay delivery to recov Orphan Pe - ١|“ message Py itficheckpointing ‏يم‎ ‎¢ ‎ins and mis lost upon failure Figure 6, Message logging for deterministic replay. Rollback Fualt Tolerancy 

صفحه 17:
ات 5۵6۲۵5:0۲ ۴ 6006260۷0۲۷])م از 50۲۵۵06 5۵6)6 بولی‌ذخیرم :20181 فرلیندهء ولقعه ن گايیو سایر لطاهاتمربوط به بازيابي ‎Collection ®‏ © ب ریپ اك کرد ن|طاهاتب_زيابیب لالستفادم ‎Gsly. checkpoint jib Lly)og oe‏ ‎Bic y Recovery line oo 5 a Garbage collection ly al)ch 3‏ ‏تمامي اطلاعات مربوط به رخدادهايي که قبل از آن خط رخ داد‌اند. مي‌باشد. ‏* اجراي الگوریتم خاص براي حذف اطلاعات بلا استفاده موجب سربار در ‏سیستم مي‌شود. ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 18:
۴ تعاریف Checkpornting ce In" ‏پروتكل‌هاي بر مبناي واقعه‌نگاري‎ * ‏مقایسه‎ * ۴ مراجع Rollback Fualt Tolerancy 

صفحه 19:
Sabali Checkpointing ۴ 066201111118 ناهماهنكبه هر فرليد اجانه بيشترينخود لستقلالیا بولیت صمیم‌گیریدر گرفتن/ 0606۳0011 میي‌هد. 9 مزیت آصلي این خود استقلالي عبارت از: * هر فرایند. 06۵660001008 خود را زماني که قادر است. مي‌گيرد. براي مثال يك فرایند مي‌تواند سربار ‎checkpointing l |,‏ در وقتی که قدار حالاتي ‎sas‏ 0 كوجك باشد. گاهش دهد 8 ار 5 5 ۴ _ احتمال وقوع اثر دومینو که سیب از دست دادن مقدار وسيعي از کار انجام شده مي‌شود. وجود دارد. فرایند ممکن است 20۵660010 بلا استفاده‌اي را که هرگز بخشی از يك حالت سازگار سراسري نخواهد بود.بگیرد. 660۵6600408 مذکور مطلوب نیست زیرا موجب سربار شده و در پیشرفت عط بازیافت دخالتي ندارد. © 08666۳001768 نناهماهنگف رلینها را مجور به ن_گهداری‌چدین!60800600]10 میکند و Sab checkpoint ir, acl Garbage cotCection ‏باعطجرلودورملوا لكوييتم‎ مدتطولانی)ستفلده ن‌شدماند. ‎Spee‏ 1 براي کاربردهايي که خروجي دارند مناسب نمي‌باشد زیرا نیازمند يك هماهنگی سراسري براي محاسیه خط بازیافت مي‌باشد. 5 5 5 5 Rollback Fualt Tolerancy 

صفحه 20:
اطلاعات وابستگی “Let C, be the x checkpoint of process P(X: Checkpoint index). “cet J,,denote the interval between checkpoints C,,,&C,,. “If Pat I, sendsmessage mto P, it will piggyback thepair (ix)on m. “When Pyreceives min I,,it vecordsependendyinfowhen P,takes c,,. x I 1 (i) Am ۳ I 1 co cu Cit cx لهم د 4 لهم Figure 7. Checkpoint index and checkpoint interval Rollback Fualt Tolerancy 

صفحه 21:
چگونه بازیافت انجام مي‌شود؟ DependencyInformation 7 : ‘Request for Rollback اگر حالت كنوني در طول خط بازیافت بود اجرا ادامه مي‌يابد. ‎hoy checkpoint 4 Sa! pe 59‏ خط بازیافت عقب گرد مي‌کند. 24/50 Rollback Fualt Tolerancy 

صفحه 22:
گراف وابستگي و گراف 606۳0110» در محاسبه خط بازیافت ان ۳ a Dependency og = 7 ‏ره‎ ‎Recovery tially line Marked ark Marka Checkpoint Graph Rowovery a Tine © .م Figure 8, (a) Example exceution: (b rollback-dependeney graph: () checkpoint graph 221/50 Rollback Fualt Tolerancy 

صفحه 23:
Garbage Collection * هر 66606۳001006 اي براي هر ترکیب ممکن از خرابي باشد مي‌تواند جزو 9060066016061101 باشد. فرایندها که قبل از 21706 106607671۷ oloai Rollback Propagation jbl» Soi 23 pin Recovery Line af lke ® ‏زيادي از 6060600106 هاي غیر ضروري لازم است نگهداري‎ Global recovery Obs checkpoints line {Go 7 Markallvolatilecheckpoints | Pal S&removealledgesendingina | | marked checkpoint. ها رای رسیم ‎Ose‏ .© ge collection based on global recovery line and obsolete cheekpoints. Rollback Fualt Tolerancy 

صفحه 24:
۷۷۵ هماهنگ ‎loan] 3 a5 ols jLi Kalen checkpointing JS5, ©‏ :610011 خود را به صورت هماهنگ در قالب يك حالت سراسري سازگار بگیرند. 8 مزایا: * ساده‌سازي در ‎Recovery‏ ‏۰ ‎ ‏در آن اثر دومینو انتظار نمی‌رود. زیرا هميشه هر فرایند از آخرین 10660000۷» خود شروع مجدد مي‌نماید. .7 © هر فرايند فقط مجبور به نگهداري يك 06۵060100 در 5۲0666510۲006 مي‌باشد که سبب کاهش سربار ذخیره. همچنین حذف نیاز به ‎Garbage collection‏ مي‌شود. 3 عيب عمده: ۴ تاخیر طولاني براي صدور خروجي. زیرا يك 6606001006> سراسري قبل از صدور خروجي به دنياي خارج نیاز است. ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 25:
چگونه 02690 ها هماهنگ می‌شوند؟ Block communications while the checkpointing protocol executes Takea checkpoint اكه ةكد ‎Communicatio‏ ‎Channet.‏ Take Tentative Checkpoint Commit message ‘Removeold checkpoint 251/50 Rollback Fualt Tolerancy 

صفحه 26:
Non-blocking Checkpoint Coordination يك مساله ابتدائي در 0606060011011 هماهنگ جلوگيري فرایند از دریافت پیام مي‌باشد که مي‌تواند 6001108 م0)عرط ناسازگار سازد. Initiator Initiator Initiator heckpoin request teekpoint rues ‎request‏ متيام لوي ‎ ‎oh Cis es ‎0 oy © ‎Figure 11, Non-blocking coordinated checkpointing: (a) checkpoint inconsistency: (b) with FIFO channels; (c) non-FIFO channels (short dashed line represents pizgybacked checkpoint request) ‎ ‎Rollback Fualt Tolerancy ‎ ‎ ‎ ‎ ‎ 

صفحه 27:
کلاك سنکرون شده )00 ۴ کلاك سنکرون مي‌تواند سبب تحريك عملیات 60۵06001۷18 محلي همه فرایندهاء تقریبا در همان زمان بدون 61۵060010 شروع کننده شود. . ‎Checkpoint 2113 eh‏ مي‌گیرد و براي مدتي که مساوي با مجموع بیشترین انحراف بین کلاك و بیشترین زمان براي تشخیص خرابي در فرايندهاي دیگر در سیستم می‌باشد. منتظر می‌ماند. ‏فرایندها مي‌توانند مطمئن باشند 45 ‎checkpoint ao‏ ها بدون نیاز به تبادل هیچ پیامی به صورت هماهنگ گرفته شده‌اند. ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 28:
Minimal Checkpoint Coordination * براي 6620© هماهنك لازم است كه همه فرايندها در هر عمليات 9 شرکت کنند. این نيازمندي به مفهوم مقیاس پذيري وابسته مي‌باشد. بنابراین کاهش تعداد فرايندهايي که در 0606۳00106 هماهنگ شرکت دارند. مطلوب می‌باشد. ل در طول فاز اول. 06600]06> آغاز کننده همه فرايندهايي که با آن )5 ‎bs checkpoint‏ ارتباط داشته است را مشخص نموده و به آنها يك درخواست مي‌فرسند. فرایند به محض دریافت درخواست. همه فرايندهايي که با آن فرایند از 606006۳00001 قبلی ارتباط داشته است را مشخص نموده و به آنها يك درخواست می‌فرستد و به همین منوال تا اینکه فرایند ديگري براي شناسايي نباشد. 3 در طول فاز دوم. همه فرايندهايي که در فاز اول شناسايي شدند 06606001106 مي‌گيرند. Rollback Fualt Tolerancy 

صفحه 29:
Communication-inducedCheckpointing * از اثر دومینو جلوگيري مي كند با اينكه به فرايندها اجازه مي‌دهد برخي :01 عع ها را مستقلا بكيرند. * بهرحال فرايندهاي مستقل مجبور به ضمانت تحول پیشرفت خط بازیافت مي‌باشد. بنابراین فرایندها مجبور به گرفتن 06001100ع0» اضافي مي‌باشند. ‎checkpoint)‏ اجباري) ‎pl ychins only al I sulrcpelCheckpoint 3‏ | يردانِشكد كرفته شود که موجبتساخیر و سربار زیاد مییّسود 7 در عوض با 006060010 گرفتن هماهنگ هیچ پیام خاصي رد و بدل نمي‌شود 29/50 Rollback Fualt Tolerancy 

صفحه 30:
چارچوب مطالب © ميمه " تعاريف * پروتكل‌هاي ‎checkpointing‏ ‏* پروتگل‌هاي بر مبناي واقحه‌نگاري ۴ مقایسه Rollback Fualt Tolerancy 

صفحه 31:
Log-Based Rollback Recovery = اجراي يك فرايند مي تواند با دنبالهاي از بازه حالات قطعي مدل شود که شروع هر اجرا و بعبارتي بازه با يك رخداد غیر قطعي آغاز مي‌شود. 7 شروع بازه قطعي فقط به دنباله‌اي از رخدادهاي غیر قطعي که قبل از شروع بازه مي‌باشد. بستگی دارد. که Rollback Fualt Tolerancy 

صفحه 32:
-Log-Based Rollback Recovery Concepts * این روش بر قطعیت تكه‌اي تکیه دارد. فرض مي‌کند همه رخدادهاي غیر قطعي مي‌تواند مشخص شود و عامل‌هاي مربوطه مي تواند | ذخیره شود. ل با واقعه نگاري و پاسخ به رخدادهاي غیر قطعي به ترتیب اصلي خود. يك فرایند قطعا مي‌تواند حالت قبل از خرابي خود را بازسازي کند حتي اگر این حالت ‎wl os checkpointing‏ * علي الخصوص براي كاربردهابي که با دنياي خارج در تعامل هستند که شامل وسایل ورودي /خروجي که نمي‌تواند 0618066 نماید. جذاب مي‌باشد. *_ با این حال هر فرایند براي کاهش گسترش عقب گرد در ‎checkpointing cab jb Jyb‏ ,| نجام مي‌دهد. 2 66ه۲6)م بر مبنایولقعه نگاييه حا تیف رلتر از ‎eh checkpoint‏ ازگار لخير و ضمانتمیکند سیستم هیچ ف ولیند بتیمي‌را تولید ز Rollback Fualt Tolerancy 

صفحه 33:
واقعه نگاري بدبینانه در مقابل خوشبینانه © در واقعه نگاري بدبینانه کاربرد بای بلوك شده و منتظر عامل‌هاي رخدادهاي غيرق رخداد توسط بقیه فرایندها یا دنياي تخارج:ديدة شود وأقحة نكاري شود. خطا مي‌تواند بعد از هر رخداد غير قطعي رخ دهد. در واقعه نگاري خوشبینانه. کاربرد بلوك نمي‌شود. عاملها در يك ۲0۵ موقتي نگهداري مي‌شود و به صورت آسنکرون در ‎wh abs stable storage‏ لا واقعه نگاري قبل از ایجاد خطا کامل مي‌شود. Rollback Fualt Tolerancy 

صفحه 34:
20-6 بر لساس‌لینکه عاملعا چگونه ن‌گاشته شوند دارلیسه روشگوناگونلست ۴ پروتکل بدبینانه ضمائت مي‌کند که بخاطر خرابي يتيمي تولید نخواهد شد. اين يروتكل سبب سادگي در ‎Garbagecollection , recovery‏ 9 خروجي با هزینه سربار كارايي بالاتر هنگام عاري از خطا بودن مي‌شود. پروتکل خوشبینانه سربار كارايي بدون خطا بودن را کاهش مي‌دهد اما اجازه ایجاد يتيم را بخاطر خطا مي‌دهد. احتمال داشتن یتیم بازیافت 7 »6 و خروجي را پیچیده مي‌کند. پروتکل سببي سعي بر ترکیب مزاياي سربار پائین کارايي و خروجي سریع را دارد. اما ممکن است نیازمند ۲۵60۷۵۳۷ و ‎Garbagecollection‏ پیچیده گردد. Rollback Fualt Tolerancy 

صفحه 35:
چگونه بدبینانه بازیافت مي‌کند؟ ‘Roll forwarduse determinant Cogs to ‏موس‎ ‎deliver same sequence of messages.‏ و ‎determinant ‎5 ‎(mmm) Po ‎ ‎Maximum recayerable state ‎ ‎ ‎ ‎(mmm) Py ‎(mm) Py ‏جح ‎ ‎Restartfrom Figure 12. Pessimistic logging ‎BothstateZYisconsistentwithX ‎‘Recoveryiscomplete ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 36:
در سيستم 08) كردن بدبينانه .... ® حالت قابل مشاهده هر فرايند هميشه قابل بازيافت است. مزای: 9 فرایندها مي‌تواند بدون اجراي پروتکل خاصي به دنياي خارج خروجي صادر کنند. 3 فرايندها از :04866201511 اخير خود به محض وقوع خرابي مجدد شروع مي‌کنند ۴ محدود كردن كسترش اجراي ‎sam‏ ‏3 بازیافت ساده شد زیرا اثر خرابي فقط محصور به فرايندي که خراب شده مي‌شود. © يك قرایند هیچ وقت يتيم نخواهد شد. زيرا فرايند هميشه به حالتي كه شامل تعامل اخير با فراينديهاي دتگر با دنيای خارج استزباز مت گزدد. 1 2 اطلاعات بازیافت مي‌تواند به آساني دور ريخته شود. © 6۵600 هاوقدیمنر و عاملهایرخدادهایغرقطمیقبلاز 0860600101 لخیر مین ولنند حذفشود. 1 0 5 5 1 " هزينهاي كه براي اين مزايا بايد برداخت شود جريمه كارايي با واقعه نكاري سنكرون مىباشد. Rollback Fualt Tolerancy 

صفحه 37:
کاهش سربار توسط روش: ‎Sender-Based Message Logging (SBML)‏ * ۹۵۷8 عاملهاي تناظر بالنتقلسيام 10 را در حافظه موقتف رستندم ا عامل‌هاي 16 شامل محتوا و ترتيبي که ارسال شده در دو مرحله ثبت مي‌شود. ‘Before Sendingm Sender Cogsitscontent involatilememory ‘Then receiver respondswithanack. includes order in which the message 0 ‏و‎ Che delivered. determinant dering information ‏مب وند ك‌خرلبی‌ا تحمل نماد و رخدادهایفبرقطعیداخلك‎ OB ‏فرلیند را ن مت ولند حاماید.‎ Rollback Fualt Tolerancy 

صفحه 38:
کاهش سربار توسط روش: ‎Relaxing Logging Atomicity‏ ۴ باارسال پیام یا رخداد و تفاوت قائل شدن ميان ثبت آنها تا زماني که میزبان با ميزبان‌هاي دیگر یا دنياي خارج ارتباط برقرار نماید. ۵ دررط ثبت پيام‌هاي اد تا زماني که با فرايندهاي دیگر یا دنياي خارج در ارتباط هستند. تغییر مي‌کند. 9 پيام‌هاي ‎sm,‏ ,10 مجاز به اثر كذاري بر روي فرايند م2 مي باشند, اما این اتر محلي است و فرایند ديگري يا دنياي خارح آن را نمي‌توانند ببینند تا اينكه ييام ثبت شود. ثبت رخداد و ارسال آن در اين واقعه‌نگاري خوشبینانه نمي‌تواند در عملیات يك لحظداي انجام شود. 7 1 ‎ee 8‏ مي‌تواند سربار را کاهش دهد. زیرا چندین رخداد مي‌تواند در يك عملکرد که باعث کاهش تعدد دسترسي به 506665107086 مي‌شود. ثبت شود. تاخیر ارتباط بین فرايندي و صدور خروجي کاهش نمي‌یاید زیرا عملیات ثبت معمولا قبل از ارسال پیام نیاز است. ‎Rollback Fualt Tolerancy ‎ ‎ 

صفحه 39:
اش ومد ریب مت کید * پروتكل‌هاي خوشبینانه نیز به این دارد که چندین 060066001006 را نگهداري ‎sales‏ * براي آسنکرون بودن صدورلاخروجي [نیازمند هماهنگي چندین میزیان ميباشد. ‎‘tog Por oll Back toundo‏ ask Need to Commit output P7become Orphan ing Orphan Beforem, isCogged P2rollback Figure 13. Optimistic logging, Rollback Fualt Tolerancy Py 

صفحه 40:
۷۷ سنکرمن ۴ همه فرایندها پروتکل 1060۷671۷ را براي محاسبه بیشترین حالت قابل بازیافت سیستم. بر اساس وابستگي و اطلاعات نگاشته شده آنجام مي‌دهند. سپس 10)18066 را انجام مي‌دهند. ° * وبستگي ستقیم انديس بازه فرستنده بر روي هر ييام خروجي براي اينكه به دريافت كننده اجازه دهد تا وابستگی که مستقیما بواسطه پیام ایجاد شده. ضبط نماید. 2 9 وابستگي متعدي عموما سبب ايجاد سربار بالاتري براي سوار شدن بر بيامها و نگهداري بردار ‎es‏ مي شود. اما صدور خروجي و بازيافت سريعتري را به ارمغان مي‌آورد. روش آن به شکل زیر است: ‎Eachprocess P.maintainsa size-Nvector TD,where TDlilis?,’s‏ current stateintervalindex,& TDIjlj i,records the highest index ofany stateinterval of Pon which P, depends. Rollback Fualt Tolerancy 

صفحه 41:
Multipleincarnations of thesameprocessmay coexist in the Asynchronous Recovery Ifa single failure causes aprocess to roll backan exponential number of times Ingeneral whichprocess P,, i> 0, rolls back 2“ timesin response to P,'sfailure. Approachis to piggyback the original rof(backannouncement onany subsequent rollbackannouncement (P,piggybacks ron r,).lix):x'"interval of [1.2] Coses i“incarnation Po عمط v,reaches?, before, Figure 14. Exponential rollbacks. Rollback Fualt Tolerancy 

صفحه 42:
‎Maximum recoverable state‏ رح ‎Po ‎ ‎ ‎{Determinant ofeach eventscontains:order inwhichitsoriginal receiver delivered the corresponding message. ‎P, will beable to guide the recovery ofP,,P,sinceit knows the order inwhich, should replaymessagesm,,m, toreach the statefromwhich?, sends é | ۱ ‏ومد‎ ‎Noticeinformation about m,m, isnot availableanywhere. ‎Figure 15. Causal logging. (a) Maximum recoverable states, and (b) antecedence graph of Pp at state X, ‎Rollback Fualt Tolerancy ‎ 

صفحه 43:
چارچوب مطالب © ميمه " تعاريف * پروتكل‌هاي ‎checkpointing‏ ‏۴ پروتکل‌هاي بر مبناي واقعه‌نگاري * مقایسه ۴ مراجع 3/50 Rollback Fualt Tolerancy 

صفحه 44:
مقایسه: 0 Causal Logging Logging -Pessimisite Logging Complex | Complex Several Possible Possibly Last 1 | checkpoint checkpoints Yes Yes Fastest Slow Fast Comm Induced Checkpointing No Complex Several Possible Possibly several checkpoints Yes Very slow Coordinate Very slow Uneoontinated Checkpeinting No Complex Several Possible Possible Lnbounded Yes Not possible Table 1 Comparison between different flavors of rollback-recovery protocols Rollback Fualt Tolerancy PWD assumed” Garbage collection ‘Checkpoint process Domino oe Orphan processes Rallback extent Complex ‘Ourput commit 

صفحه 45:
چارچوب مطالب مقدمه ۴ تعاریف * پروتكل‌هاي ‎checkpointing‏ ‏۴ پروتکل‌هاي بر مبناي واقعه‌نگاري * مقایسه ely Rollback Fualt Tolerancy 

صفحه 46:
| Survey £. N.E(nozahy,D.B.Johnson,andy.M. Wang, A survey of rollback-recovery protocolsin message-passing systems, Tech. Rep. No. CMU-CS-96-787,Dept. of Computer Science, Carnegie MefCon University, 1996. = £.AlvisiandK. MarzulCo, "Message Logging: Pessimistic, Optimistic,andCausal,’ Proceedings of the 5thIEEEInternational Conferenceon Distributed Computing Systems. Vancouver,Canada, June 1995, Pp. 229-236. Rollback Fualt Tolerancy 

صفحه 47:
| Model & Consistency * K.M.Chandyand£. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, ACM Trans. on Computer Syst.,vol.3,n0.1,pp.63-75, Feb. 1985. © VM. Wang A.Lowry andW. i. Fucks, ‏شدای سس امه او نج ایو‎ direct dependency tracking, Information Processing Letters, Vol.50, No.4, pp.223- 230, May 1994. = YM. Wang,“Maximumandminimum consistent global checkpointsand their applications, in Proc. IEEE Symp. Reliable Distributed Syst. (SRDS), pp. 86--95, Sept. 7995. " JianXuand Robert H.B. Netzer, Necessary and Sufficient Conditions for Consistent Global Snapshots, (cs93-32,ps), IEEE Trans. on PADS. Vol.6, No.2, February 1995. © D.ManivannanandM. Singhal,’A Low-overhead Recovery Technique Usin, Quasi Synchronous Checkpotnting, In Proceedingsofthe sethinternational Conference on Distributed Computing Systems, May 1996, pages 100-707. © D.Manivannan, Robert H.B. Netzer andM. Singhal, Finding Consistent Global Checkpointsina DistributedComputation, (OSU-CISRC-3/96-TR16) In IEEE Transactions on Parallel and Distributed Systems, a(6):623-627, June 1997. ۶ D,ManivannanandM. Singhal, Quasi-Synchronous Checkpointing: Models, Characterization andClassification, Submitted toIEEETransactionson Parallel and Distributed Systems.(7999) Rollback Fualt Tolerancy 

صفحه 48:
| ‏سس‎ (No Cogging) JianXuand Robert H.B. Netzer, AdaptiveIndependent Checkpointing for Reducing Rollback Propagation, (cs93-25.ps)In Proc. sthIEEE Symp. on Parallel and Distributed Processing pages 754-761, December 1993. " B.Bhar qavaands. R. Lian, Independent Checkpointing andConcurrent Rottbackfor Recovery An Optimistic Approach, In Proc. of IEEE Symp. on Reliable Distributed Syst.,pp.2-12,1988. = R,Kooands.Toueg,'Checkpointing and Rollback-Recovery for DistributedSystems, IEEE Trans. on Software Eng.,vol.SE-13,no. 1,pp. 23-31,Jan.1997. * [1.2.1000 ‏و0 'ب6ته .4ه‎ in DistributedSystems, IEFETrans.on Parallel and DistributedSyst Vol. 4,n0. 8, pp.955-960, Aug. 1993. V.M.WangandW.K. Fuchs, Lazy checkpoint coordination for bounding rollback propagation, in Proc. IEEE Symp. on Reliable Distributed Systems (SRDS -72),pp.78--85,0ct.1993. = y.M.Wang,?.y.Chung,I.J.Lin,andW.X. Pucks. “Checkpoint space reclamation for uncoordinated check; ointing in message-passing systems." IEEE Trans. Parallel and Distributed Syst.,6(5):546-554,May 1995. Rollback Fualt Tolerancy 

صفحه 49:
Implementation & Performance © Emootazbellah Nabil ELnozahy, David B. Johnson and WillyZwaenepoel, ‘The Berformanceof Consistent Checkpointing, In Proceedings of te thSymposiumon Reliable Distributed Systems pp. 39-47, IEEE Computer Society, Houston, TX, October 1992. © Y.dtuang,C.Kintala,andy.m. Wang, Software ToolsandLibrariesfor Fault Tolerance, in Bulletin of the Technical Committeeon Operating Systemsand Application Environment (TCOS), Vol.7, No.4,pp.5--9, Winter, 7995. © V.M.Wang¥,duang,X.-P. Vo,P.y. Chung, andC. Kintala, 'Checkpointingandits applications, in Proc. IEEE Fault-Tolerant Computing Symposium (FICS-25), pp. 22-37,June 1995. * Roberto Baldoni,Jean Michel Helary, Achour Mostefaoui, Michel Raynal. “Consistent Checkpointing in Message Passing Distributed’ ystems".Institut National de RechercheenInformatiqueet en Automatique, Juin, 1995. Gerard?. Kavanaughand William 4. Sanders. “Performance Analysisof two Hime. Based Coordinated heckpointing Protocols.” Center for Reliable & High Performance Computing Coordinated Science Laboratory, University of I(tinoisat ‘Urbana-Champaign, From PacficRimInternational Symposiumon Fault- Tolerant Systems, Taipei, Taiwan, December 15-16,1997. B.BhargavaandS.R. Lian. “Independent checkpointingandconcurrent rollback for recovery -Anoptimistic approach." In Proc. IEEE Symp. Reliable Distributed ‘Syst.,pages 3-12, 1988. Rollback Fualt Tolerancy 

صفحه 50:
| MiscelCaneous " £.Cohen,y.M. Wang,andG. Suri, "When piecewise determinismisalmost true, in ‎Fault-Tolerant Systems,pp.66--71,‏ مع 0 رط ‎‘Dec. 1995.‏ ‎boundon useful distributed‏ عو وی با ‎J‏ .ته وتتبجقء ۱ ‎System checkpoint, Tech. Rep. CRIC-99-16 CoordsnatedScience faboratary,‏ ‎‘University of I(Cinoisat Urbana-Champaign, 7995.‏ ‎Ramamurthy, B.,Upadhyaya,S.Bhargava,B.,"Designandanatysisofan‏ ‎integrated checkpointirig and recovery scheme for distributed applications, IEEE‏ ‎Transactions on KnowledgeandData Engineering, Volume: 72Issue:2,March-‏ ‎April 2000 Pagels):174-186‏ ‎Dan Pei, Dongsheng Wang, Meiming Shen, Weimin Zheng, "Designand‏ ‎implementation ofa (ow overhead ilecheckpointingapproach, High Performance‏ ‎Computingin the Asia-Pacific Region, 2000. Proceedings. The Fourt‏ ‎International Conference/Exhibition on, Volume: 7,2000Page(s):439 -441vol.1‏ ‎Meth, K.z.,Tuel,W.G,,"Parallel checkpoint /restart without message Clogging,‏ = ‎International Workshops on Parallel Processing, 2000. Page(s):253-258‏ ‎ViZhang, Jianping Hu'Checkpointing andprocessmigrationin network‏ ‎computing environment, Info-techandInfo-net,2007. Proceedings. ICI 2007 -‏ ‎‘Beijing. 2007 International Conferences on, Volume: 3,200‏ مهم كشا كهوحها عقعدة ]اه تفاهه وج اخ دادمو عع جنتعو]ء 5 ملاب ركوط ۱ ‎distributed systems, Distributed Computing Systems, 2007. 27st International‏ ‎Conferenceon.,2007 Page(s):39-46‏ ‎ ‎ ‎Rollback Fualt Tolerancy ‎ ‎ 

‏ فصل : 12پروتكل‌هاي Roll-back Recoveryدر سيستم گذر دهي پيام درس طراحي سيتم‌هاي مطمئن چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 2/50 ‏Rollback Fualt Tolerancy مقدمه : ‏ ‏ ‏ امروزه سيستمهاي توزيع شده در همه جا موجود مي‌باشند و بدين سبب ما را قادر به انجام بسياري از كارها مي‌نمايد .سيستمهاي Client Serverو WWWو محاسبات علمي از جمله بسياري از آنها مي‌باشند. پتانسيل اين سيستمها به خاطر گستردگي محاسبات و با توجه به حساسيت آنها نسبت به وقوع خطا محدود مي‌گردد .از اينرو تكنيكهاي فراواني براي قابليت اطمينان ،دسترس پذيري باال براي سيستم‌هاي توزيع شده گسترش يافته است. اين تكنيكها شامل موارد زير مي‌باشد: ‏ :Transactions ‏ : Group communications ‏ : Rollback recovery ‏ ‏ ‏ 3/50 بر كاربردهاي داده گرا تمركز دارد. انتزاعي از يك سيتم ارتباطي ايده‌آل كه برنامه نويس مي‌تواند برنامه‌اش را بصورت مطمئن بر روي آن توسعه دهد، پيشنهاد مي‌كند. بر روي كاربردهاي با زمان اجراي طوالني تمركز دارد ،مانند محاسبات علمي و كاربردهاي ارتباطي. ‏Rollback Fualt Tolerancy مدل سيستم سيستم گذر دهي پيام ( )message passing systemشامل تعداد ثابتي فرايند که بين آنها پيام رد و بدل مي‌‌شود ،مي‌باشد .فرايندها براي اجراي برنامه کاربردي توزيع شده ضمن تعامMMل بMMا جهان خارج با دريافت پيام ورودي و ارسال پيام خروجي ،با هم همکاري مي‌کنند. يMMMMMMMMMMMMMMMMMMMMMMMMMMMک فراينMMMMMMMMMMMMMMMMMMMMMMMMMMMد ممکن اسMMMMMMMMMMMMMMMMMMMMMMMMMMMت بهمحضخرابي ،دچار خرابي شود. مدلتوقف  اجرابراساس  ‏ياتوقف  بدليلگمكردنحالتموقتخود 4/50 ‏Rollback Fualt Tolerancy مفهوم Rollback Recoveryدر سيسMMتم‌هاي توزيMMع شده ‏ در سيستم فوق تحمل‌پذيري خطا با ذخيره حالت فرايندهاي سيستم در دوره‌هاي خاص ،زمان اجراي عاري از خطا طبق سياست معين ،روي منبع ذخيره پايدار Stale Storageو بازگشت بMMه يكي از آن حاالت هنگام بروز خرابي ميسر مي‌شود .اين كار سبب كاهش محاسبات از دست رفته مي‌شود. هر حالت ذخيره شده يك Checkpointنام دارد .عمليات بازيافتي كه فرايند به محض وقوع خطا انجام مي‌دهد تا به يكي از اين Checkpointها بازگشMMت نمايMMد Rollback Recovery مي‌گويند. ‏ پروتكل‌هاي Rollback Recoveryبه دو دسته تقسيم مي‌شوند: ‏ ‏ Rollback Recoveryبا سيستم توزيع شده بعنوان مجموعه‌اي از فرايندها كه در طول شبكه با هم در ارتباط هستند رفتار مي‌كند. ‏ ‏Checkpoint-based براي جلوگيري از هدر رفتن محاسبات و عمليات ،بر روي هر فرايند در مواردي طبق سياست خMMاص از وضعيت فرايند Checkpointگرفته مي‌شود .بسته بMMه نحMMوه گMMرفتن CheckpointبMMه سMMه دسته هماهنگ ،ناهماهنگ و وابسته به ارتباط تقسيم مي‌شود. ‏log-based عالوه بر مورد باال رخدادهاي غيرقطعي فرايندها را نيز ثبت مي‌كند تا مقدار بيشتري از عمليMMات انجMMام شده را بازيافت نمايد .بسته به نوع ثبت رخداد به سه دسته بدبينانه ،خوشبينانه ،سببي تقسيم مي‌شود. ‏ 5/50 ‏Rollback Fualt Tolerancy چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 6/50 ‏Rollback Fualt Tolerancy حالت سازگار سراسري سيستم ‏ ‏ ‏ بدليل انتقال پيام بين فرايندها در سيستم گاهي پيش مي‌آيد كه يك Checkpointنشان‌دهنده آن است كه فرايند پيامي دريافت كرده ،در حالي كه هيچ Checkpointاز فرايند ديگري نشان‌دهنده ارسال آن پيام نيست .چنين پيامي را يتيم Orphanمي‌گويند. در Recoveryبه تركيبي از Checkpointها كه در Rollbackبدست مي‌آيد ،حالت سيستم مي‌گويند. اين حالت بدليل وجود پيام يتيم به دو دسته تقسيم مي‌شوند: ‏ ‏ ‏ 7/50 حالتي كه در آن پيام يتيم وجود داشته باشد حالت ناسازگار Inconsistent حالتي كه پيام يتيم نداشته باشد و يك اجراي درست را نشان دهد سازگار Consistentگويند. Recoveryهدف پيدا كردن تركيبي از Checkpointها بطوري كه حالت سازگار ‌ در سراسري سيستم را نشان دهد ،و بازگشت به آن حالت در سيستم مي‌باشد. ‏Rollback Fualt Tolerancy پيام گذرا پيامي است که فرستاده شده اما هنوز دريافت نشده است. موقعيتي را نشان مي‌دهد که پيام از فرستنده ارسال شده و در شبکه سرگردان مي‌باشد. فرايند P2نشان مي‌دهد m2دريافت شده اما حالت فرايند P1ارسال آن را منعکس نکرده است. پيام يتيم پيامي است که دريافت شده اما فرستنده‌اي ندارد. 8/50 ‏Rollback Fualt Tolerancy مسير Zو چرخه Z • مسير ( Zمسير زيگزاگي) دنباله خاصي از پيام‌ها است که دو checkpointرا به هم متصل مي‌کند. {}m3,m4{ , }m1,m2 • چرخه Zمسير Zاي است که نقطه شروع و پايان آن يکي باشد}m5,m3,m4{ . • يک checkpointدرون چرخه Zنمي‌تواند بخشي از يک حالت سازگار در سيستمي که فقط از checkpointاستفاده مي‌کند ،باشد. ‏Zcycle ‏X ‏Zpath 9/50 ‏Rollback Fualt Tolerancy پيام‌هاي گذرا درمدل سيستم فرض شده باشد يا نه. • وجود پيام گذرا بسته به اين است که کانالارتباطيامن  • فرض ارتباط امن طراحي پروتکل را راحت مي‌کند اما پياده سازي را مشکل مي‌نمايد. 10/50 ‏Rollback Fualt Tolerancy اطالعات Checkpointingو وابستگي فرايندها ‏ ‏ ‏ ‏ در checkpointingهMMر فراينMMد حMMالت خMMود را بMMه صMMورت دوره‌اي بMMر روي Stable Storageذخيره مي‌كند .حالت ذخيره شده يك فرايند شامل اطالعات كافي براي شروع مجدد آن فرايند مي‌باشد. در سيستم گذر دهي پيام بخاطر تبادل پيام بين فراينMMدها هنگMMام عمليMMات عMMاري از خطا ،وابستگي ايجاد مي‌شود ،بMMه همين دليMMل داراي Rollback Recovery پيچيده مي‌باشد. هر حالت سراسري سMMازگار از checkpointدر سيسMMتم مي‌توانMMد بMMراي شMMروع مجدد فرايندها به محض وقوع خطا بكار رود. مجموعه Checkpointهاي سراسMMري سMMازگار در سيسMMتم يMMك خMMط ارجMMاع را تشMMMكيل داده كMMMه بMMMه آن ‌Recovery LineگوينMMMد ،اين خMMMط هنگMMMام Recoveryمشخص و سيستم به آن حالت برمي‌گردد. 11/50 ‏Rollback Fualt Tolerancy  Propagation Rollbackو اثر دومينو ‏ ‏ ‏ ‏ فرايندها بسته به نيازشان هنگام اجرا با هم ارتباط برقرار مي‌كنند .بدينوسيله وابستگي بين آنها ايجاد مي‌شود. هنگام وقوع خرابي در يك يا چند فرايند ،در زمان ، Rollbackبه خاطر وابستگي بين فرايندها عالوه بر فرايندي كه در آن خرابي رخ داده ،ممكن است ساير فرايندها نيز مجبور به Rollbackشوند .به اين پديده Rollback Propagationمي‌گويند. حالت سراسري سازگار checkpointمي‌تواند Rollback Propagationرا محدود نمايد. اگر در برخي سناريوهاي خرابي اين Rollback Propagationمنجر به اين شود كه همه فرايندها به حالت اوليه خود برگردند ،اثر دومينو ( )Domino Effectرخ داده است .وقوع اين پديده باعث از دست رفتن تمامي محاسبات قبل از خرابي گشته و سيستم را به حالتي كه هيچ عملياتي انجام نداده بود مي‌برد .بدين جهت اين پديده نامطلوب است. 12/50 ‏Rollback Fualt Tolerancy براي اجتناب از اثر دومينو در سيستم ،فرايندها‌بايد checkpointingخود را بصورت هماهنگ انجام داده كه سبب پيشرفت Recovery lineمي‌شود .يا اينكه عمليات checkpointing خود را با واقعه نگاري نگاري تركيب كنند. ‏Domino Effect ‏Rollback ‏Propagation 3 \ \ 2 1 9 6 / / \ \ \ 8 5 4 13/50 ‏Initial ‏State ‏Rollback Fualt Tolerancy \ 7  Checkpointingو اثر دومينو ‏ هنگامي كه هر فرايند مستقٌال عمليات checkpointingرا انجام دهد مي‌تواند سبب پيدايش اثر دومينو شود (.عمليات checkpointingناهماهنگ) ‏ يكي از روشهايي كه سبب مي‌شود عمليات checkpointingهماهنگ انجام شود اين است كه سيستم در بعد وسيع حالت سازگار خود را ذخيره نمايد. ‏ راه ديگر اينكه checkpointingبر مبناي ارتباط باشد .به اين معني كه هر فرايند را مجبور كند بر اساس اطالعات سوار شده بر پيام‌هايي كه از فرايندهاي ديگر دريافت مي‌كند checkpoint ،خود را بگيرد Checkpoint .هايي كه در كل سيستم به صورت سازگار گرفته شده‌اند ،هميشه بر روي Stable ‌Storageوجود دارند ،بنابراين از اثر دومينو اجتناب مي‌شود. 14/50 ‏Rollback Fualt Tolerancy تعامل با دنياي خارج ‏ ‏ ‏ ‏ يك سيستم گذردهي پيام معموال براي دريافت داده يا نشان دادن خروجي محاسبات با دنياي خارج در تعامل است .با اين تفاوت كه اگر خرابي رخ دهد دنياي خارج نمي‌تواند به Rollbackتكيه نمايد. بنابراين پروتكل‌هاي Rollbackبراي تعامل با دنياي خارج بايد رفتار خاصي را بر گزيند. قبل از ارسال خروجي به دنياي خارج ،سيستم بايد مطمئن شود حالتي كه خروجي از آن ارسال مي‌شود ،عليرغم خرابي در آينده ،قابل بدست آوردن است(.مساله صدور خروجي) براي پيام‌هاي ورودي راه حل عبارت از ذخيره پيام ورودي بر روي ،Stable Storageقبل از اينكه به برنامه كاربردي اجازه پردازش آن داده شود ،مي‌باشد. 15/50 ‏Rollback Fualt Tolerancy Logging Protocols vs. ‏Checkpointing روش واقعه نگاري وقتي تعامل با دنياي خارج مكرر است ،بيشتر استفاده مي‌شود .زيMMرا يMMك فراينMMد را قMMادر مي‌سMMازد اجMMرايش را تكMMرار كنMMد و بMMا ارسMMال خMMروجي بMMه دنيMMاي خMMارج بMMدون داشMMتن هزينMMه گMMران checkpointingقبل از ارسال خروجي سازگاري داشته باشد. ‏Orphan ‏messag ‏e ‏Replay delivery to recover ‏messages ‏X ‏X 16/50 ‏X ‏With ‏checkpointing ‏Rollback Fualt Tolerancy Stable Storage & Garbage ‏Collection ‏ ‏ Rollback Recoveryاز Stable Storageبراي ذخيره checkpointفرايندها ،واقعه نگاري و ساير اطالعات مربوط به بازيابي استفاده مي‌كند. Garbage Collectionبراي پاك كردن اطالعات بازيابي بال استفاده بكار مي‌رود(.زباله داني checkpointمي‌باشد) ‏ ‏ يك راه براي ‌Garbage collectionمشخص كردن Recovery lineو حذف تمامي اطالعات مربوط به رخدادهايي كه قبل از آن خط رخ داده‌اند ،مي‌باشد. اجراي الگوريتم خاص براي حذف اطالعات بال استفاده موجب سربار در سيستم مي‌شود. 17/50 ‏Rollback Fualt Tolerancy چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 18/50 ‏Rollback Fualt Tolerancy  ‌Checkpointingناهماهنگ ‏ Checkpointingناهماهنگ به هر فرايند اجازه بيشترين خود استقاللي را براي تصميم‌گيري در گرفتن checkpointمي‌دهد. ‏ مزيت اصلي اين خود استقاللي عبارت از: ‏ معايب: ‏ هر فرايند checkpointخود را زماني كه قادر است ،مي‌گيرد .براي مثال يك فرايند مي‌تواند سربار را با checkpointingدر وقتي كه مقدار حاالتي كه بايد ذخيره كند ،كوچك باشد ،كاهش دهد. ‏ احتمال وقوع اثر دومينو كه سبب از دست دادن مقدار وسيعي از كار انجام شده مي‌شود ،وجود دارد. فرايند ممكن است checkpointبال استفاده‌اي را كه هرگز بخشي از يك حالت سازگار سراسري نخواهد بود ،بگيرد checkpoint .مذكور مطلوب نيست زيرا موجب سربار شده و در پيشرفت خط بازيافت دخالتي ندارد. ‌checkpointingناهماهنگ فرايندها را مجبور به نگهداري چندين checkpointمي‌كند و باعث اجراي دوره‌اي الگوريتم Garbage collectionبراي دور ريختن checkpoint هايي كه مدت طوالني استفاده نشده‌اند ،مي‌شود. براي كاربردهايي كه خروجي دارند مناسب نمي‌باشد زيرا نيازمند يك هماهنگي سراسري براي محاسبه خط بازيافت مي‌باشد. ‏ ‏ ‏ 19/50 ‏Rollback Fualt Tolerancy اطالعات وابستگي •Let Ci,x be the Xth checkpoint of process Pi (X: Checkpoint index). •Let Ii,x denote the interval between checkpoints Ci,x-1 & Ci,x . •If Pi at Ii,x sends message m to Pj , it will piggyback the pair (i,x) on m. •When Pj receives m in Ij,y , it records dependency info when Pj takes cj,y . Rollback Fualt Tolerancy 20/50 چگونه بازيافت انجام مي‌شود؟ Calculates recovery line based on global dependency information Recoverin g Process Dependency request Dependency Information Request for Rollback ncy e d pen ation e D rm info Re lin cov er Dee y pen den cy req ues t ،اگر حالت كنوني در طول خط بازيافت بود اجرا ادامه مي‌يابد نزديك خط بازيافتcheckpoint در غير اينصورت به .عقب گرد مي‌كند Rollback Fualt Tolerancy Process 0 Process 1 Process 2 Process N 21/50 ‌ در محاسبه خط بازيافتcheckpoint گراف وابستگي و گراف Dependency Graph Node: checkpoint Dedge: Message from ci,x to cj,y if: •i ≠ j, and M from Ii,x to Ij,y •i = j and y = x Checkpoint +1 Graph When a message sent from Ii,x to Ij,y , a D-edge drawn ci,x-1 to cj,y (instead ci,x , cj,y) Rollback Fualt Tolerancy 22/50 Garbage Collection Recovery Line ‌ اي براي هر تركيب ممكن از خرابي فرايندها كه قبل ازcheckpoint • هر .‌ باشدGarbage collection باشد مي‌تواند جزو Rollback Propagation بخاطر، پيشرفت نمي‌كندRecovery Line • هنگامي كه . هاي غير ضروري الزم است نگهداري شوندcheckpoint تعداد زيادي از 1. Mark all volatile checkpoints & remove all edges ending in a marked checkpoint. 2. Use reachability analysis to determine the worst-case recovery line. Rollback Fualt Tolerancy 23/50  Checkpointingهماهنگ ‏ پروتكل checkpointingهماهنگ نياز دارد كه فرايندها checkpointخود را به صورت هماهنگ در قالب يك حالت سراسري سازگار بگيرند. ‏ مزايا: ‏ ‏ ‏ ‏ عيب عمده: ‏ 24/50 ساده‌سازي در Recovery در آن اثر دومينو انتظار نمي‌رود ،زيرا هميشه هر فرايند از آخرين ‌checkpointخود شروع مجدد مي‌نمايد. هر فرايند فقط مجبور به نگهداري يك checkpointدر stable storage مي‌باشد كه سبب كاهش سربار ذخيره ،همچنين حذف نياز به Garbage collectionمي‌شود. تاخير طوالني براي صدور خروجي ،زيرا يك checkpointسراسري قبل از صدور خروجي به دنياي خارج نياز است. ‏Rollback Fualt Tolerancy  ها هماهنگ مي‌شوند؟chekpoint چگونه Block communications while the checkpointing protocol executes Take a checkpoint Request message Coordinato r Commit message e a oint k Ta ckp e ch Ac Co n kn ow m mm t es le sa i t dg ge m e Process 0 Process 1 Process 2 Process N Stop Execution Flush all Communicatio n Channels Take Tentative Checkpoint Send Ack. Remove old checkpoint Makes tentative checkpoint, then free to resume execution and exchange messages Rollback Fualt Tolerancy 25/50 Non-blocking Checkpoint Coordination هماهنگ جلوگيري فرايند از دريافت پيام مي‌باشد كهcheckpointing يك مساله ابتدائي در .‌را ناسازگار سازدcheckpoint مي‌تواند Rollback Fualt Tolerancy 26/50 كالك سنكرون شده checkpoint ‏ ‏ ‏ كالك سنكرون مي‌تواند سبب تحريك عمليات checkpointingمحلي همه فرايندها ،تقريبا در همان زمان ،بدون checkpointشروع كننده شود. يك فرايند checkpointمي‌گيرد و براي مدتي كه مساوي با مجموع بيشترين انحراف بين كالك و بيشترين زمان براي تشخيص خرابي در فرايندهاي ديگر در سيستم مي‌باشد ‌،منتظر مي‌ماند. فرايندها مي‌توانند مطمئن باشند كه همه checkpointها بدون نياز به تبادل هيچ پيامي به صورت هماهنگ گرفته شده‌اند. 27/50 ‏Rollback Fualt Tolerancy Minimal Checkpoint ‏Coordination ‏ ‏ براي checkpointهماهنگ الزم است كه همه فرايندها در هر عمليات ‌checkpointingشركت كنند. اين نيازمندي به مفهوم مقياس پذيري وابسته مي‌باشد .بنابراين كاهش تعداد فرايندهايي كه در checkpointهماهنگ شركت دارند ،مطلوب مي‌باشد. ‏ ‏ ‏ 28/50 در طول فاز اول checkpoint ،آغاز كننده همه فرايندهايي كه با آن از checkpoint قبلي ارتباط داشته است را مشخص نموده و به آنها يك درخواست مي‌فرستد. فرايند به محض دريافت درخواست ،همه فرايندهايي كه با آن فرايند از checkpointقبلي ارتباط داشته است را مشخص نموده و به آنها يك درخواست مي‌فرستد و به همين منوال تا اينكه فرايند ديگري براي شناسايي نباشد. در طول فاز دوم ،همه فرايندهايي كه در فاز اول شناسايي شدند ‌checkpointمي‌گيرند. ‏Rollback Fualt Tolerancy Communication-induced ‏Checkpointing ‏ ‏ از اثر دومينو جلوگيري مي‌كند با اينكه به فرايندها اجازه مي‌دهد برخي checkpointها را مستقال بگيرند. بهرحال فرايندهاي مستقل مجبور به ضمانت تحول پيشرفت خط بازيافت مي‌باشد .بنابراين فرايندها مجبور به گرفتن ‌checkpointاضافي مي‌باشند checkpoint(.اجباري) ‏ ‏ 29/50 Checkpointاجباري بايد قبل از آنكه كاربرد محتواي پيام را پردازش كند ،گرفته شود كه موجب تاخير و سربار زياد مي‌شود. در عوض با ‌checkpointگرفتن هماهنگ هيچ پيام خاصي رد و بدل نمي‌شود. ‏Rollback Fualt Tolerancy چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 30/50 ‏Rollback Fualt Tolerancy Log-Based Rollback Recovery ‏ اجراي يك فرايند مي‌تواند با دنباله‌اي از بازه حاالت قطعي مدل شود كه شروع هر اجرا و بعبارتي بازه با يك رخداد غير قطعي آغاز مي‌شود. ‏ شروع بازه قطعي فقط به دنباله‌اي از رخدادهاي غير قطعي كه قبل از شروع بازه مي‌باشد ،بستگي دارد. ‏Deterministi ‏c Interval ‏m4 ‏m3 ‏m2 ‏m 1 ‏Nondeterministi ‏c event 31/50 ‏Rollback Fualt Tolerancy ‏P0 ‏P1 Log-Based Rollback Recovery :Concepts ‏ اين روش بر قطعيت تكه‌اي تكيه دارد .فرض مي‌كند همه رخدادهاي غير قطعي مي‌تواند مشخص شود و عامل‌هاي مربوطه مي‌تواند در ‌stable storage ذخيره شود. ‏ با واقعه نگاري و پاسخ به رخدادهاي غير قطعي به ترتيب اصلي خود ،يك فرايند قطعا مي‌تواند حالت قبل از خرابي خود را بازسازي كند حتي اگر اين حالت checkpointingنشده باشد. ‏ ‏ ‏ 32/50 علي الخصوص براي كاربردهايي كه با دنياي خارج در تعامل هستند كه شامل وسايل ورودي/خروجي كه نمي‌تواند Rollbackنمايد ،جذاب مي‌باشد. با اين حال هر فرايند براي كاهش گسترش عقب گرد در طول بازيافت checkpointingرا انجام مي‌دهد. Rollbackبر مبناي واقعه نگاري به حالتي فراتر از checkpointهاي سازگار اخير مي‌رسد و ضمانت مي‌كند سيستم هيچ فرايند يتيمي را توليد نكند. ‏Rollback Fualt Tolerancy واقعه نگاري بدبينانه در مقابل خوشبينانه ‏ ‏ در واقعه نگاري بدبينانه كاربرد بايد بلوك شده و منتظر عامل‌هاي رخدادهاي غيرقطعي شود .و قبل از آنكه اثر آن رخداد توسط بقيه فرايندها يا دنياي خارج ديده شود ،واقعه نگاري شود. خطا مي‌تواند بعد از هر رخداد غير قطعي رخ دهد. در واقعه نگاري خوشبينانه ،كاربرد بلوك نمي‌شود .عاملها در يك logموقتي نگهداري مي‌شود و به صورت آسنكرون در stable storageتخليه شود. واقعه نگاري قبل از ايجاد خطا كامل مي‌شود. 33/50 ‏Rollback Fualt Tolerancy  Log-baseبر اساس اينكه عامل‌ها چگونه نگاشته شوند داراي سه روش گوناگون است ‏ ‏ ‏ پروتكل بدبينانه ضمانت مي‌كند كه بخاطر خرابي يتيمي توليد نخواهد شد. اين پروتكل سبب سادگي در recoveryو Garbage collectionو خروجي با هزينه سربار كارايي باالتر هنگام عاري از خطا بودن مي‌شود. پروتكل خوشبينانه سربار كارايي بدون خطا بودن را كاهش مي‌دهد اما اجازه ايجاد يتيم را بخاطر خطا مي‌دهد .احتمال داشتن يتيم بازيافت و Garbage collectionو خروجي را پيچيده مي‌كند. پروتكل سببي سعي بر تركيب مزاياي سربار پائين كارايي و خروجي سريع را دارد .اما ممكن است نيازمند recoveryو Garbage collection پيچيده گردد. 34/50 ‏Rollback Fualt Tolerancy چگونه بدبينانه بازيافت مي‌كند؟ Logs determinant s {m0, m4, m7} Receipt message m7 from P1 Roll forward use determinant logs to deliver same sequence of messages. {m1, m3, m6} P1, P2 Fail {m2, m5} Restart from Recovery is complete Both state Z,Y is consistent with X Rollback Fualt Tolerancy 35/50 در سيستم logكردن بدبينانه .... ‏ ‏ حالت قابل مشاهده هر فرايند هميشه قابل بازيافت است. مزايا: ‏ فرايندها مي‌تواند بدون اجراي پروتكل خاصي به دنياي خارج خروجي صادر كنند. فرايندها از checkpointاخير خود به محض وقوع خرابي مجدد شروع مي‌كنند. ‏ بازيافت ساده شد زيرا اثر خرابي فقط محصور به فرايندي كه خراب شده مي‌شود. ‏ اطالعات بازيافت مي‌تواند به آساني دور ريخته شود. ‏ ‏ ‏ ‏ ‏ محدود كردن گسترش اجراي مجدد يك فرايند هيچ وقت يتيم نخواهد شد .زيرا فرايند هميشه به حالتي كه شامل تعامل اخير با فراينديهاي ديگر يا دنياي خارج است ،باز مي‌گردد. Checkpointهاي قديمي‌تر و عامل‌هاي رخدادهاي غيرقطعي قبل از checkpointاخير مي‌توانند حذف شود. هزينه‌اي كه براي اين مزايا بايد پرداخت شود جريمه كارايي با واقعه نگاري سنكرون مي‌باشد. 36/50 ‏Rollback Fualt Tolerancy :كاهش سربار توسط روش Sender-Based Message Logging (SBML) را در حافظه موقت فرستندهm عامل‌هاي متناظر با انتقال پيامSMBL  .نگهداري مي‌كند . شامل محتوا و ترتيبي كه ارسال شده در دو مرحله ثبت مي‌شودm عامل‌هاي Before Sending m Sender logs its content in volatile memory Then receiver responds with an ack. includes order in which the message was delivered. Sender adds to the determinant ordering information فقط مي‌تواند يك خرابي را تحمل نمايد و رخدادهاي غيرقطعي داخل يك فرايندSMBL .را نمي‌تواند حل نمايد Rollback Fualt Tolerancy   37/50 كاهش سربار توسط روش: ‏Relaxing Logging Atomicity ‏ با ارسال پيام يا رخداد و تفاوت قائل شدن ميان ثبت آنها تا زماني كه ميزبان با ميزبان‌هاي ديگر يا دنياي خارج ارتباط برقرار نمايد. ‏ ‏ ‏ در P0ثبت پيام‌هاي m7 , m4تا زماني كه با فرايندهاي ديگر يا دنياي خارج در ارتباط هستند ،تغيير مي‌كند. پيام‌هاي m4و m7مجاز به اثر گذاري بر روي فرايند P0مي‌باشند ،اما اين اثر محلي است و فرايند ديگري يا دنياي خارح آن را نمي‌توانند ببينند تا اينكه پيام ثبت شود. ثبت رخداد و ارسال آن در اين واقعه‌نگاري خوشبينانه نمي‌تواند در عمليات يك لحظه‌اي انجام شود. ‏ 38/50 اين طرح مي‌تواند سربار را كاهش دهد ،زيرا چندين رخداد مي‌تواند در يك عملكرد كه باعث كاهش تعدد دسترسي به ‌stable storageمي‌شود ،ثبت شود .تاخير ارتباط بين فرايندي و صدور خروجي كاهش نمي‌يابد زيرا عمليات ثبت معموال قبل از ارسال پيام نياز است. ‏Rollback Fualt Tolerancy چگونه خوشبينانه بازيافت مي‌كند؟ • اگر در فرايندي خرابي رخ داد ،عامل‌ها در logموقتي آن از بين خواهند رفت. • روش خوشبينانه شرط هميشه بدون يتيم را پياده نمي‌كند. • پروتكل‌هاي خوشبينانه نياز به اين دارد كه چندين checkpointرا نگهداري نمايد. صدورخروجينيازمند هماهنگي چندين ميزبان مي‌باشد. ‏ • براي آسنكرون بودن ‏P0 roll back to ‏undo effects of ‏m7 ‏Need to ‏Commit ‏output ‏Orphan ‏Ask ‏to ‏log \ ‏P1 become ‏Orphan ‏Orphan \ ‏Restart ‏from B ‏instead D ‏X ‏Before m5 is ‏logged 39/50 ‏Log ‏P2 rollback ‏Rollback Fualt Tolerancy  Recoveryسنكرون ‏ ‏ ‏ همه فرايندها پروتكل Recoveryرا براي محاسبه بيشترين حالت قابل بازيافت سيستم، بر اساس وابستگي و اطالعات نگاشته شده انجام مي‌دهند .سپس Rollbackرا انجام مي‌دهند. وابستگي مستقيم انديس بازه فرستنده بر روي هر پيام خروجي براي اينكه به دريافت كننده اجازه دهد تا وابستگي كه مستقيما بواسطه پيام ايجاد شده ،ضبط نمايد. وابستگي متعدي وابستگي متعدي عموما سبب ايجاد سربار باالتري براي سوار شدن بر پيام‌ها و نگهداري بردار وابستگي مي‌شود .اما صدور خروجي و بازيافت سريعتري را به ارمغان مي‌آورد .روش آن به شكل زير است: ‏Each process Pi maintains a size-N vector TDi, where TDi[i] is ‏Pi’s current state interval index, & TDi[j], j≠i, records the ‏highest index of any state interval of Pj on which Pi depends. 40/50 ‏Rollback Fualt Tolerancy ‏ Multiple incarnations of the same process may coexist in the Asynchronous Recovery If a single failure causes a process to roll back an exponential number of times. In general which process Pi , i > 0, rolls back 2i-1 times in response to P0’s failure. Approach is to piggyback theloses original rollback announcement on any subsequent rollback announcement (P1 piggybacks r0 on r1). [i,x]: P0 fails th x interval of ithincarnation Rollback announceme nt r1 reaches P2 before r0 Rollback Fualt Tolerancy 41/50 P0 at X logged determinants of m0,m1,m2,m3,m4 m5 , m6 may be lost Determinant of each events contains: order in which its original receiver delivered the corresponding P0 will be able to guide the message. recovery of P1 , P2 since it knows the order in which P1 should replay messages m1 , m3 to reach the state from which P1 sends message m4. Notice information about m5,m6 is not available anywhere. Rollback Fualt Tolerancy 42/50 چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 43/50 ‏Rollback Fualt Tolerancy :مقايسه Rollback Fualt Tolerancy 44/50 چارچوب مطالب ‏ ‏ ‏ ‏ ‏ ‏ مقدمه تعاريف پروتكل‌هاي checkpointing پروتكل‌هاي بر مبناي واقعه‌نگاري مقايسه مراجع 45/50 ‏Rollback Fualt Tolerancy Survey   E. N. Elnozahy, D. B. Johnson, and Y. M. Wang, "A survey of rollback-recovery protocols in messagepassing systems," Tech. Rep. No. CMU-CS-96-181, Dept. of Computer Science, Carnegie Mellon University, 1996. L. Alvisi and K. Marzullo, "Message Logging: Pessi mistic, Optimistic, and Causal," Proceedings of the 15th IEEE International Conference on Distributed Computing Systems. Vancouver, Canada, June 1995, pp. 229-236. Rollback Fualt Tolerancy 46/50 Model & Consistency        K. M. Chandy and L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems," ACM Trans. on Computer Syst., vol. 3, no.1, pp. 63-75, Feb. 1985. Y. M. Wang, A. Lowry, and W. K. Fuchs, "Consistent global checkpoints based on direct dependency tracking," Information Processing Letters, Vol. 50, No. 4, pp. 223-230, May 1994. Y. M. Wang, "Maximum and minimum consistent global checkpoints and their applications," in Proc. IEEE Symp. Reliable Distributed Syst. (SRDS), pp. 86--95, Sept. 1995. Jian Xu and Robert H. B. Netzer, "Necessary and Sufficient Conditions for Consistent Global Snapshots,"(cs93-32.ps), IEEE Trans. on PADS., Vol. 6, No. 2, February 1995. D. Manivannan and M. Singhal, "A Low-overhead Recovery Technique Using Quasi-Synchronous Checkpointing," In Proceedings of the 16th International Conference on Distributed Computing Systems, May 1996, pages 100-107. D. Manivannan, Robert H. B. Netzer and M. Singhal, "Finding Consistent Global Checkpoints in a Distributed Computation," (OSU-CISRC-3/96-TR16) In IEEE Transactions on Parallel and Distributed Systems, 8(6):623-627, June 1997. D. Manivannan and M. Singhal, "Quasi-Synchronous Checkpointing: Models, Characterization, and Classification," Submitted to IEEE Transactions on Parallel and Distributed Systems.(1999) Rollback Fualt Tolerancy 47/50 Checkpointing (No logging)       Jian Xu and Robert H. B. Netzer, "Adaptive Independent Checkpointing for Reducing Rollback Propagation," (cs93-25.ps) In Proc. 5th IEEE Symp. on Parallel and Distributed Processing, pages 754-761, December 1993. B. Bhargava and S. R. Lian, "Independent Checkpointing and Concurrent Rollback for Recovery - An Optimistic Approach," In Proc. of IEEE Symp. on Reliable Distributed Syst., pp. 2-12, 1988. R. Koo and S. Toueg, "Checkpointing and Rollback-Recovery for Distributed Systems," IEEE Trans. on Software Eng., vol. SE-13, no. 1, pp. 23-31, Jan. 1997. J. L. Kim and T. Park, "An Efficient Protocol for Checkpointing Recovery in Distributed Systems," IEEE Trans. on Parallel and Distributed Syst., vol. 4, no. 8, pp. 955-960, Aug. 1993. Y. M. Wang and W. K. Fuchs, "Lazy checkpoint coordination for bounding rollback propagation," in Proc. IEEE Symp. on Reliable Distributed Systems (SRDS-12), pp. 78--85, Oct. 1993. Y. M.Wang, P. Y. Chung, I. J. Lin, andW. K. Fuchs. “Checkpoint space reclamation for uncoordinated checkpointing in messagepassing systems.” IEEE Trans. Parallel and Distributed Syst., 6(5):546–554, May 1995. Rollback Fualt Tolerancy 48/50 Implementation & Performance       Elmootazbellah Nabil Elnozahy, David B. Johnson, and Willy Zwaenepoel, "The Performance of Consistent Checkpointing," In Proceedings of the 11th Symposium on Reliable Distributed Systems, pp. 39-47, IEEE Computer Society, Houston, TX, October 1992. Y. Huang, C. Kintala, and Y. M. Wang, "Software Tools and Libraries for Fault Tolerance," in Bulletin of the Technical Committee on Operating Systems and Application Environment (TCOS), Vol. 7, No. 4, pp. 5--9, Winter, 1995. Y. M. Wang, Y. Huang, K.-P. Vo, P. Y. Chung, and C. Kintala, "Checkpointing and its applications," in Proc. IEEE Fault-Tolerant Computing Symposium (FTCS-25), pp. 22-31, June 1995. Roberto Baldoni, Jean Michel Helary, Achour Mostefaoui, Michel Raynal. “Consistent Checkpointing in Message Passing Distributed Systems”. Institut National de Recherche en Informatique et en Automatique, Juin, 1995. Gerard P. Kavanaugh and William H. Sanders. “Performance Analysis of two Time- Based Coordinated Checkpointing Protocols.” Center for Reliable & High-Performance Computing Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, From Pacfic Rim International Symposium on Fault-Tolerant Systems, Taipei, Taiwan, December 15-16, 1997. B. Bhargava and S. R. Lian. “Independent checkpointing and concurrent rollback for recovery - An optimistic approach.” In Proc. IEEE Symp. Reliable Distributed Syst., pages 3–12, 1988. Rollback Fualt Tolerancy 49/50 Miscellaneous        E. Cohen, Y. M. Wang, and G. Suri, "When piecewise determinism is almost true," in Proc. Pacific Rim International Symposium on Fault-Tolerant Systems, pp. 66--71, Dec. 1995. Y. M. Wang, P. Y. Chung, and W. K. Fuchs, "Tight upper bound on useful distributed system checkpoints," Tech. Rep. CRHC-95-16, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1995. Ramamurthy, B., Upadhyaya, S., Bhargava, B., "Design and analysis of an integrated checkpointing and recovery scheme for distributed applications," IEEE Transactions on Knowledge and Data Engineering, Volume: 12 Issue: 2, March-April 2000 Page(s): 174 -186 Dan Pei, Dongsheng Wang, Meiming Shen, Weimin Zheng, "Design and implementation of a low-overhead file checkpointing approach," High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on, Volume: 1 , 2000 Page(s): 439 -441 vol.1 Meth, K.Z., Tuel, W.G., "Parallel checkpoint/restart without message logging," International Workshops on Parallel Processing, 2000. Page(s): 253 -258 Yi Zhang, Jianping Hu "Checkpointing and process migration in network computing environment," Info-tech and Info-net, 2001. Proceedings. ICII 2001 - Beijing. 2001 International Conferences on, Volume: 3 , 2001 Kasbekar, M.; Das, C.R., "Selective checkpointing and rollbacks in multithreaded distributed systems," Distributed Computing Systems, 2001. 21st International Conference on. , 2001 Page(s): 39 -46 Rollback Fualt Tolerancy 50/50