Реферат: Распределенные алгоритмы
Утверждение 7.8 Если круг i начинается с k (k>1) активными процессами, и все процессы имеют различные ci, то в круге остаются не меньше 1 и не больше k/2 процессов. В конце круга снова все текущие идентификаторы активных процессов различны и включают наименьший идентификатор.
Доказательство. Путем обмена сообщениями <one,q>, которые пропускаются пассивными процессами, каждый активный процесс получает текущий идентификатор своего активного соседа против часовой стрелки, который всегда отличается от его собственного идентификатора. Далее, каждый активный процесс продолжает обход круга, передавая сообщения <two,q>, благодаря которым каждый активный процесс получает текущий идентификатор своего второго активного соседа против часовой стрелки. Теперь все активные процессы имеют различные значения acn, откуда следует, что в конце круга все оставшиеся в круге идентификаторы различны. По крайней мере, остается идентификатор, который был наименьшим в начале круга, т.е. остается хотя бы один процесс. Идентификатор рядом с локальным минимумом не является локальным минимумом, откуда следует, что количество оставшихся в круге не превышает k/2.
Из Утверждения 7.8 следует, что существует круг с номером £ ëlogNû+1, который начинается ровно с одним активным идентификатором, а именно, с наименьшим среди идентификаторов инициаторов.
Утверждение 7.9 Если круг начинается ровно с одним активным процессом p с текущим идентификатором cip, то алгоритм завершается после этого круга с winq = cip для всех q.
Доказательство. Сообщение <one,cip> пропускается всеми процессами и, в конце концов, его получает p. Процесс p обнаруживает, что acnp = cip и посылает по кольцу сообщение <smal,acnp>, вследствие чего все процессы выходят из основного цикла с winp = acnp.
Алгоритм завершается в каждом процессе и все процессы согласовывают идентификатор лидера (в переменной winp); этот процесс находится в состоянии лидер, а остальные - в состоянии проигравший.
Всего происходит не более ëlogNû+1 обходов круга, в каждом из которых передается ровно 2N сообщений, что доказывает, что сложность сообщений ограничена 2N logN + O(N). Теорема 7.7 доказана.
Dolev и др. удалось улучшить свой алгоритм до 1.5N logN, после чего Petersen получил алгоритм, использующий только 1.44N logN сообщений. Этот алгоритм снова был улучшен Dolev и др. до 1.356N logN. Верхняя граница в 1.356N logN считалась наилучшей для выбора на кольцах более 10 лет, но была улучшена до 1.271N logN Higham и Przytycka [HP93].
В этом подразделе будет доказана нижняя граница сложности выбора на однонаправленных кольцах. Т.к. выбор можно провести за одно выполнение децентрализованного волнового алгоритма, нижняя граница сложности децентрализованных волновых алгоритмов для колец будет получена как заключение.
Результат получен Pachl, Korach и Rotem [PKR84] при следующих предположениях.
(1) Граница доказывается для алгоритмов, вычисляющих наименьший идентификатор. Если существует лидер, наименьший идентификатор может быть вычислен с помощью N сообщений, а если наименьший идентификатор известен хотя бы одному процессу, процесс с этим идентификатором может быть выбран опять же за N сообщений. Следовательно, сложность задач выбора и вычисления наименьшего идентификатора различаются не более чем на N сообщений.
(2) Кольцо является однонаправленным.
(3) Процессам не известен размер кольца.
(4) Предполагается, что каналы FIFO. Это предположение не ослабляет результат, потому что сложность не-FIFO алгоритмов не лучше сложности FIFO алгоритмов.
(5) Предполагается, что все процессы являются инициаторами. Это предположение не ослабляет результат, потому что оно описывает ситуацию, возможную для каждого децентрализованного алгоритма.
(6) Предполагается, что алгоритмы управляются сообщениями; т.е. после отправления сообщений при инициализации алгоритма, процесс посылает сообщения в дальнейшем только после получения очередного сообщения. Т.к. рассматриваются асинхронные системы, общие алгоритмы не достигают лучшей сложности, чем алгоритмы, управляемые сообщениями. Действительно, если A - асинхронный алгоритм, то управляемый сообщениями алгоритм B может быть построен следующим образом. После инициализации и после получения любого сообщения B посылает максимальное количество сообщений, которое можно послать в A, не получая при этом сообщений, и только затем получает следующее сообщение. Алгоритм B не только управляется сообщениями, но кроме того, каждое вычисление B является возможным вычислением A (возможно, при довольно пессимистическом распределении задержек передачи сообщений).
Три последних предположения устраняют недетерминизм системы. При этих предположениях каждое вычисление, начинающееся с данной начальной конфигурации, содержит одно и то же множество событий.
В этом разделе через s = (s1, ..., sN), t и т.п. обозначаются последовательности различных идентификаторов процессов. Множество всех таких последовательностей обозначено через D, т.е. D = {(s1, ..., sk): si Î P и i ¹ j Þ si ¹ sj}. Длина последовательности s обозначается через len(s), а конкатенация последовательностей s и t обозначается st. Циклическим сдвигом s называется последовательность s¢s¢¢, где s = s¢¢s¢ ; она имеет вид si, ..., sN, s1, ..., si-1. Через CS(s) (cyclic shift - циклический сдвиг) обозначено множество циклических сдвигов s, и естественно |CS(s)| = len(s).
Говорят, что кольцо помечено последовательностью (s1, ..., sN), если идентификаторы процессов с s1 по sN расположены на кольце (размера N) в таком порядке. Кольцо, помеченное s также называют s-кольцом. Если t - циклический сдвиг s, то t-кольцо совпадает с s-кольцом.
С каждым сообщением, посылаемым в алгоритме, свяжем последовательность идентификаторов процессов, называемую следом (trace) сообщения. Если сообщение m было послано процессом p до того, как p получил какое-либо сообщение, след m равен (p). Если m было послано процессом p после того, как он получил сообщение со следом s = (s1, ..., sk), тогда след m равен (s1, ..., sk, p). Сообщение со следом s называется s-сообщением. Нижняя граница будет выведена из свойств множества всех следов сообщений, которые могут быть посланы алгоритмом.
Пусть E - подмножество D. Множество E полно (exhaustive), если
(1) E префиксно замкнуто, т.е. tu Î E Þ t Î E ; и
(2) E циклически покрывает D, т.е. " s Î D: CS(s) Ç E ¹ Æ.
Далее будет показано, что множество всех следов алгоритма полно. Для того, чтобы вывести из этого факта нижнюю границу сложности алгоритма, определены две меры множества E. Последовательность t является последовательной цепочкой идентификаторов в s-кольце, если t - префикс какого-либо r Î CS(s). Обозначим через M(s,E) количество последовательностей в E, которые удовлетворяют этому условию в s-кольце, а через Mk(s,E) - количество таких цепочек длины k;
M(s,E) = |{ t Î E : t - префикс некоторого r Î CS(s) }| и
Mk(s,E) = |{ t Î E : t - префикс некоторого r Î CS(s) и len(t) = k}|.
В дальнейшем, допустим, что A - алгоритм, который вычисляет наименьший идентификатор, а EA - множество последовательностей s таких, что s-сообщение посылается, когда алгоритм A выполняется на s-кольце.
Лемма 7.10 Если последовательности t и u содержат подстроку s и s-сообщение посылается, когда алгоритм A выполняется на t-кольце, то s-сообщение также посылается, когда A выполняется на u-кольце.
Доказательство. Посылка процессом sk s-сообщения, где s = (s1, ..., sk), каузально зависит только от процессов с s1 по sk. Их начальное состояние в u-кольце совпадает с состоянием в t-кольце (напоминаем, что размер кольца неизвестен), и следовательно совокупность событий, предшествующих посылке сообщения, также выполнима и в u-кольце.
Лемма 7.11 EA - полное множество.
Доказательство. Чтобы показать, что EA циклически замкнуто, заметим, что если A посылает s-сообщение при выполнении на s-кольце, тогда для любого префикса t последовательности s A сначала посылает t-сообщение на s-кольце. По Лемме 7.10 A посылает t-сообщение на t-кольце, следовательно t Î EA.
Чтобы показать, что EA циклически покрывает D, рассмотрим вычисление A на s-кольце. Хотя бы один процесс выбирает наименьший идентификатор, откуда следует (аналогично доказательству Теоремы 6.11), что этот процесс получил сообщение со следом длины len(s). Этот след является циклическим сдвигом s и принадлежит E.
Лемма 7.12 В вычислении на s-кольце алгоритм A посылает не менее M(s,EA) сообщений.
Доказательство. Пусть t Î EA - префикс циклического сдвига r последовательности s. Из определения EA, A посылает t-сообщение в вычислении на t-кольце, а следовательно также и на r-кольце, которое совпадает с s-кольцом. Отсюда, для каждого t из {t Î E: t - префикс некоторого r Î CS(s)} в вычислении на s-кольце посылается хотя бы одно t-сообщение, что доказывает, что количество сообщений в таком вычислении составляет не менее M(s,E).
Страницы: 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, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
