Среда, которую мы описали, является достаточно абстрактной. Это общая модель для многих типов систем, производительность которых зависит от множества факторов.

Эффективность протокола должна отражать реальные затраты, которые требуются системе. То есть нам нужна абстрактная мера вычислительных и прочих затрат, которая будет иметь смысл в реальном мире.

Мы будем использовать две меры: затраты коммуникации и время, необходимое для завершения вычисления. Это позволит смотреть на систему с точки зрения самой системы (сколько трафика будет сгенерировано для решения задачи? насколько занята будет система?) и с точки зрения пользователя (сколько придется ждать окончания вычисления?).

4.1 Количество сетевой деятельности

Передача сообщения через исходящий порт (то есть исходящему соседу) это самая простая сетевая деятельность в системе. Стоит заметить, что отправка сообщения, которое не достигнет пункта назначения из-за ошибки, все еще считается сетевой деятельностью. Получается, мерой сетевой деятельности может выступать количество сообщений M, так же называемое затратой на сообщения (message cost).

Другое важное значение это нагрузка на узел L_node = M / |V|, или количество сообщений на каждый узел, и нагрузка на соединение L_link = M / |E|, или количество сообщений на каждое соединение (ребро графа).

Сообщение это набор битов; некоторые протоколы используют очень короткие сообщения (например, сигнальные биты), некоторые – очень длинные (например, графические файлы). Значит, для более точного подсчета эффективности системы нужно брать в расчет количество битов. Это значение назыавют битовой сложностью (bit complexity) протокола.

4.2 Время

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

В общей модели нет предположений касательно времени, кроме аксиомы 3.1.1: “При отсутствии повреждений и ошибок, задержки коммуникации конечны.” В целом, длина задержки непредсказуема и мы не может с точностью вычислить требуемое протоколу время.

Однако, мы можем найти значение времени, если сделаем еще несколько предположений. Время, найденное таким способом, называют идеальным или идеальной временной сложностью T. При “еденичных коммуникационных задержках” и “синхронизированных часах” любое сообщение передается и обрабатывается за один промежуток времени. В таком случае, общее время можно подсчитать зная битовую сложность.

Другой показатель времени называют казуальным, T_causal: это промежуток времени, требуемый для передачи самой длинной цепи связанных сообщений. Казуальное время очень редко используется для анализа протоколов.

Пример: вещание

Представьте себе распределенную систему, в которой одна сущность обладает информацией, неизвестной другим, и задачей является передача (вещание) этой информации всем сущностям.

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

Пусть E будет набор сущностей, а G коммуникационной топологией системы. Для упрощения, примем несколько дополнительных допущений:

1. Двусторонние соединения. (используем ненаправленный граф; см. рис. 3.2.1).
2. Полная надежность

Стоит заметить, что если граф G не соединен, то существуют узлы, до которых невозможно “достучаться”, в случае чего проблема становится нерешаемой. Поэтому, нужно принять следующее допущение:

3. Соединение (connectivity). Коммуникационная топология G является соединенной.

Из определения самой задачи вещания следует, что только один узел обладает информацией в начале, значит:

4. Уникальный инициатор

Простая стратегия, которой мы будем следовать, звучит следующим образом:

“если сущность обладает информацией, то она делится ею с соседями”

Чтобы создать набор правил, реализующий эту стратегию, необходимо определить набор статусных значений S. Из определения понятно, что нужно отличать узел-инициатор от всех остальных узлов. Поэтому, {initiator, idle} ⊆ S. Процесс может быть начат только инициатором (узлом, статус которого является “initiator”). Обозначим информацию, которую нужно передать, за I. Так выглядит набор правил B(x) (однинаков для всех сущностей):

1. initiator × ι → {send(I) to N(x)}
2. idle × Receiving(I) → {Process(I); send(I) to N(x)}
3. initiator × Receiving(I) → nil
4. idle × ι → nil

где ι означает спонтанный импульс, а nil означает бездействие. В рамках принятых допущений, каждый узел в конечном итоге получит информацию. Не смотря на это, протокол обладает существенной проблемой:

активность, сгенерированная протоколом, никогда не закончится

Представьте себе простую систему, состояющую из трех узлов, соединенных между собой (см. рис. 4.2.1). Пусть x будет инициатором, y и z будут idle, и все сообщения передаются с одинаковой скоростью; тогда y и z будут посылать сообщения друг другу до бесконечности.

Рис 4.2.1.

Для обхода этой проблемы каждая сущность должна отправлять сообщение соседям только один раз: когда она сама получает информацию. Этого можно добиться добавлением нового статуса “done”, который будет означать, что узел выполнил свою работу. Тогда S={initiator, idle, done}.

1. initiator × ι → {send(I) to N(x); become done}
2. idle × Receiving(I) → {Process(I); become done; send(I) to N(x)}
3. initiator × Receiving(I) → nil
4. idle × ι →nil
5. done × Receiving(I) → nil
6. done × ι→nil

В этом случае сетевая деятельность протокола прекращается после конечного промежутка времени, или, другими словами, за конечное время каждый узел получает статус “done”.

Имейте ввиду, что это не означает одновременность завершения всеми узлами. На самом деле, узел может завершить свою деятельность до того, как другой начал. Есть разница между локальным завершением и глобальным завершением.

Также заметьте. что в этом протоколе никто никогда не знает, случилось ли глобальное завершение.

Протокол является корректным, поэтому теперь давайте подсчитаем затраты и сложность.

Первое: подсчитаем количество переданных сообщений. Каждая сущность (хоть инициатор, хоть нет) отправляет сообщение каждому соседу. Следовательно, сумма переданных сообщений:

На самом деле мы может уменьшить затраты. В текущей версии протокола, когда idle-узел получает сообщение, он пересылает информацию всем соседям, включая того, от которого информация была получена. Естественно, это лишнее сообщение. Вторая аксиома (о локальной ориентации узлов) позволяет сущностям отличать своих соседей, то есть сущность знает, от кого из соседей поступило сообщение, и не будет посылать информацию по этому порту. Финальная версия протокола с небольшими изменениями выглядит так:

Protocol Flooding
1. initiator × ι → {send(I) to N(x); become done}
2. idle × Receiving(I) → {Process(I); become done; send(I) to N(x)-sender}
3. initiator × Receiving(I) → nil
4. idle × ι → nil
5. done × Receiving(I) → nil
6. done × ι → nil

Этот алгоритм называется Flooding (затопление), потому что система “затапливается” сообщениями в процессе. Это базовый алгоритмический инструмент для распределенных вычислений.

Теперь мы знаем, что количество сообщений меньше 2m:

M[flooding] = 2m - n + 1.

Теперь посмотрим на затраты времени. Пусть d(x,y) будет обозначать дистанцию (длину кратчайшего пути) между узлами x и y в графе G. Естественно, что сообщение, переданное инициатором, должно достичь всех узлов, включая самый отдаленный. Итак, если x это инициатор, то идеальное время будет r(x) = Max {d(x, y) : y ∈ E}; это значение также называют радиусом узла x. Другими словами, общее время зависит от топологии сети и его невозможно определить заранее. Однако, мы можем определить идеальное время в худшем из возможных случаев.

Так как любая сущность может быть инициатором, идеальное время выполнения в худшем случае будет d(G) = Max (r(x) : x ∈ E}, что является диаметром графа G. Получается, идеальное время выполнения будет как максимум диаметром G:

T[flooding] ≤ d(G).