Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 12

Поэтому нельзя управлять вычислением, основываясь на информации о глобальном состоянии системы. Конечно,узел может получить информацию о состоянии других узлов и принять решение,учитывая эту информацию. Но, в отличие от централизованных систем, за время,1.3. Распределенные алгоритмы41прошедшее между моментом отправления этой информации и моментом принятиярешения, состояние других узлов может измениться, и это обстоятельство делаетустаревшую информацию неактуальной.Узлы системы не способны оценить состояние коммуникационной подсистемы (в частности, они не могут знать о том, какие сообщения пребывают на этапепересылки в тот или иной момент времени), поскольку содержимое каналов связи не поддается прямому наблюдению со стороны узлов.

Эти сведения можнополучить косвенным образом, проведя дедуктивный анализ информации о техсообщениях, которые были отправлены и получены всеми узлами системы.2. Отсутствие глобальной шкалы времени. Все события, которые возникают при выполнении централизованного алгоритма, можно вполне упорядочитьестественным образом в зависимости от времени их осуществления; для каждойпары событий одно из них происходит ранее или позднее другого. Подобное отношение предшествования по времени, введенное на множестве событий, которыевозникают при выполнении распределенного алгоритма, не является тотальным:для некоторых пар событий есть основания считать, что одно из них происходитранее или позднее другого, но есть и такие пары событий, ни одно из которыхнельзя счесть произошедшим ранее или позднее другого [124] .В централизованной системе очень просто добиться взаимно исключенногодоступа к ресурсу: если процесс p обращается к ресурсу позже процесса q, тои доступ к ресурсу будет предоставлен процессу p только после того, как процесс q освободит этот ресурс.

И в самом деле, все события, о которых идет речь(начало и окончание доступа к ресурсу процессами p и q), вполне упорядоченыотношением предшествования по времени. В распределенных системах такогоможет не быть, и этой стратегии уже недостаточно. Процессы p и q могут обратиться к ресурсу, но ни для одного из этих процессов начало его обращенияк ресурсу не предшествует по времени началу обращения другого.3. Недетерминизм.

Для заданных входных данных централизованная программа строит одно-единственное вычисление, оно разворачивается совершеннооднозначно и недвусмысленно. А вот выполнение распределенной системы, напротив, обычно бывает недетерминированным, ввиду того что быстродействиеразличных компонентов системы оказывается разным.Рассмотрим ситуацию, когда процесс-сервер ожидает поступления заранеенеизвестного числа запросов от клиентских процессов. Сервер не может отложить обработку запросов, пока они все не будут ему доставлены, поскольку он незнает, как много сообщений ему поступит. Значит, каждый запрос должен бытьобработан немедленно, и обрабатываться запросы должны в порядке их поступления.

Даже если известен порядок отправления этих запросов клиентами, задержки, возникающие при их передаче, никогда точно не известны, и поэтомузапросы могут поступать совсем в другом порядке.Все это вместе взятое — отсутствие сведений о глобальном состоянии, отсутствие глобальной шкалы времени и недетерминизм — приводит к тому, что задачапроектирования распределенных алгоритмов становится весьма замысловатой,из-за того что эти три особенности могут встречаться в самых разнообразныхсочетаниях.42Гл.

1. Введение: распределенные системыПонятия времени и состояния очень тесно связаны друг с другом: в централизованных системах понятие времени вводится на основе последовательности состояний, которые достигаются по ходу выполнения программы. И хотядля распределенных систем можно определить понятие глобального состояния ивыполнение программы можно мыслить как последовательность глобальных состояний (см.

определение 2.2), подобная точка зрения представляется довольноограниченной, поскольку то же самое выполнение может быть образовано другойпоследовательностью глобальных состояний (теорема 2.21). Такие альтернативные последовательности обычно состоят из разных глобальных состояний, и поэтому нет особого смысла говорить о том, что то или иное состояние достигаетсяпо ходу выполнения распределенной программы.Отсутствие сведений о глобальном состоянии можно было бы возместить возможностью предвидеть достижимость этого состояния по ходу выполнения исходя из устройства алгоритма.

К сожалению, и этого нельзя сделать из-за недетерминизма, неизбежно возникающего при выполнении распределенных систем.1.3.2. Пример связи с передачей одного сообщенияМы проиллюстрируем те затруднения, которые обусловлены отсутствием сведений о глобальном состоянии и отсутствием глобальной шкалы времени, на примере одной задачи надежного обмена информацией по ненадежному каналу связи, которая обсуждается в работе Бельснеса [26] .

Рассмотрим два процесса aи b, связанных друг с другом в какой-либо сети, которая позволяет передаватьданные от одного процесса к другому. Сообщение может быть доставлено скольугодно поздно после своего отправления, а может и вообще потеряться в сети.Надежность коммуникации можно повысить, если воспользоваться процедурамиуправления сетью (NCPs 17) ), при помощи которых процессы a и b получают доступ к сети.

Процесс a начинает устанавливать соединение, передав одну единицуинформации m процедуре A. Взаимодействие между процедурами управления сетью (через сеть передачи данных DN 18) ) должно быть организовано так, чтобыинформация m была доставлена процессу b (при посредничестве NCP B), и после этого процесс должен быть оповещен об этой доставке (при посредничествеNCP A). Структура коммуникаций изображена на рис.

1.5.Даже в том случае, когда процесс a должен передать процессу b тодько однуединицу информации, ненадежность сети вынуждает NCP A и NCP B вступитьв диалог, который сопровождается обменом целым рядом сообщений. Эти процедуры сохраняют информацию о том, в каком состоянии находится этот диалог, новвиду того что число партнеров, с которыми каждый процесс вступает в диалог,может быть очень велико, после завершения обмена сообщениями вся информация о состоянии диалога стирается. Инициализация информации о состояниидиалога называется открытием диалога, а сброс информации о его состоянииназывается закрытием диалога. Нужно иметь в виду, что после закрытия диа17) Network18) DataControl Procedures.

— Прим. перев.Network. — Прим. перев.1.3. Распределенные алгоритмыПроцесс aНачать?Процесс b6ПодтвердитьNCP A436ДоставитьNCP B66?Сеть передачи данных (DN)?Рис. 1.5. Упрощенная архитектура сетилога NCP перейдет как раз в то состояние, в котором эта процедура пребывалаперед открытием этого диалога; это состояние мы будем называть закрытымсостоянием.Говорят, что блок информации m был потерян, если процесс a был оповещено приеме этого блока процессом b, но сам блок при этом так и не был никогдадоставлена процессу b. Говорят, что блок информации m был дублирован, еслион была доставлен дважды. Надежное средство связи должно предотвращатькак потери, так и дублирования. Предполагается также, что процедуры управления сетью могут выходить из строя (ломаться) и после каждой поломки ониперезапускаются из закрытого состояния (при этом вся информация о текущемоткрытом диалоге будет потеряна).Надежная связь невозможна.

Прежде всего убедимся в том, что независимо от того, насколько изощренно устроены процедуры управления сетью, абсолютно надежную связь обеспечить невозможно. К этому выводу можно прийтинезависимо от устройства сети передачи данных и процедур управления этой сетью, основываясь лишь на предположении о том, что NCP может утрачиватьинформацию о ведущемся диалоге.Чтобы убедиться в этом, предположим, что, после того как процесс a инициировал соединение, процедуры A и B вступают в диалог, в ходе которого NCP Bдолжна доставить информацию m процессу b после получения сообщения M отNCP A. Рассмотрим случай, когда NCP B выходит из строя и перезапускаетсяв закрытом состоянии, после того как NCP A уже отправила сообщение M.

В этойситуации ни NCP A, ни NCP B не могут сказать, была ли информация m ужедоставлена в тот момент, когда NCP B вышла из строя. Процедура A не можетэтого сделать, потому что она не может судить о том, какие события произошлив NCP B (из-за отсутствия сведений о глобальном состоянии), а процедура Bне может этого сделать, потому что она вышла из строя и была перезапущенав закрытом состоянии. Ошибка может возникнуть независимо от того, как процедуры управления сетью продолжат свой диалог. Если NCP A вновь отправитсообщение NCP B и NCP B доставит это сообщение, то произойдет дублирование информации. А если подтверждение a будет отправлено, тогда как доставкаинформации m не состоялась, то случится потеря информации.44Гл.