Чтобы показать, что W(N) - нижняя граница временной сложности, построим на клике из N процессов вычисление, которое затрачивает время N. Зафиксируем в клике остовное дерево глубины N-1 (на самом деле, линейную цепочку вершин). Предположим, что все сообщения <tok>, посланные вниз по ребрам дерева, будут получены спустя 1/N единиц времени после их отправления, а сообщения <tok> через листовые ребра будут получены спустя одну единицу времени. Эти задержки допустимы, согласно предположению T2, и в этом вычислении дерево полностью формируется в течение одной единицы времени, но имеет глубину N-1. Допустим теперь, что все сообщения, посылаемые вверх по ребрам дерева также испытывают задержку в одну единицу времени; в этом случае решение принимается ровно через N единиц времени с начала вычисления.

Можно спорить о том, какое из двух определений предпочтительнее при обсуждении сложности распределенного алгоритма. Недостаток единичной сложности в том, что некоторые вычисления не учитываются, хотя они и допускаются алгоритмом. Среди игнорируемых вычислений могут быть такие, которые потребляют очень много времени. Предположения в Определении 6.31 не исключают ни одного вычисления; определение только устанавливает меру времени для каждого вычисления. Недостаток временной сложности в том, что результат определен вычислениями (как в доказательстве Теоремы 6.38), что хотя и возможно, но считается крайне маловероятным. Действительно, в этом вычислении одно сообщение «обгоняется» цепочкой из N-1 последовательно передаваемого сообщения.

В качестве компромисса между двумя определениями можно рассмотреть a-временную сложность, которая определяется согласно предположению, что задержка каждого сообщения - величина между a и 1 (a - константа £1). К сожалению, этот компромисс обладает недостатками обоих определений. Читатель может попытаться показать, что a-временная сложность эхо-алгоритма равна O(min(N,D/a)).

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

Определение, основанное на цепочках сообщений. Затраты времени на распределенное вычисление могут быть определены с использованием структурных свойств вычисления, а не идеализированных временных предположений. Пусть C - вычисление.

Определение 6.39  Цепочка сообщений в C - это последовательность сообщений m1, m2, ..., mk такая, что для любого i  (0 £ i £ k) получение mi каузально предшествует отправлению mi+1.

Цепочечная сложность распределенного алгоритма (chain-time complexity) - это длина самой длинной цепочки сообщений во всех вычислениях алгоритма.

Это определение, как и Определение 6.31, рассматривает всевозможные выполнения алгоритма для определения его временной сложности, но определяет другую меру сложности для вычислений. Рассмотрим ситуацию (происходящую в вычислении, определенном в доказательстве теоремы 6.38), когда одно сообщение «обгоняется» цепочкой из k сообщений. Временная сложность этого (под)вычисления равна 1, в то время, как цепочечная сложность того же самого (под)вычисления равна k. В системах, где гарантируется существование верхней границы задержек сообщений (как предполагается в определении временной сложности), временная сложность является правильным выбором. В системах, где большинство сообщений доставляется со «средней» задержкой, но небольшая часть сообщений может испытывать гораздо большую задержку, лучше выбрать цепочечную сложность.

Упражнения к  Главе 6

Раздел 6.1

Упражнение 6.1  Приведите пример PIF-алгоритма для систем с синхронной передачей сообщений, который не позволяет вычислять функцию инфимума (см. Теоремы 6.7 и 6.12). Пример может подходить только для конкретной топологии.

Упражнение 6.2  В частичном порядке (X, £) элемент b называется дном, если для всех c Î X, b £ c.

В доказательстве Теоремы 6.11 используется то, что частичный порядок (X,£) не содержит дна. Где именно?

Можете ли вы привести алгоритм, который вычисляет функцию инфимума в частичном порядке с дном и не является волновым алгоритмом?

Упражнение 6.3  Приведите два частичных порядка на натуральных числах, для которых функция инфимума является (1) наибольшим общим делителем, и (2) наименьшим общим кратным (the least common ancestor).

Приведите частичные порядки на наборах подмножеств области U, для которых функция инфимума является (1) пересечением множеств, и (2) объединением множеств.

Упражнение 6.4  Докажите теорему об инфимуме (Теорему 6.13).

Раздел 6.2

Упражнение 6.5  Покажите, что в каждом вычислении древовидного алгоритма (Алгоритм 6.3) решение принимают ровно два процесса.

Упражнение 6.6  Используя эхо-алгоритм (Алгоритм 6.5), составьте алгоритм, который вычисляет префиксную схему маркировки (см. Подраздел 4.4.3) для произвольной сети с использованием 2|E| сообщений и O(N) единиц времени.

Можете ли вы привести алгоритм, вычисляющий схему маркировки за время O(D) ? (D - диаметр сети.)   

Упражнение 6.7  Покажите, что соотношение в Лемме 6.19 выполняется, если сообщение потерялось в канале pq, но не выполняется, если сообщения могут дублироваться. Какой шаг доказательства не действует, если сообщения могут дублироваться?

Упражнение 6.8  Примените построение в Теореме 6.12 к фазовому алгоритму так, чтобы получить алгоритм, вычисляющий максимум по целочисленным входам всех процессов.

Каковы сложность сообщений, временная и битовая сложность вашего алгоритма?

Упражнение 6.9  Предположим, вы хотите использовать волновой алгоритм в сети, где может произойти дублирование сообщений.

(1) Какие изменения должны быть сделаны в эхо-алгоритме?

(2)  Какие изменения должны быть сделаны в алгоритме Финна?

Раздел 6.3

Упражнение 6.10  Полный двудольный граф - это граф G = (V,E), где V = V1 È V2  при V1 Ç V2 = Æ  и  E = V1 ´ V2.

Приведите алгоритм 2x-обхода для полных двудольных сетей.

Упражнение 6.11  Докажите или опровергните: Обход гиперкуба без чувства направления требует Q(N logN) сообщений.

Раздел 6.4

Упражнение 6.12  Приведите пример вычисления алгоритма Тарри, в котором в результате получается не DFS-дерево.

Упражнение 6.13  Составьте алгоритм, который вычисляет интервальные схемы маркировки поиска в глубину (см. Подраздел 4.4.2) для произвольных связных сетей.

Может ли это быть сделано за O(N) единиц времени? Может ли это быть сделано с использованием O(N) сообщений?

Упражнение 6.14  Предположим, что алгоритм поиска в глубину со знанием соседей используется в системе, где каждый процесс знает не только идентификаторы своих соседей, но и множество идентификаторов всех процессов (P). Покажите, что в этом случае достаточно сообщений, состоящих из N бит.  

Раздел 6.5

Упражнение 6.15  Адаптируйте эхо-алгоритм (Алгоритм 6.5) для вычисления суммы по входам всех процессов.

Упражнение 6.16  Предположим, что процессы в сетях, изображенных на Рис.6.21, имеют уникальные идентификаторы, и каждый процесс имеет целочисленный вход. Смоделируйте на обеих сетях вычисление фазового алгоритма, вычисляя множество S = {(p, jp): p Î P} и сумму по входам.  

Упражнение 6.17  Какова цепочечная сложность фазового алгоритма для клик (Алгоритм 6.8) ?

7  Алгоритмы выбора

В этой главе будут обсуждаться проблемы выбора, также называемого нахождением лидера. Задача выбора впервые была изложена ЛеЛанном [LeLann; LeL77], который предложил и первое решение; см. Подраздел 7.2.1. Задача начинается в конфигурации, где все процессы находятся в одинаковом состоянии, и приходит в конфигурацию, где ровно один процесс находится в состоянии лидера (leader), а все остальные - в состоянии проигравших (lost).

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

Существует большое количество результатов о задаче выбора (как алгоритмы, так и более общие теоремы). Результаты для включения в эту главу выбирались по следующим критериям.

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90