Distributed Algorithms for Message-Passing Systems

محاسبات توزیع شده در قلب بسیاری از برنامه ها قرار دارد. به محض اینکه شخص مجبور شود مشکلی را از نظر موجودیت‌هایی حل کند - مانند فرآیندها، همتایان، پردازنده‌ها، گره‌ها یا عامل‌ها - که به صورت جداگانه فقط اطلاعات جزئی از بسیاری از پارامترهای ورودی مرتبط با مشکل را دارند. به طور خاص، هر نهادی که در جهت هدف مشترک همکاری می کند، نمی تواند از وضعیت فعلی موجودیت های دیگر آگاهی آنی داشته باشد. در حالی که محاسبات موازی عمدتاً با «کارایی» سروکار دارد و محاسبات بلادرنگ عمدتاً با «محاسبات به‌موقع» سروکار دارد، محاسبات توزیع‌شده عمدتاً به «تسلط بر عدم قطعیت» ناشی از مسائلی مانند تعدد جریان‌های کنترل، ارتباطات ناهمزمان مربوط می‌شود. رفتارهای ناپایدار، تحرک و پویایی.

در حالی که برخی از الگوریتم‌های توزیع‌شده فقط از چند خط تشکیل شده‌اند، درک رفتار آنها دشوار است و بیان و اثبات ویژگی‌های آنها دشوار است. هدف این کتاب این است که مفاهیم، ​​مفاهیم و الگوریتم های اساسی محاسبات توزیع شده را در زمانی که موجودیت های توزیع شده با ارسال و دریافت پیام در بالای یک شبکه ناهمزمان همکاری می کنند، به صورت جامع ارائه دهد. این کتاب از هفده فصل تشکیل شده است که در شش بخش ساختار یافته است: الگوریتم های نمودار توزیع شده، به ویژه آنچه آنها را از الگوریتم های متوالی یا موازی متفاوت می کند. زمان منطقی و حالات جهانی، هسته اصلی کتاب؛ طرد متقابل و تخصیص منابع؛ انتزاعات ارتباطی سطح بالا؛ تشخیص پراکنده خواص؛ و حافظه مشترک را توزیع کرد. نویسنده اهداف روشنی را در هر فصل تعیین می‌کند و محتوا در سراسر آن با مثال‌های گویا، خلاصه‌ها، تمرین‌ها و کتاب‌شناسی مشروح پشتیبانی می‌شود.

این کتاب مقدمه‌ای برای محاسبات توزیع‌شده است و مناسب است. برای دانشجویان پیشرفته کارشناسی یا دانشجویان کارشناسی ارشد در علوم کامپیوتر و مهندسی کامپیوتر، دانشجویان کارشناسی ارشد در ریاضیات علاقه مند به محاسبات توزیع شده، و پزشکان و مهندسان درگیر در طراحی و اجرای برنامه های کاربردی توزیع شده. خواننده باید دانش پایه ای از الگوریتم ها و سیستم عامل ها داشته باشد.

Distributed computing is at the heart of many applications. It arises as soon as one has to solve a problem in terms of entities -- such as processes, peers, processors, nodes, or agents -- that individually have only a partial knowledge of the many input parameters associated with the problem. In particular each entity cooperating towards the common goal cannot have an instantaneous knowledge of the current state of the other entities. Whereas parallel computing is mainly concerned with 'efficiency', and real-time computing is mainly concerned with 'on-time computing', distributed computing is mainly concerned with 'mastering uncertainty' created by issues such as the multiplicity of control flows, asynchronous communication, unstable behaviors, mobility, and dynamicity.

While some distributed algorithms consist of a few lines only, their behavior can be difficult to understand and their properties hard to state and prove. The aim of this book is to present in a comprehensive way the basic notions, concepts, and algorithms of distributed computing when the distributed entities cooperate by sending and receiving messages on top of an asynchronous network. The book is composed of seventeen chapters structured into six parts: distributed graph algorithms, in particular what makes them different from sequential or parallel algorithms; logical time and global states, the core of the book; mutual exclusion and resource allocation; high-level communication abstractions; distributed detection of properties; and distributed shared memory. The author establishes clear objectives per chapter and the content is supported throughout with illustrative examples, summaries, exercises, and annotated bibliographies.

This book constitutes an introduction to distributed computing and is suitable for advanced undergraduate students or graduate students in computer science and computer engineering, graduate students in mathematics interested in distributed computing, and practitioners and engineers involved in the design and implementation of distributed applications. The reader should have a basic knowledge of algorithms and operating systems.