Книга «Розподілені алгоритми. Інтуїтивний підхід»

image Ця книга розрахована на курс з розподіленим алгоритмів для студентів старших курсів та аспірантів за спеціальностями, пов'язаними з інформатикою та програмною інженерією. Вона також може бути використана в якості довідника дослідниками в цих областях. Книга робить упор на базові алгоритми і результати, отримані в сфері розподілених обчислень. Розглянуті в ній алгоритми в основному відносяться до «класичним» і були обрані у першу чергу тому, що повчальні з точки зору проектування алгоритмів для розподілених систем або проливають світло на ключові проблеми в розподіленому і паралельному програмуванні.

Книга складається з двох частин. Перша частина присвячена взаємодії процесів за допомогою передачі повідомлень. Вона сформувалася на основі курсу, що читається в університеті Врийе (Амстердам), спочатку заснованого на підручнику «Вступ до розподілені алгоритми» Герарда Теля. Друга частина присвячена архітектурі із загальною пам'яттю.

Введення
Алгоритм — це покрокова процедура, спрямована на вирішення конкретної проблеми комп'ютером. Щоб стати кваліфікованим програмістом, необхідно мати хороше розуміння алгоритмів. Кожна освітня програма в галузі інформатики пропонує один або кілька курсів, присвячених основам алгоритмізації. Зазвичай вони розглядають алгоритми пошуку та сортування, розпізнавання образів і знаходження найкоротших шляхів у графах. Вони вчать студентів виявляти такі підзадачі в своїх комп'ютерних програмах та ефективно їх вирішувати. Більше того, студенти вчаться алгоритмічно мислити, доводити коректність алгоритмів і виробляти найпростіший аналіз складності.

Розподілені обчислення набагато складніше однопроцесорних і сильно відрізняються від них, оскільки виконання частин завдання на вузлах розподіленої системи перемежовується у часі. Коли два вузла паралельно виконують деякі дії, неможливо передбачити, яка з них буде виконано раніше за часом. Це призводить, наприклад, до так званого ефекту гонок: коли два повідомлення приходять до одного вузла в мережі, поведінка сайту може залежати від того, яке з повідомлень прийде раніше. Розподілені системи, таким чином, недетерминированы за своєю природою — запуск системи двічі в одній конфігурації з одного і того ж початкового стану може призвести до різних результатів. При цьому кількість досяжних станів має властивість рости експоненціально зі збільшенням кількості вузлів.

Ще одна важлива відмінність між розподіленими і однопроцесорними обчисленнями полягає в тому, що вузли в розподіленій системі в загальному випадку не мають актуальних відомостей про глобальне стан системи. Їм відомі власні локальні стану, але вони не завжди знають про локальних станах інших вузлів або повідомленнях, що перебувають у процесі передачі. Наприклад, стає проблематичним визначення моменту завершення виконання. Має бути встановлено, що всі вузли у системі завершили роботу, але навіть в цьому випадку може виявитися, що все ще передається деяке повідомлення, яке викличе активізацію приймаючого вузла.

Дана книга пропонує вашій увазі широкий спектр базових алгоритмів, які вирішують такі ключові проблеми в розподілених системах, як визначення моменту завершення обчислень і спільне побудова вузлами знімка глобального стану системи. Основною її метою є формування у студентів алгоритмічного складу розуму, щоб вони могли розпізнавати і вирішувати фундаментальні проблеми в області розподілених обчислень. Їх увазі пропонується всебічний огляд цих проблем з висоти пташиного польоту, а також докази коректності «на пальцях» і наближені способи оцінки складності.

Дві основні комунікаційні парадигми в розподілених обчисленнях — обмін повідомленнями, коли вузли пересилають один одному повідомлення по каналах, і спільна пам'ять, коли різні виконувані потоки можуть читати і писати в загальні області пам'яті. Книга розділена на дві частини, присвячені цим двом комунікаційним парадигм. Решта введення дає попередню інформацію, яка застосовується до обох підходів.

Безлічі
Як зазвичай, S1 ∪ S2, S1 \ S2, S1 ⊆ S2 позначають об'єднання, різниця і включення множин; s ∈ S означає, що s — елемент множини S. Безлічі натуральних і дійсних чисел позначені і відповідно. Булеві (логічні) змінні мають значення true (істина) і false (неправда). Множина може бути записано у вигляді {...|...}, де зліва від вертикальної риски зазначаються його елементи, а праворуч задається умова, яким вони повинні задовольняти. Наприклад, {n ∈ | n > 5} являє собою безліч натуральних чисел не більше 5. Порожня множина позначається символом Ø. Для будь-якого кінцевого безлічі S-кількість елементів у ньому позначається |S|.

Міри складності
Заходи складності показують, як споживання ресурсів (повідомлень, часу, пам'яті) зростає щодо розміру вхідних даних. Наприклад, якщо в гіршому випадку алгоритм має складність за повідомленнями O(n2), то для вхідних даних розміру n алгоритм у гіршому випадку вимагає передачі порядку n2 повідомлень плюс-мінус константа.

image

image
Частина I, присвячена парадигмі обміну повідомленнями, в основному розглядає складність за повідомленнями. Складність по бітам цікава тільки тоді, коли повідомлення можуть бути дуже довгими. При аналізі тимчасової складності ми припускаємо, що обробка подій не вимагає часу і отримання повідомлення займає максимум одну одиницю часу після його відправлення. Різні запуски можуть призводити до різного споживання ресурсів. Ми розглядаємо складність для гіршого випадку і середню складність, причому для останньої наводимо деякий імовірнісний розподіл по всім запусків.

Відносини порядку
Відношенням (строгого порядку на множині S називається иррефлексивное, асиметричне і транзитивное бінарне відношення на його елементах. Це означає, що для будь-яких a, b, c ∈ S не виконується a < a; якщо a < b, то не виконується b < a; якщо a < b і b < c, то a < c. Порядок називається строгою, якщо для будь-яких різних a, b ∈ S або a < b, або b < a; в іншому випадку порядок називається частковим. Нехай дано дві множини S1 та S2 з відносинами порядку <1 і <2 відповідно. Тоді відношення лексикографічного порядку < на парах з S1 × S2 визначається як (a1, a2) < (b1, b2), або якщо a1 <1 b1, або a1 = b1 і a2 <2 b2. Якщо <1 і <2 є відносинами суворого порядку, то і відповідне ставлення лексикографічного порядку > буде відношенням строгого порядку.

Модульна арифметика
Цілісне кільце з натурального позитивного модулю n представлено елементами {0… n − 1}. Всяке ціле k має репрезентативний залишок від ділення на n, позначається k mod n, який є єдиним ℓ ∈ {0… n − 1}, таких, що k − ℓ ділиться націло на n. Це означає, що по досягненні n відбувається циклічний повернення: n mod n 0, (n + 1) mod n-1 і т. д. Додавання і віднімання переносяться на модульну арифметику прямолінійним чином: (j mod n) + (k mod n) = (j + k) mod n та (j mod n) · (k mod n) = (j · k) mod n.

Вправи
image
» Більш докладно з книгою можна ознайомитися на сайті видавництва
» Зміст
» Уривок

Для Хаброжителей знижка 25% по купону — Алгоритми
На жаль, книга доступна тільки в паперовому вигляді.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.