Связь. Связь между процессами свойственна распределенным системам: если процессы не связываются, каждый процесс функционирует в изоляции от других процессов и должен изучаться в изоляции, a не как часть распределенной системы. Когда процессы сотрудничают в вычислении, связь необходима, если один процесс нуждается в промежуточном результате, произведенном другим процессом. Также, синхронизация необходима, потому что вышеупомянутый процесс должен быть приостановлен, пока результат не доступен. Прохождение cообщения затрагивает, и связь и синхронизацию; общедоступная память затрагивает только связь: дополнительная осторожность должна быть предусмотрена для синхронизации процессов, которые сообщаются c использованием общедоступной памяти. В языках, которые обеспечивают передачу сообщения, доступны операции "посылать" и "получать". Связь происходит выполнением посылающейся операции в одном процессе (следовательно названным процессом отправителя) и получающейся операцией в другом процессе (процесс приемника). Параметры посылающей операции - адрес приемника и дополнительные данные, формирующие содержание сообщения. Эти дополнительные данные становятся доступными приемнику, когда получающая инструкция выполнена, то есть, таким образом осуществляет связь. Получающая операция может быть завершена только после того, как посылающая операция была выполнена, что и осуществляет синхронизацию. В некоторых языках получающая операция не доступна явно; вместо этого, процедура или операция активизируется неявно, когда сообщение получено. Язык может обеспечивать синхронное прохождение сообщения, когда посылающая операция завершена только после выполнения получающей операции.
Другими словами, отправитель блокирован, пока сообщение не было получено, и имеет место двухсторонняя синхронизация между результатами приемника и отправителем. Сообщения могут быть посланы двухточечно, то есть, от одного отправителя на один приемник, или широковещательно, когда то же самое сообщение получено всеми приемниками. Термин мультиприведение также используется, чтобы обратиться к сообщениям, которые посланы совокупности (не обязательно всех) процессов. Несколько более структурированный примитив связи - удаленный вызов процедуры (RPC). Чтобы связываться с процессом b, процедура a обращается к процедуре, представленной в процессе b, посылая параметры процедуры в сообщении; а приостанавливается, пока результат процедуры не будет возвращен в другом сообщении. Вариант для прохождения сообщения - использование общедоступной памяти для связи; один процесс пишет значение переменной, и другой процесс читает значение. Синхронизация между процессами тяжелее, чтобы ее достигнуть, потому что чтение переменной может быть использовано прежде, чем переменная была записана. При использовании примитивов синхронизации типа семафоров [Dij68] или мониторов [Hoa78], возможно выполнить передачу сообщения, в среде общедоступных переменных. И наоборот, также возможно выполнить (виртуальную) общедоступную память в передающей сообщения среде, но это очень неэффективно.
Недетерменизм. В многих точках в выполнении процесс может быть способен продолжиться различными способами. Получающая операция часто недетерминирована, потому что это позволяет получение сообщений от различных отправителей. Дополнительные способы выражать недетерменизм основаны на охраняемых командах. Охраняемая команда в наиболее общей форме - список инструкций, каждый предшествованный булевым выражением (его защитником). Процесс может продолжать выполнение с любой из инструкций, для которых соответствующая защита оценивается истиной. Защита может содержать получающую операцию, когда она оценивается истиной, если имеется сообщение, доступное, чтобы быть полученным.
Предыдущие разделы дали причины для использования распределенных компьютерных систем и объяснили характер этих систем; потребность программировать эти системы возникает как следствие. Программирование распределенных систем должно быть основано на использовании правильных, гибких, и эффективных алгоритмов. В этом разделе обсуждается, что разработка распределенных алгоритмов - ремесло, совершенно различное по характеру от ремесла, используемого в разработке централизованных алгоритмов. Распределенные и централизованные системы отличаются по ряду существенных отношений, обрабатываемых в Подразделе 1.3.1 и иллюстрируемых в 1.3.2 Подразделе. Распределенное исследование алгоритмов следовательно развилось как независимое поле научного исследования; см. 1.3.3 Подраздел. Эта книга предназначена, чтобы представить читателю это поле исследования. Цели книги и выбора результатов, включенных в книгу установлены в Подразделе 1.3.4.
1.3.1 Распределенный против Централизованных Алгоритмов
Распределенные системы отличаются от централизованных компьютерных систем по трем существенным отношениям, которые мы теперь обсуждаем.
(1) Недостаток знания глобального состояния. В централизованных решениях управление алгоритмом может быть сделано основанным на наблюдениях состояния системы. Даже при том, что к всему состоянию обычно нельзя обращаться в одиночной машинной операции, программа может осматривать переменные один за другим, и принимать решение, в конце концов релевантная информация будет расценена. Никакие данные не изменяются между проверкой и решением, и это гарантирует целостность решения. Узлы в распределенной системе имеют доступ только к их собственному состоянию и не к глобальному состоянию всей системы. Следовательно, не возможно делать решение управления основанным на глобальном состоянии. Это имеет место тот факт, что узел может получать информацию относительно состояния других узлов и базировать решения управления на этой информации. В отличие от централизованных систем, факт, что полученная информация является старой, может стать причиной получения недопустимой информации, потому что состояние другого узла, возможно, изменилось между посылкой информации состояния и решения, основанного на этом. Состояние подсистемы связи (то есть, какие сообщения находятся в транзите в некоторый момент) никогда непосредственно не наблюдается узлами. Эта информация может только быть выведена косвенно, сравнивая информацию относительно сообщений, посланных и полученных узлами. Недостаток глобального кадра времени. События, составляющие выполнение централизованного алгоритма полностью упорядочиваются естественным способом их временным появлением; для каждой пары событий, каждое происходит ранее или позже чем другое. Временное отношение, вызванное на событиях, составляющих выполнение распределенного алгоритма - не общее количество; Для некоторых пар событий может иметься причина для решения, что каждое происходит перед другим, но для других пар имеет место, что ни одно из событий не происходит перед другим [Lam78]. Взаимное исключение может быть достигнуто в централизованной системе требующих его, если доступ процесса p к ресурсу начинается позже чем доступ процесса q, то доступ процесса p начался после того, как доступ процесса q закончился. Действительно, все такие события (старт и окончание доступа процессов p и q) полностью упорядочиваются отношением временного предшествования; в распределенной системе они - не упорядочиваются, и та же самая стратегия не достаточна. Процессы p и q могут начать обращаться к ресурсу, в то время как начало одного не предшествует началу другой.
(3) Недетерменизм. Централизованная программа может описывать вычисления, поскольку они разворачиваются из некоторого ввода недвусмысленно; имея данную программу и ввод, только одиночное вычисление возможно. Напротив, выполнение распределенной системы обычно не -детерминировано, из-за возможных различий в быстродействии выполнения компонентов системы.
Рассмотрим ситуацию, где процесс сервера может получать запросы из неизвестного числа процессов пользователя. Сервер не может приостановить обработку запросов, пока все запросы не были получены, потому что не известно, сколько сообщений прибудет. Следовательно, каждый запрос должен быть обработан немедленно, и порядок обработки - порядок, в который запросы прибывают. Порядок, в котором клиентура посылает их запросы, может быть известен, но поскольку задержки передачи не известны, запросы могут прибывать в различном порядке.
Комбинация недостатка знания относительно глобального состояния, недостаток глобального кадра времени, и недетерменизм делает проект распределенных алгоритмов запутанным ремеслом, потому что три аспекта вмешиваются несколькими способами. Понятия времени и состояния очень связаны; в централизованных системах понятие времени может быть определено, рассматривая последовательность состояний, принятых системой в течение выполнения. Даже при том, что в распределенной системе глобальное состояние может быть определено, и выполнение может рассматриваться как последовательность глобальных состояний (Определение 2.2), это представление имеет ограниченное использование, так как выполнение может также быть описано другими последовательностями глобальных состояний (Теорема 2.21). Те альтернативные последовательности обычно состоят из различных глобальных состояний; это придает утверждению "система, принимала это или то состояние в течение выполнения " очень сомнительное значение. Недостаток знания относительно глобального состояния мог бы компенсироваться, если было возможно предсказать это глобальное состояние из алгоритма, который выполняется. К сожалению, это не возможно из-за свойственного недетерменизма в выполнении распределенных систем.