آشنایی با الگوریتم‌های خودتثبیت‌گر توزیع‌شده ۲۰۲۲
Introduction to Distributed Self-Stabilizing Algorithms 2022

این کتاب با هدف ارائه یک مقدمه جامع و آموزشی به مفهوم «خود-پایدارسازی» (Self-Stabilization) تدوین شده است، مفهومی که نخستین بار توسط ادسخر وایبه دیکسترا در سال 1973 معرفی شد. خود-پایدارسازی به توانایی یک الگوریتم توزیع‌شده برای همگرا شدن در یک زمان محدود به یک پیکربندی گفته می‌شود که از آن نقطه به بعد، رفتار الگوریتم صحیح خواهد بود (یعنی مطابق با یک مشخصه معین). این پیکربندی اولیه دلخواه می‌تواند ناشی از وقوع تعدادی محدود از خطاهای گذرا باشد. بنابراین، خود-پایدارسازی در واقع به عنوان یک رویکرد تحمل خطای غیرپوششی همه‌کاره در نظر گرفته می‌شود، زیرا از اثر هر تعداد محدودی از این خطاها به شکلی یکپارچه بهبود می‌یابد. یکی دیگر از جنبه‌های مهم این روش بازیابی خودکار، دشواری تنظیم مجدد دستگاه‌های دچار نقص در یک سیستم توزیع‌شده بزرگ (و بنابراین، گسترده از نظر جغرافیایی) است (اینترنت، شبکه‌های همتا به همتا و شبکه‌های تحمل‌پذیر تاخیر، نمونه‌هایی از این سیستم‌های توزیع‌شده هستند). علاوه بر این، خود-پایدارسازی معمولاً به عنوان یک ویژگی سبک‌وزن برای دستیابی به تحمل خطا در مقایسه با سایر رویکردهای کلاسیک تحمل خطا شناخته می‌شود. در واقع، سربار الگوریتم‌های خود-پایدارساز پیشرفته، هم از نظر زمان و هم از نظر فضا، معمولاً کم است. این امر خود-پایدارسازی را برای سیستم‌های توزیع‌شده مجهز به پردازنده‌هایی با قابلیت‌های محاسباتی و حافظه‌ای پایین، مانند شبکه‌های حسگر بی‌سیم، بسیار جذاب می‌کند.

پس از بیش از 40 سال، خود-پایدارسازی اکنون به اندازه کافی به عنوان یک زمینه مهم تحقیقاتی در محاسبات توزیع‌شده نظری تثبیت شده است تا تدریس آن را در دوره‌های تحصیلات تکمیلی پیشرفته و پژوهش‌محور توجیه کند. این کتاب یک دوره مقدماتی است که شامل تعریف رسمی خود-پایدارسازی و مفاهیم مرتبط با آن، و به دنبال آن بررسی و مطالعه عمیق الگوریتم‌های کلاسیک (ساده)، طرح‌های اثبات و الگوهای طراحی رایج، و همچنین نتایج برجسته حاصل از جامعه خود-پایدارسازی است. همانطور که اغلب در حوزه خود-پایدارسازی اتفاق می‌افتد، در این کتاب بر اثبات صحت و پیچیدگی تحلیلی الگوریتم‌های خود-پایدارساز توزیع‌شده مورد مطالعه تمرکز می‌کنیم.

در نهایت، تاکید می‌کنیم که بیشتر الگوریتم‌های مورد مطالعه در این کتاب در واقع به مدل *حالت-اتمی* سطح بالا اختصاص داده شده‌اند، که رایج‌ترین مدل محاسباتی در حوزه خود-پایدارسازی است. با این حال، در فصل آخر، تکنیک‌های کلی برای دستیابی به خود-پایدارسازی در مدل گذر پیام سطح پایین، و همچنین نمونه‌هایی از الگوریتم‌ها را ارائه می‌دهیم.

This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization, introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in an unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweight property to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks.

After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms.

Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model, which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms.