Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 87
Текст из файла (страница 87)
Если взаимосвязьосуществляется посредством асинхронного обмена сообщениями, то эта задачане имеет детерминированного алгоритма решения; это может быть установленопутем проведения рассуждений, аналогичнымх тем, которые будут использованыпри доказательстве теоремы 9.5. Мы не хотим рассматривать решения, в которыхсимметрия разрушается за счет особенностей механизма взаимосвязи; поэтомумы ограничимся рассматрением систем, в которых взаимосвязь осуществляетсяпосредством асинхронного обмена сообщениями.То решение, которое предложила Энглуин, очень существенно зависит от топологии; оно не пригодно, например, для кольцевых сетей.
Результаты о невозможности получения некоторых решений, рассматриваемые в этой главе, будутобобщены для систем с синхронным обменом сообщениями в сетях с произвольной и кольцевой топологией.Симметрия между двумя процессами может быть разрушена детерминированно, если сообщения передаются синхронно. Отсюда следует, что не существуетдетерминированного алгоритма, способного реализовать синхронный обмен сообщениями в анонимных сетях, в которых проводится асинхронный обмен сообщениями.9.2.
Детерминированные алгоритмы332Гл. 9. Анонимные сетиВ этом параграфе представлены некоторые результаты, касающиеся детерминированных алгоритмов. Наиболее важным является следующий отрицательныйрезультат: избрать лидера детерминированно невозможно даже в том случае, когда речь идет о кольцевой сети, размер которой заранее известен. Будет такжепоказано, что вычислять функции можно при условии, что размер кольца известен, и невозможно, если размер кольца неизвестен заранее.9.2.1. Детерминированные выборы: отрицательныерезультатыВ этом параграфе будет показано, что провести детерминированные выборылидера в анонимных сетях невозможно. Доказательство проводится с использованием понятия с и м м е т р и ч е с к о й к о н ф и г у р а ц и и . Показано, что существуетвычисление, которое берет начало в симметрической конфигурации и достигаетсимметрической конфигурации через каждые N шагов. Невозможность получения детерминированного решения следует из того, что корректный алгоритм незавершает работу в симметрической конфигурации.Теорема 9.5.
Н е с у щ е с т в у е т д е т е р м и н и р о в а н н о г о а л г о р и т м а и з б р а н и я ли д ер а в а н о н и м н о м кольце, р а зм ер к о т о р о го за р а н е е н еи звест ен .Д о к а з а т е л ь с т в о . Мы приведем доказательство этого утверждения дляслучая однонаправленных колец, но если идея этого доказательства станет ясна,то распространить обоснование на случай двунаправленных колец не составиттруда. Предположим, что ряд процессов, начинающийся процессом ро и оканчивающийся процессом р д г _ 1 , образует кольцо так, что для каждого i < N — 1процесс pi может отправлять сообщения процессу р1+\ и процесс рдг- i можетотправлять сообщения процессу ро.
В конфигурации данного кольца обозначимсимволом d состояние процесса pi, а символом Mi — совокупность сообщений,адресованных процессу pi.Конфигурацию будем называть с и м м е т р и ч е с к о й , если состояния всех процессов одинаковы и также одинаковы множества сообщений, адресованных каждому процессу и пребывающих на этапе пересылки, т. е.V/, / : (с[ = C; A Mi = М,).Для каждого алгоритма на данном кольце строится такое вычисление С = (у о , у ь • •что каждая конфигурацияв последовательности С является симметрической.Обозначим символом уо симметрическую начальную конфигурацию.
Такая конфигурация существует, поскольку каждый процесс имеет одно и то же множествоначальных состояний и первоначально все множества Mi — пустые.Если конфигурация у*дг является терминальной, то построение завершено;вычисление С завершается симметрической конфигурацией. В противном случаеjkN является симметрической конфигурацией, в которой по меньшей мере однособытие осуществимо; предположим, что это событие е; в процессе pi. Симметричность конфигурации позволяет заключить, что такое же событие осуществимо9.2. Детерминированные алгоритмы333в каждом процессе. Из теоремы 2.19 следует, что это событие может быть осуществлено параллельно всеми процессами, и после выполнения этих N переходовобразуется симметрическая конфигурация.
Действительно, все процессы перешли из одинаковых состояний в одинаковые же состояния. Если событие предполагает прием сообщения, то это сообщение изымается из каждого из идентичныхмножеств Mi, а если происходит отправление сообщения, то оно добавляется ккаждому из идентичных множеств А/,-. Следовательно, продолжив наше вычисление и совершив N шагов, мы вновь придем к симметрической конфигурацииT(*+i )N-Таким образом, каждый алгоритм для данного анонимного кольца имеет вычисление, которое либо является бесконечным, либо завершается симметрической конфигурацией.
В симметрической конфигурации либо все процессы пребывают в состоянии leader, либо ни один процесс не пребывает в этом состоянии;значит, в симметрической конфигурации один единственный процесс не можетпребывать в состоянии leader. Для детерминированного алгоритма избрания лидера все конфигурации завершаются терминальной конфигурацией, в которойровно один процесс пребывает в состоянии leader. Это означает, что таких алгоритмов для нашего кольца не существует.□Из теоремы 9.5 следует, что и более общая задача о выборах в произвольныхсетях или кольцах неизвестного размера также неразрешима детерминированными алгоритмами.9.2.2.
Вычисление функций на кольцеВ связи с невозможностью проведения выборов возникает вопрос о том, существуют ли более простые задачи, которые можно решить даже в том случае,если избрание лидера невозможно. В этом параграфе рассматривается задачавычисления значения функции на ориентированном анонимном кольце. Предположим, что на вход процесса pi подаются данные х,- e l , и пусть SX обозначаетмножество всех последовательностей элементов из X. Функцию /, определеннуюна SX, назовем циклической, если она инвариантна относительно циклическихсдвигов входных данных, т. е. f(y) = /(х) для всех циклических сдвигов у последовательности х.
Примерами циклических функций могут служить функции суммирования, максимума и минимума на целых числах, булевы функции дизъюнкции,конъюнкции и сложения по модулю два, а также функция вычисления длины входа. Предположим, что процесс р наделен переменной resultp; тогда постусловиевсякого алгоритма вычисления / имеет вид «resultp = /(хо, . . . , хдг-i)».Результаты этого параграфа свидетельствуют о том, насколько важна информация о размере кольца, а также о том, насколько существенны различияв завершении вычисления по признаку окончания работы процессов и окончанияприема сообщений.Размер кольца известен.
Если размер кольца известен, то всякая циклическая функция может быть вычислена некоторым детерминированным алгоритмомпутем накопления всех входных данных каждым процессом. Такое решение носит334Гл. 9. Анонимные сетиназвание н а к о п л е н и е в х о д о в . Для накопления входов требутся N(N — 1) сообщений, и эта величина служит нижней оценкой сложности вычисления некоторыхфункций детерминированными алгоритмами.Теорема 9.6.
Е с л и р а з м е р к о л ь ц а и з в е с т е н , т о в с я к а я ц и к л и ч е с к а я ф у н к ция / м ож ет бы т ь вы числена неко т о р ы м д ет ер м и н и р о ва н н ы м а лго р и т мом, за вер ш а ю щ и м вы чи слен и е по п р и зн а к у о к о н ч а н и я р аб от ы процессов,с и с п о л ь з о в а н и е м N ( N — 1) с о о б щ е н и й .Д о к а з а т е л ь с т в о .
Чтобы сделать наше обоснование более наглядным,будем считать, что в каналах поддерживается очередность сообщений. По ходуработы алгоритма сообщения отправляются на протяжении N —1 этапов. На первом этапе каждый процесс отправляет свои собственные входные данные соседуслева и принимает входные данные своего соседа справа. На каждом последующем этапе всякий процесс отправляет соседу слева данные, полученные им напредыдущем этапе, и принимает от соседа справа новые данные. Поскольку каждая порция входных данных на каждом этапе достигает всякий раз еще одногопроцесса, на г-м этапе всякий процесс принимает данные, принадлежащие егог-му по порядку соседу справа; таким образом, каждый процесс сумеет накопитьвсе входные данные (в том порядке, в котором они располагаются относительноэтого процесса на кольце) за N — 1 этапов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
