Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 67
Текст из файла (страница 67)
Туры не синхронизированы глобально; возможна ситуация, при которой один из процессов опережаетна несколько туров другой процесс, расположенный в иной части кольца. Ноколь скоро каждый процесс отправляет и получает в каждом туре ровно два сообщения и в каналах поддерживается очередность посланий, получатель всякогосообщения будет участвовать в том же туре, в котором находился его отправитель. В первом туре все инициаторы активны и каждый активный процессхранит индивидуальный «текущий отличительный признак».Утверждение 7.8.
Если в начале i-го тура имеется k > 1 активных процессов и все «текущие отличительные признаки» ci, хранимые этими процессами, попарно различны, то в следующий тур перейдет не менее одного и не более k/2 процессов. По окончании i-го тура текущие отличительные признаки активных процессов будут вновь попарно различны, и срединих будет находиться самый младший признак.Д о к а з а т е л ь с т в о. После обмена сообщениями вида hone, qi, которыеретранслируются пассивными процессами, каждый активный процесс получиттекущий отличительный признак своего ближайшего активного соседа, расположенного против хода часовой стрелки, и этот признак будет во всяком случаене совпадать с его собственным отличительным признаком.
Следовательно, каждый активный процесс продолжит этот тур, и произойдет обмен сообщениямивида htwo, qi, благодаря чему каждый активный процесс получит также текущийотличительный признак второго по близости активного соседа, расположенного против хода часовой стрелки. Все активные процессы теперь хранят разныезначения acn, а это означает, что процессы, выдержавшие этот тур, будут в конце его хранить разные отличительные признаки. Этот тур выдержит по крайнеймере тот отличительный признак, который был наименьшим в начале тура, и,значит, хотя бы один процесс перейдет в следующий тур.
А поскольку отличительный признак, который расположен вслед за локальным минимумом, не будетлокальным минимумом, число процессов, перешедших в следующий тур, не будетпревосходить k/2.Из утверждения 7.8 следует, что наступит и такой тур (его номер не будетпревосходить величины blog Nc + 1), в начале которого будет ровно один активный участник, а именно самый младший среди отличительных признаков всехинициаторов.7.2.
Кольцевые сети253Утверждение 7.9. Если в начале тура есть только один активный процесс p с текущим отличительным признаком cip , то по окончании этоготура алгоритм завершит свою работу, и при этом для каждого процессаq будет выполнено равенство winq = cip .Д о к а з а т е л ь с т в о. Сообщение hone, cip i, отправленное процессом p,будет ретранслировано всеми процессами и в конце концов будет получено самимпроцессом p. Процесс p убедится в том, что выполняется равенство acn p = cip ,и отправит сообщение hsmall, acnp i по кольцу, вынудив тем самым каждый процесс q выйти из основного цикла, присвоив при этом переменной win q значениеacnp .Рассматриваемый нами алгоритм завершает свое выполнение в каждом изпроцессов, и при этом все процессы будут согласованно оповещены об отличительном признаке лидера (этот признак является значением переменной win q).Процесс с указанным признаком будет пребывать в состоянии leader, а всеостальные процессы — в состоянии lost.Потребуется самое большее blog Nc + 1 туров, в каждом из которых происходит обмен ровно 2N сообщениями; это и служит обоснованием оценки сложности2N log N + O(N) по числу обменов сообщениями.
Доказательство теоремы 7.7 завершено.Долеву, Клейву и Роде удалось улучшить их алгоритм так, что верхняя оценкасложности была уменьшена до 1.5N log N, после чего Петерсон сумел построитьалгоритм, в котором используется всего лишь 1.44N log N обменов сообщениями.Но и эта оценка была впоследствии уменьшена Долевым, Клейвом и Роде до1.356N log N. В течение 10 лет верхняя оценка 1.356N log N для задачи о выборахна кольцах оставалась самой точной, но и она была уменьшена до 1.271N log NХайемом и Пржитикой в работе [104] .7.2.3. Результат о нижних оценкахВ этом параграфе дается обоснование нижней оценке сложности задачи о выборах на однонаправленных кольцах.
Так как выборы можно провести по ходу одного-единственного выполнения децентрализованного волнового алгоритма,в качестве следствия будет получена и нижняя оценка сложности децентрализованных волновых алгоритмов на кольцах.Этот результат был получен Пачлом, Корачем и Ротемом в работе [156]в рамках следующих допущений.1. Оценка установлена для алгоритмов, вычисляющих самый младший отличительный признак. Если лидер известен, то самый младший отличительныйпризнак можно вычислить с использованием N обменов сообщениями, а еслисамый младший отличительный признак известен хотя бы одному процессу, топроцесс с этим признаком может быть избран лидером также с использованиемN обменов сообщениями.
Следовательно, сложность задачи о выборах и сложность задачи вычисления самого младшего отличительного признака отстоят другот друга самое большее на N обменов сообщениями.254Гл. 7. Алгоритмы избрания лидера2. Рассматриваемое кольцо однонаправленное.3. Процессы не осведомлены о размерах кольца.4. Предполагается, что в каналах поддерживается очередность сообщений.Это допущение не ослабляет результат, поскольку сложность алгоритмов безсоблюдения очередности сообщений не может быть лучше, чем сложность алгоритмов, требующих поддержания очередности сообщений.5. Предполагается, что все процессы являются инициаторами.
Это допущение не ослабляет результат, потому что оно описывает ситуацию, свойственнуюлюбому децентрализованному алгоритму.6. Предполагается, что алгоритмы приводятся в действие сообщениями; этоозначает, что после того, как на этапе инициализации алгоритма были отправлены некоторые сообщения, всякий процесс отправляет последующие сообщениятолько после получения какого-нибудь сообщения.
Если речь идет об асинхронных системах, то алгоритмы общего вида не дают выигрыша по сложности посравнению с алгоритмами, приводимыми в действие сообщениями. И в самомделе, для всякого асинхронного алгоритма A можно построить следующий алгоритм B, который приводится в действие сообщениями. После инициализациии получения какого-нибудь сообщения алгоритм B отправляет максимальную последовательность сообщений, которые разрешается отправить алгоритму A, непроводя приема сообщений, и лишь затем получает очередное сообщение.
Алгоритм B приводится в действие сообщениями, и, более того, каждое вычислениеалгоритма B является одним из возможных вычислений алгоритма A (хотя, возможно, распределение задержек передач сообщений будет далеко не лучшим).Последние три допущения избавляют систему от недетерминированности. В рамках этих допущений каждое вычисление, начинающееся с заданной конфигурации, содержит одно и то же множество событий.В этом параграфе записи s = (s1 , . . . , sN), t, и т. п. будут использоваться дляобозначения наборов попарно различных отличительных признаков.
Множествовсех таких наборов обозначим D, т. е.D = { (s1 , . . . , sk) : si ∈ P и i 6= j =⇒ si 6= sj }.Длину набора s обозначим len(s), а конкатенацию наборов s и t обозначим st.Циклическим сдвигом набора s назовем такой набор s0 s00 , что s = s00 s0 ; ясно,что этот набор имеет вид si , . . . , sN , s1 , .
. . , si−1 . Запись CS(s) будет обозначатьмножество циклических сдвигов набора s. Нетрудно видеть, что размер множества CS(s) равен длине набора s.Будем говорить, что кольцо помечено набором (s 1 , . . . , sN), если именно в таком порядке в кольце размера N расположены отличительные признаки процессов, начиная с s1 и оканчивая sN . Кольцо, помеченное набором s, будем такженазывать s-кольцом. Если t является циклическим сдвигом набора s, то t-кольцо,естественно, будет тем же самым кольцом, что и s-кольцо.С каждым сообщением, которое отправляется по ходу работы алгоритма, мыассоциируем набор отличительных признаков процессов, который будем называтьтрассой данного сообщения. Если сообщение m было отправлено процессом p,до того как p получил некоторое сообщение, то трассой сообщения m служит7.2. Кольцевые сети255набор (p). Если сообщение m было отправлено процессом p, после того как онполучил некоторое сообщение, трассой которого служит набор s = (s 1 , .
. . , sk),то трасса сообщения m задается набором (s1 , . . . , sk , p). Сообщение с трассой sбудет называться s-сообщением. Нижняя оценка будет получена на основе анализа свойств множества трасс всех сообщений, которые могут быть отправленыпо ходу работы алгоритма.Рассмотрим подмножество E множества D. Множество E назовем исчерпывающим, если выполнены следующие условия:1) E префиксно замкнуто, т. е. tu ∈ E =⇒ t ∈ E;2) E является циклическим покрытием множества D, т. е. ∀s ∈ D: CS(s) ∩ E 6=6 ∅.=Как будет показано далее, множество всех трасс любого алгоритма 1) является исчерпывающим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
