Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 92
Текст из файла (страница 92)
. , R}) ;send htest, estp , lblp , 1i to Nextpendelse skip (* Возможно, что вернулся маркер процесса p *)else (* est < estp *) skipendendАлгоритм 9.5. Вероятностное вычисление размера кольцаЛемма 9.14. Приведенный алгоритм оканчивает работу по завершении обмена O(N3) сообщениями.
В заключительной конфигурации все переменные estp равны, и их общее значение ограничено величиной N, т. е.для любой пары процессов p и q выполняется соотношение estp = estq 6 N.Д о к а з а т е л ь с т в о. Решающий этап обоснования завершаемости алгоритма — это демонстрация того, что оценки действительно остаются консервативными.
Заметим, что значение переменной estp никогда не убывает, а значениепеременной lblp изменятся только тогда, когда увеличивается значение est p . Отсюда следует, что, пока циркулирует маркер htest, est, lbl, hi, выпущенный процессом p, и выполняется равенство est = estp , будет выполняться и равенствоlblp = lbl. Воспользовавшись этим, можно провести индуктивное обоснованиетого, что все вычисленные оценки консервативны.Так как оценки, заложенные в маркеры, вычислены самими процессами, достаточно рассмотреть вычисление оценок, осуществляемое процессами. Здесьможно выделить три случая.9.4.
Вычисление размера сети3471. Процесс p может увеличить значение estp до est после получения маркерас оценкой est. А так как эта оценка была вычислена ранее, по предположниюиндукции можно считать, что она консервативна.2. Процесс p может увеличить значение estp до est + 1 после получениямаркера с оценкой est, если счетчик переходов маркера также показывает est.В таком случае, est консервативна по индуктивному предположению и, кроме тоговерно соотношение N 6= est, поскольку процесс, выпустивший данный маркер,отличен от процесса p и отстоит от него на est переходов.3. Наконец, процесс p можт увеличить estp до est + 1 после получения маркера с оценкой est = h = estp , если его пометка lbl 6= lblp . Процесс, выпустившийэтот маркер, отстоит на est переходов от p.
А так как lbl 6= lbl p , этот процессбудет отличен от p. И вновь отсюда следует, что N 6= est, а консервативностьоценки est влечет неравенство N > est.Каждый процесс порождает менее N различных маркеров, оценки которых пробегают числа от 2 до N, и при этом маркер с оценкой e совершает не более eпереходов. Отсюда следует, что число обменов сообщениями огранично величиной O(N3).
Если процесс p увеличивает значение estp , например до величины e, тоp отправляет процессу Nextp маркер, содержащий значение e. После полученияэтого маркера переменная estNextp будет иметь значение, не уступающее e, и поэтому в заключительной конфигурации выполняется неравенство est Nextp > estp .Оно выполняется для всех процессов p, и отсюда следует, что все оценки будутравны. А ранее мы показали, что они ограничены величиной N.Теорема 9.15.
Алгоритм 9.5 всегда завершает работу, и после завершения работы для всех процессов p с вероятностью, не меньшей 1− (N−2) (1/R) N/2 ,выполняется равенство estp = N.Д о к а з а т е л ь с т в о. Согласно лемме 9.14 работа алгоритма завершается такой конфигураций, в которой все оценки равны. Обозначим общее значениеэтих оценок символом e и предположим, что e < N. Обозначим процессы символами, начиная с p0 и оканчивая pN−1 , в порядке их обхода по кольцу противхода часовой стрелки.Процесс pi выбирает пометку lblpi . Он порождает маркер htest, e, lblpi , hi,когда значение estpi будет равно e.
Этот маркер совершит e переходов и достигнет процесса pi+e , который является e-м против хода часовой стрелки соседом процесса pi ; процесс pi+e , получив этот маркер, не станет увеличивать своюоценку. Это означает, что равенство lblpi = lblpi+e соблюдается для всех i. Пустьf = НОД(N, e). Тогда, учитывая равенства lblpi = lblpi+e , приходим к выводуо том, что всякий раз, когда номера i и j отличаются на величину, кратную f,пометки, выбранные процессами pi и pj совпадают, т.
е.f| (j − i) =⇒ lblpi = lblpj .Все процессы, начиная с p0 и оканчивая pN−1 , оказываются разбитыми на f групппо N/f процессов в каждой так, что все процессы из одной и той же группы имеютодинаковые пометки.348Гл. 9. Анонимные сетиНо поскольку пометки были выбраны случайным образом из множества {1, . .
. , R},вероятность того, что все процессы из одной группы выбрали одну и ту же пометку, будет равна (1/R) N/f−1 , а вероятность того, что это произойдет для всехгрупп, будет равна всего лишь (1/R) f (N/f−1) = (1/R) N−f . Для всех возможныхзначений e, величина f не превосходит N /2, и, суммируя вероятности завершенияработы со всеми возможными неправильными ответами (от 2 до N − 1), мы приходим к заключению о том, что вероятность правильного ответа будет не меньше1 − (N − 2) (1/R) N/2 .9.5. Упражнения к главе 99.5.1обозначает некоторое постусловие. ПредполоУпражнение 9.1. Пустьжим, что в нашем распоряжении имеются1.
алгоритм A типа Монте-Карло, оканчивающий вычисления по завершенииработы процессов и удовлетворяющий постусловию , и2. детерминированный алгоритм верификации B, оканчивающий вычисления по завершении работы процессов и проверяющий выполнимость .Покажите, как построить алгоритм C типа Лас-Вегас, удовлетворяющий постусловию .обозначает некоторое постусловие. ПредполоУпражнение 9.2. Пустьжим, что в нашем распоряжении имеется алгоритм A типа Лас-Вегас. Предположим также, что известно математическое ожидание K числа обменов сообщениями в алгоритме A. Требуется построить алгоритм типа Монте-Карло с параметризованной вероятностью неудачи , удовлетворяющий постусловию .
(Этоозначает, что алгоритм должен всегда завершать работу и выдавать правильныйответ с вероятностью 1 − ).Упражнение 9.3. Постройте детерминированный централизованный алгоритм выработки имен, которому требуется совершить 2|E| обменов сообщениямиза O(D) единиц времени.Упражнение 9.4 (см. [8]). Постройте детерминированный алгоритм избрания лидера в клике, если обмен сообщениями — синхронный.Упражнение 9.5. Постройте детерминированные алгоритмы вычисления MAXдля колец и произвольных сетей заранее неизвестного размера, которые оканчивали бы работу по завершении обмена сообщениями.Упражнение 9.6. Рассмотрим задачу о выборах для анонимных деревьевзаранее неизвестного размера при том условии, что обмен сообщениями асинхронный.1. Постройте рандомизованный частично корректный алгоритм, который оканчивал бы вычисления по завершении работы процессов с вероятностью 1 и длякоторого ожидаемая сложность по числу обменов сообщениями составляла бывеличину O(N).
(На самом деле можно добиться того, чтобы ожидаемая сложность по числу обменов сообщениями была равна N + 1.)2. Можно ли построить для этого случая детерминированный алгоритм?9.5. Упражнения к главе 93499.5.2Упражнение 9.7. Докажите, что не существует детерминированного алгоритма подсчета количества процессов, который работал бы корректно для всеханонимных сетей, диаметр которых не превосходит 2.Идея: воспользуйтесь симметричностью сетей, представленных на рис. 6.20.Упражнение 9.8. Докажите, что не существует детерминированного алгоритма избрания лидера в кольцах заранее известного четного размера при томусловии, что обмен сообщениями — синхронный.Обобщите доказательство на случай, когда размер сети задается составным числом.Упражнение 9.9.
Пусть задана функция f на целочисленных конечных последовательностях x = (x1 , . . . , xk): Значение f(x) считается равным true, есливсе числа xi попарно равны; в противном случае значение f(x) равно false. Можно ли вычислить f при помощи детерминированного алгоритма, оканчивающеговычисления по завершении работы процессов, на кольцах заранее неизвестного размера? Можно ли вычислить f при помощи детерминированного алгоритма,оканчивающего вычисления по завершении обмена сообщениями, на кольцах заранее неизвестного размера?Упражнение 9.10. Тот же самый вопрос, что и в упражнении 9.9, но дляслучая, когда g(x) принимает значение true, если x имеет неубывающий циклический сдвиг, т.
е. существует такой циклический сдвиг z последовательности x,что i < j =⇒ zi 6 zj .9.5.3Упражнение 9.11. Постройте алгоритм типа Монте-Карло, оканчивающийвычисления по завршении работы процессов, для избрания лидера в анонимныхкольцах заранее неизвестного размера. Какова сложность построенного алгоритма по числу обменов сообщениями и какова вероятность его успешного завершения?Можно ли сделать вероятность успеха сколь угодно близкой к единице?Сеть, процессы которой имеют отличительные признаки, но при этом некоторые из этих признаков могут оказаться одинаковыми, называется псевдоанонимной сетью. Псевдоанонимное кольцо (состоящее из процессов, начиная с p 0и оканчивая pN−1) называется периодическим, если существует такое число k << N, что для всех i выполняется равенство idi = idi+k .Упражнение 9.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
