Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 92
Текст из файла (страница 92)
Упражнения к главе 99.5.1Упражнение 9.1. Пусть ф обозначает некоторое постусловие. Предположим, что в нашем распоряжении имеются1. алгоритм А типа Монте-Карло, оканчивающий вычисления по завершенииработы процессов и удовлетворяющий постусловию ф, и2. детерминированный алгоритм верификации В, оканчивающий вычисления по завершении работы процессов и проверяющий выполнимость ф.Покажите, как построить алгоритм С типа Лас-Вегас, удовлетворяющий постусловию ф.Упражнение 9.2. Пусть ф обозначает некоторое постусловие. Предположим, что в нашем распоряжении имеется алгоритм А типа Лас-Вегас. Предположим также, что известно математическое ожидание К числа обменов сообщениями в алгоритме А.
Требуется построить алгоритм типа Монте-Карло с параметризованной вероятностью неудачи е, удовлетворяющий постусловию ф. (Этоозначает, что алгоритм должен всегда завершать работу и выдавать правильныйответ с вероятностью 1 —е).Упражнение 9.3. Постройте детерминированный централизованный алгоритм выработки имен, которому требуется совершить 2 |£| обменов сообщениямиза 0(D) единиц времени.Упражнение 9.4 (см. [8]). Постройте детерминированный алгоритм избрания лидера в клике, если обмен сообщениями — синхронный.Упражнение 9.5.
Постройте детерминированные алгоритмы вычисления МАХдля колец и произвольных сетей заранее неизвестного размера, которые оканчивали бы работу по завершении обмена сообщениями.Упражнение 9.6. Рассмотрим задачу о выборах для анонимных деревьевзаранее неизвестного размера при том условии, что обмен сообщениями асинхронный.1. Постройте рандомизованный частично корректный алгоритм, который оканчивал бы вычисления по завершении работы процессов с вероятностью 1 и длякоторого ожидаемая сложность по числу обменов сообщениями составляла бывеличину 0(N).
(На самом деле можно добиться того, чтобы ожидаемая сложность по числу обменов сообщениями была равна /V+ 1 .)2. Можно ли построить для этого случая детерминированный алгоритм?9.5. Упражнения к главе 93499.5.2Упражнение 9.7. Докажите, что не существует детерминированного алгоритма подсчета количества процессов, который работал бы корректно для всеханонимных сетей, диаметр которых не превосходит 2 .Идея : воспользуйтесь симметричностью сетей, представленных на рис. 6.20.Упражнение 9.8. Докажите, что не существует детерминированного алгоритма избрания лидера в кольцах заранее известного четного размера при томусловии, что обмен сообщениями — синхронный.Обобщите доказательство на случай, когда размер сети задается составным числом.Упражнение 9.9.
Пусть задана функция / на целочисленных конечных последовательностях х = (х\,, Xk). Значение f{x) считается равным true, есливсе числа х; попарно равны; в противном случае значение /(х) равно false. Можно ли вычислить / при помощи детерминированного алгоритма, оканчивающеговычисления по завершении работы процессов, на кольцах заранее неизвестного размера? Можно ли вычислить / при помощи детерминированного алгоритма,оканчивающего вычисления по завершении обмена сообщениями, на кольцах заранее неизвестного размера?Упражнение 9.10. Тот же самый вопрос, что и в упражнении 9.9, но дляслучая, когда g(x) принимает значение true, если х имеет неубывающий циклический сдвиг, т. е.
существует такой циклический сдвиг z последовательности х,что i < jZ'i ^ Zj.9.5.3Упражнение 9.11. Постройте алгоритм типа Монте-Карло, оканчивающийвычисления по завршении работы процессов, для избрания лидера в анонимныхкольцах заранее неизвестного размера. Какова сложность построенного алгоритма по числу обменов сообщениями и какова вероятность его успешного завершения?Можно ли сделать вероятность успеха сколь угодно близкой к единице?Сеть, процессы которой имеют отличительные признаки, но при этом некоторые из этих признаков могут оказаться одинаковыми, называется псевдоанонимной сетью.
Псевдоанонимное кольцо (состоящее из процессов, начиная с рои оканчивая ры-\) называется периодическим, если существует такое число k << N, что для всех i выполняется равенство idi =Упражнение 9.12. Покажите, что существует детерминированный алгоритмизбрания лидера, оканчивающий работу по завершении обменов сообщениями,в непериодическом псевдо-анонимном кольце заранее известного размера.Упражнение 9.13. Покажите, что не существует вероятностного алгоритмаизбрания лидера, оканчивающего вычисления по завершении работы процессов,в непериодическом псевдоанонимном кольце заранее неизвестного размера, который выдавал бы правильные результаты с положительной вероятностью.9.5.4350Гл. 9.
Анонимные сетиУпражнение 9.14. Пусть функция g определена так же, как в упражнении 9.10. Постройте вероятностный алгоритм избрания лидера, оканчивающийработу по завершении обменов сообщениями и правильно вычисляющий g в кольце заранее неизвестного размера с вероятностью 1 —е.Упражнение 9.15.
Можно ли обнаружить завершаемость алгоритма Айтаи—Роде (алгоритм 9.5) при помощи алгоритма Сафры обнаружения завершения (алгоритм 8.7)?Можете ли вы предложить для этой цели другой алгоритм обнаружения завершения из числа тех, которые обсуждались ранее?ГЛАВА10МОМЕНТАЛЬНЫЕ СОСТОЯНИЯ СИСТЕМЫРассмотренные нами до сих пор алгоритмы (за исключением тех, что изучались в гл. 8) выполняют задачи, связанные с внутренним устройством сети илис глобальным функционированием сети. В этой главе мы обсудим алгоритмы,задача которых состоит в анализе свойств вычислений, порождаемых, как правило, другими алгоритмами. Однако обнаруживается, что следить за вычислениями распределенной системы изнутри самой системы — это невероятно труднаязадача.
При проектировании алгоритмов, работающих с системными вычислениями, важным конструктивным блоком служит процедура расчета и сохраненияв памяти отдельной конфигурации этого вычисления, так называемого моментального состояния системы.Согласно определению 2.22, распределенное вычисление описывается различными последовательностями конфигураций, и в этих последовательностях представлены разные совокупности конфигураций. Поэтому совсем неясно, какие изконфигураций рассматриваются в качестве конфигураций того или иного вычисления. Этот вопрос будет поставлен в § 10.5.1, где мы свяжем воедино понятиясечения, согласованного сечения и моментального состояния системы.
Эти понятия тесно связаны с понятием причинно-следственной зависимости, введеннымв §2.Построение моментальных состояний системы объясняется их использованием в целом ряде приложений, и здесь мы рассмотрим три из них.Во-первых, свойства вычисления, в той мере, в какой они представлены в отдельной конфигурации, можно анализировать в режиме off-line, т. е. при помощиалгоритма, который исследует (фиксированное) моментальное состояние всей системы, а не (изменчивые) текущие состояния процессов. К числу таких свойствотносится устойчивые свойства; свойство Р конфигураций называется устойчивым, если справедливо соотношениеР(у) А у8=£• Р(Ь).Иными словами, если вычисление достигает конфигурации у, обладающей свойством Р, то, начиная с этого момента, свойством Р будет обладать каждая последующая конфигурация 8 . Следовательно, если будет обнаружено, что свойствоР выполняется для моментального состояния некоторой конфигурации системы, то отсюда можно сделать вывод о выполнимости Р для всех последующихконфигураций.
К устойчивым свойствам относятся завершенность вычисления,блокировка (попадание в тупиковую ситуацию), потеря маркера, а также недостижимость объектов в структурах динамической памяти. В § 10.4 мы применим352Гл. 10. Моментальные состояния системымоментальные состояния системы для решения проблемы обнаружения тупиковых ситуаций.Во-вторых, моментальные состояния системы можно использовать вместо начальных конфигураций, если требуется перезапустить вычисление ввиду отказакакого-либо процесса. Для этого процесс р следует переустановить в то локальное состояние ср, которое было запечатлено в моментальном состоянии системы,после чего работа алгоритма будет продолжена.В третьих, моментальные состояния системы являются полезным средствомотладки распределенных программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
