Эта книга рассчитана на курс по распределенным алгоритмам для студентов старших курсов и аспирантов по специальностям, связанным с информатикой и программной инженерией. Она также может быть использована в качестве справочника исследователями в этих областях. Книга делает упор на базовые алгоритмы и результаты, полученные в сфере распределенных вычислений. Рассматриваемые в ней алгоритмы в основном относятся к «классическим» и были выбраны в первую очередь потому, что поучительны с точки зрения проектирования алгоритмов для распределенных систем или проливают свет на ключевые проблемы в распределенном и параллельном программировании.Книга состоит из двух частей. Первая часть посвящена взаимодействию процессов посредством передачи сообщений. Она сформировалась на основе курса, читаемого в университете Врийе (Амстердам), изначально основанного на учебнике «Введение в распределенные алгоритмы» Герарда Теля. Вторая часть посвящена архитектурам с общей памятью.
Введение
Алгоритм — это пошаговая процедура, направленная на решение конкретной проблемы компьютером. Чтобы стать квалифицированным программистом, необходимо иметь хорошее понимание алгоритмов. Всякая образовательная программа в области информатики предлагает один или несколько курсов, посвященных основам алгоритмизации. Обычно они рассматривают алгоритмы поиска и сортировки, распознавания образов и нахождения кратчайших путей в графах. Они учат студентов выявлять такие подзадачи в своих компьютерных программах и эффективно их решать. Более того, студенты учатся мыслить алгоритмически, доказывать корректность алгоритмов и производить простейший анализ сложности.
Распределенные вычисления гораздо сложнее однопроцессорных и сильно отличаются от них, поскольку выполнение частей задачи на узлах распределенной системы перемежается во времени. Когда два узла параллельно выполняют некоторые действия, невозможно предсказать, которое из них будет выполнено раньше по времени. Это приводит, например, к так называемому эффекту гонок: когда два сообщения приходят к одному узлу в сети, поведение узла может зависеть от того, какое из сообщений придет раньше. Распределенные системы, таким образом, недетерминированы по своей природе — запуск системы дважды в одной конфигурации из одного и того же начального состояния может привести к различным результатам. При этом количество достижимых состояний имеет свойство расти экспоненциально с увеличением количества узлов.
Еще одно важное различие между распределенными и однопроцессорными вычислениями состоит в том, что узлы в распределенной системе в общем случае не имеют актуальных сведений о глобальном состоянии системы. Им известны собственные локальные состояния, но они не всегда знают о локальных состояниях других узлов или сообщениях, находящихся в процессе передачи. Например, проблематичным становится определение момента завершения выполнения. Должно быть установлено, что все узлы в системе завершили работу, но даже в этом случае может оказаться, что все еще передается некоторое сообщение, которое вызовет активизацию принимающего узла.
Данная книга предлагает вашему вниманию широкий спектр базовых алгоритмов, решающих такие ключевые проблемы в распределенных системах, как определение момента завершения вычислений и совместное построение узлами снимка глобального состояния системы. Основной ее целью является формирование у студентов алгоритмического склада ума, чтобы они могли распознавать и решать фундаментальные проблемы в области распределенных вычислений. Их вниманию предлагается всесторонний обзор этих проблем с высоты птичьего полета, а также доказательства корректности «на пальцах» и приближенные способы оценки сложности.
Две основные коммуникационные парадигмы в распределенных вычислениях — обмен сообщениями, когда узлы пересылают друг другу сообщения по каналам, и общая память, когда разные исполняемые потоки могут читать и писать в общие области памяти. Книга разделена на две части, посвященные этим двум коммуникационным парадигмам. Оставшаяся часть введения дает предварительную информацию, применимую к обоим подходам.
Множества
Как обычно, S1 ∪ S2, S1 \ S2, и S1 ⊆ S2 обозначают объединение, разность и включение множеств; s ∈ S значит, что s — элемент множества S. Множества натуральных и действительных чисел обозначены и соответственно. Булевы (логические) переменные имеют значения true (истина) и false (ложь). Множество может быть записано в виде {…|…}, где слева от вертикальной черты указываются его элементы, а справа задается условие, которому они должны удовлетворять. Например, {n ∈ | n > 5} представляет собой множество натуральных чисел больше 5. Пустое множество обозначается символом Ø. Для любого конечного множества S количество элементов в нем обозначается |S|.
Меры сложности
Меры сложности показывают, как потребление ресурсов (сообщений, времени, памяти) растет относительно размера входных данных. Например, если в худшем случае алгоритм имеет сложность по сообщениям O(n2), то для входных данных размера n алгоритм в худшем случае требует передачи порядка n2 сообщений плюс-минус константа.
Часть 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.
Упражнения
» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — Алгоритмы
К сожалению, книга доступна только в бумажном виде.
