Упражнение 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.10 Полный двудольный граф - это граф G = (V,E), где V = V1 È V2при V1 Ç V2 = Æ и E = V1 ´ V2.
Приведите алгоритм 2x-обхода для полных двудольных сетей.
Упражнение 6.11 Докажите или опровергните: Обход гиперкуба без чувства направления требует Q(N logN) сообщений.
Упражнение 6.12 Приведите пример вычисления алгоритма Тарри, в котором в результате получается не DFS-дерево.
Упражнение 6.13 Составьте алгоритм, который вычисляет интервальные схемы маркировки поиска в глубину (см. Подраздел 4.4.2) для произвольных связных сетей.
Может ли это быть сделано за O(N) единиц времени? Может ли это быть сделано с использованием O(N) сообщений?
Упражнение 6.14 Предположим, что алгоритм поиска в глубину со знанием соседей используется в системе, где каждый процесс знает не только идентификаторы своих соседей, но и множество идентификаторов всех процессов (P). Покажите, что в этом случае достаточно сообщений, состоящих из N бит.
Упражнение 6.15 Адаптируйте эхо-алгоритм (Алгоритм 6.5) для вычисления суммы по входам всех процессов.
Упражнение 6.16 Предположим, что процессы в сетях, изображенных на Рис.6.21, имеют уникальные идентификаторы, и каждый процесс имеет целочисленный вход. Смоделируйте на обеих сетях вычисление фазового алгоритма, вычисляя множество S = {(p, jp): p Î P} и сумму по входам.
Упражнение 6.17 Какова цепочечная сложность фазового алгоритма для клик (Алгоритм 6.8) ?
В этой главе будут обсуждаться проблемы выбора, также называемого нахождением лидера. Задача выбора впервые была изложена ЛеЛанном [LeLann; LeL77], который предложил и первое решение; см. Подраздел 7.2.1. Задача начинается в конфигурации, где все процессы находятся в одинаковом состоянии, и приходит в конфигурацию, где ровно один процесс находится в состоянии лидера (leader), а все остальные - в состоянии проигравших (lost).
Выбор среди процессов нужно проводить, если должен быть выполнен централизованный алгоритм и не существует заранее известного кандидата на роль инициатора алгоритма. Например, в случае процедуры инициализации системы, которая должна быть выполнена в начале или после сбоя системы. Т.к. множество активных процессов может быть неизвестно заранее, невозможно назначить один процесс раз и навсегда на роль лидера.
Существует большое количество результатов о задаче выбора (как алгоритмы, так и более общие теоремы). Результаты для включения в эту главу выбирались по следующим критериям.
(1) Синхронные системы, анонимные процессы, и отказоустойчивые алгоритмы обсуждаются в других главах. В этой главе всегда предполагается, что процессы и каналы надежны, система полностью асинхронна, и процессы различаются уникальными идентификаторами.
(2) Мы сосредоточим внимание на результатах, касающихся сложности сообщений. Алгоритмы с улучшенной временной сложностью или результаты, предполагающие компромисс между временной сложностью и сложностью сообщений, не обсуждаются.
(3) Мы будем уделять внимание порядку величины сложности сообщений, и не будем рассматривать результаты, вносящие в сложность только постоянный множитель.
(4) Т.к. результаты Кораха и др. (Раздел 7.4) подразумевают существование O(N logN)-алгоритмов для нескольких классов сетей, алгоритм для клики с этой сложностью не будет рассматриваться отдельно.
Задача выбора требует, чтобы из конфигурации, где все процессы находятся в одинаковом состоянии, система пришла в конфигурацию, где ровно один процесс находится в особом состоянии лидер (leader), а все остальные процессы - в состоянии проигравших (lost). Процесс, находящийся в состоянии лидер в конце вычисления, называется лидером и говорят, что он выбран алгоритмом.
Определение 7.1 Алгоритм выбора - это алгоритм, удовлетворяющий следующим требованиям.
(1) Каждый процесс имеет один и тот же локальный алгоритм.
(2) Алгоритм является децентрализованным, т.е. вычисление может быть начато произвольным непустым подмножеством процессов.
(3) Алгоритм достигает заключительной конфигурации в каждом вычислении, и в каждой достижимой заключительной конфигурации существует ровно один процесс в состоянии лидера, а все остальные процессы - в состоянии проигравших.
Иногда последнее требование ослабляется и требуется только, чтобы ровно один процесс находился в состоянии лидера. В этом случае выбранный процесс знает, что он победил, но проигравшие (еще) не знают, что они проиграли. Если дан алгоритм, удовлетворяющий этим ослабленным действиям, то его можно легко расширить, добавив инициируемую лидером рассылку сообщений всем процессам, при которой все процессы информируются о результатах выбора. В некоторых алгоритмах этой главы это дополнительное оповещение опущено.
Во всех алгоритмах этой главы процесс p имеет переменную statep с возможными значениями leader (лидер) и lost (проигравший). Иногда мы будем предполагать, что statep имеет значение sleep (спящий), когда p еще не выполнил ни одного шага алгоритма, и значение cand (кандидат), если p вступил в вычисление, но еще не знает, победил он или проиграл. Некоторые алгоритмы используют дополнительные состояния, такие как active, passive и др., которые будут указаны в самом алгоритме.
7.1.1 Предположения, используемые в этой главе
Рассмотрим предположения, при которых задача выбора изучалась в этой главе.
(1) Система полностью асинхронна. Предполагается, что процессам недоступны общие часы, и что время передачи сообщения может быть произвольно долгим или коротким.
Оказывается, что предположение о синхронной передаче сообщений (т.е. когда отправление и получение сообщения считается единой передачей) незначительно влияет на результаты, полученные для задачи выбора. Читатель может сам убедиться, что алгоритмы, данные в этой главе, могут применяться в системах с синхронной передачей сообщений, и что полученные нижние границы также применимы в этом случае.
Предположение о существовании глобального времени, также как и предположение о том, что процессам доступно реальное время и что задержка сообщений ограничена, имеют важное влияние на решения задачи выбора.
(2) Каждый процесс идентифицируется уникальным именем, своим идентификатором, который известен процессу изначально. Для простоты предполагается, что идентификатор процесса p - просто p. Идентификаторы извлекаются из совершенно упорядоченного множества P, т.е. для идентификаторов определено отношение £. Количество бит, представляющих идентификатор, равно w.
Важность уникальных идентификаторов в задаче выбора состоит в том, что они могут использоваться не только для адресации сообщений, но и для нарушения симметрии между процессами. При разработке алгоритма выбора можно, например, потребовать, что процесс с наименьшим (или наоборот, с наибольшим) идентификатором должен победить. Тогда задача состоит в поиске наименьшего идентификатора с помощью децентрализованного алгоритма. В этом случае задачу выбора называют задачей поиска экстремума.
Хотя некоторые из алгоритмов, обсуждаемых в этой главе, изначально были изложены для нахождения наибольшего процесса, мы излагаем большинство алгоритмов для выбора наименьшего процесса. Во всех случаях алгоритм для выбора наибольшего процесса можно получить, изменив порядок сравнения идентификаторов.
(3) Некоторые результаты этой главы относятся к алгоритмам сравнения. Алгоритмы сравнения - это алгоритмы, которые используют сравнение как единственную операцию над идентификаторами. Как мы увидим, все алгоритмы, представленные в этой главе, являются алгоритмами сравнения. Всякий раз, когда дается оценка нижней границы, мы явно отмечаем, касается ли она алгоритмов сравнения.
Было показано (например, Бодлендером [Bodlaender, Bod91b] для случая кольцевых сетей), что в асинхронных сетях произвольные алгоритмы не достигают лучшей сложности, чем алгоритмы сравнения. Это не так в случае синхронных систем, как будет показано в Главе 11; в этих системах произвольные алгоритмы могут достигать лучшей сложности, чем алгоритмы сравнения.