19408

۱۹۴۰۸

روشي براي همگام سازي اعتمادپذير زمان در سيستمهاي توزيعي

كارشناسي ارشد

نرم افزار

۱۳۹۵

۱۳۹۷/۶/۲۶

دكتر محمد عبداللهي ازگمي

كامپيوتر

انسان ها و سيستم‌هاي كامپيوتري با هم در تعامل هستند. انتظار داريم كه سيستم‌هايي كه با آن‌ها در تعامل هستيم، رفتاري سازگار با رفتارهاي گذشته‌ي خود نشان دهند. همچنين، انتظار داريم كه يك سيستم توزيعي نسبت به موقعيت جغرافيايي اجزاء توزيع شده، شفاف بوده و همانند يك سيستم متمركز به ما پاسخگو باشد. در اينجا مسأله اين است كه چطور اين رفتار سازگار، توسط يك سيستم توزيعي در حوزه‌ي همگام‌سازي زمان (ساعت) تضمين شود. به نظر مي آيد كه مسأله‌ي اجماع توزيعي، در قلب اين مسأله جاي داشته باشد. انگيزه‌ي اصلي اين پژوهش ارائه‌ي روشي براي تضمين رفتار سازگار سيستم و عدم نمايش رفتار ناهنجار براي كاربران بوده است. هدف آن است كه روش ارائه شده را در قالب يك سرويس فراهم كنيم تا براي گروه بزرگي از كاربران و برنامه‌هاي كاربردي قابل استفاده باشد. براي حل مسأله‌ي رفتار ناهنجار، يك بازي تحت عنوان «بازي ساعت‌ها» مطرح كرده ايم. اين مسأله به‌عبارت ساده، يك ناسازگاري در رفتار سيستم بوده كه توسط كاربران قابل مشاهده است. تلاش شده است كه روش ارائه شده براي حل مسأله را نسبت به وقوع «خرابي‌هاي سقوط» تحمل‌پذير نماييم. در اين پژوهش، چهار رُكن اساسي محاسبات «اعتمادپذير» را نيز در نظر گرفته ايم و تأكيد ما بيشتر بر قابليت اطمينان و تحمل خرابي‌هاي سقوط بوده است. در اين پايان نامه، روشي براي حل مسأله‌ي رفتار ناهنجار ارائه كرده ايم كه مبتني بر ساعت‌هاي منطقي است. با قرار دادن پردازه‌ها در يك ساختار درخت دودويي و اعمال تغيير جزئي در يكي از قواعد جلو بردن ساعت منطقي، سعي در برطرف نمودن رفتار ناهنجار سيستم به‌صورت كامل شده است. در مورد تحمل‌پذير بودن نسبت به خرابي، با اضافه نمودن اشاره‌گرهايي در پردازه‌ها كه به ساير گره‌ها اشاره مي‌كنند سعي كرده ايم با وقوع خرابي‌هاي سقوط مقابله نماييم. براي ارزيابي طرح پيشنهادي، يك شبيه‌ساز طراحي كرده ايم تا پندار اصلي مقابله با رفتار ناهنجار در عدم حضور خرابي‌هاي سقوط را نشان دهيم. سپس يك پياده‌سازي واقعي از الگوريتم را انجام داده¬ايم تا رفتار آن در محيط حقيقي با حضور خرابي‌هاي سقوط را مشاهده كنيم. اين برنامه‌ي پياده‌سازي شده، توسط ماشين‌هاي مجازي اجرا شده كه با يكديگر تشكيل يك سيستم واقعي را مي‌دهند. همچنين، استدلال‌هاي منطقي درباره‌ي صحّت تصميم‌هاي اتخاذ شده در روش پيشنهادي ارائه شده است.

1397/07/04

A Method for Trustworthy Time Synchronization in Distributed Systems

9/17/2018 12:00:00 AM

Humans and computer systems interact with each other. We expect the systems we are interacting exhibit consistent behavior with respect to their past behavior. We also expect a distributed system to be transparent with respect to the geographical position of objects, and to be responsive to us as a centralized system is. The problem here is how to guarantee this consistent behavior of a distributed system in the field of time (clock) synchronization. It appears that the problem of distributed consensus lies at the heart of this problem. The main motivation of this research is to present a method to guarantee the system’s consistent behavior, and not to exhibit anomalous behavior to its users. The aim has been to provide the proposed method as a service in order to be usable for a large group of users and applications. We have presented a game, entitled as: “The Game of Clocks”, in order to solve the problem of anomalous behavior. In simple words, this problem is an inconsistency in the system’s behavior, which is observable by its users. Efforts have been made to make the proposed method for solving the problem fault-tolerant with respect to the occurrence of crash failures. In this research, we have also considered the four pillars of “Trustworthy Computing," and our emphasis has been more on the reliability and tolerating crash failures. In this thesis, we have proposed a method for solving the problem of anomalous behavior, which is based on logical clocks. Efforts have been made to completely eliminate the anomalous behavior, by placing processes in a binary tree structure and applying a minor change in one of the clock advancement rules of logical clocks. In terms of being tolerant with respect to failure, we have tried to stand with the occurrence of crash failures by adding pointers in processes, which point to other nodes. In order to evaluate the proposed method, we have designed a simulator to show the main idea of standing the anomalous behavior in the absence of failures. Then, we have done a real implementation of the method in order to show its behavior in a real environment in the presence of crash failures. The implemented program is executed in virtual machines, which constitute a real system together. We have also presented the logical reasoning about the correctness of the decisions we have made in the proposed method.