Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 84
Текст из файла (страница 84)
е. в заключительной конфигурации длякаждого процесса р выполняется неравенство qtPo > qtp. Когда процесс ро пребывал в состоянии quiet в последний раз (т. е. в момент времени qtPo), он отправил маркер (tok, qtPo, qtPo, ро). Этот маркер совершил полный обход по кольцуи был возвращен процессу ро. Действительно, каждый процесс р в тот момент,когда к нему попал маркер, должен был пребывать в состоянии quiet и при этомдолжно было выполняться неравенство qtp ^ qtPo. Если бы это было не так, тоГл. 8.
Обнаружение завершения320процесс р по получении маркера пришлось бы установить на своих часах значение, превышающее qtPo, и перейти в состояние quiet позже, нежели это довелосьпроцессу ро, вопреки нашему выбору процесса ро. Когда маркер был возвращенпроцессу ро, этот процесс все еще пребывал в состоянии quiet и поэтому вызвалпроцедуру Announce.Чтобы обосновать достаточное условие корректности рассматриваемого алгоритма, предположим, что процесс ро вызывает процедуру Announce. Это происходит, когда ро пребывает в состоянии quiet и получает назад свой маркер(tok, 0 , qt, ро), который был переправлен ему поочередно всеми процессами.Проведем доказательство от противного.
Допустим, что условие term не соблюдается в тот момент, когда процесс ро обнаруживает завершение вычисления; этоозначает, что имеется процесс р, который не удовлетворяет условию quiet. В таком случае процесс р перестал удовлетворять условию quiet уже после того,как расстался с маркером, выпущенным процессом ро', ведь р должен был пребывать в состоянии quiet, когда передавал этот маркер. Пусть q — первый процесс, который перестал удовлетворять условию quiet после передачи маркера(tok, 0 , qt, ро).
Это означает, что процесс q был активизирован в результате получения сообщения от некоторого процесса г, который еще не участвовал в передаче маркера, выпущенного процессом ро, ибо в противном случае процесс гперестал бы удовлетворять условию quiet после передачи этого маркера, но дотого, как этому условию перестал удовлетворять процесс q, вопреки выбору q.Теперь после передачи указанного маркера неравенство 09 > qtPo будет по-прежнему соблюдаться. Отсюда следует, что в подтверждении, отправленном процессом q процессу г в ответ на сообщение, которое вывело q из состояния quiet,стоит метка времени 0о > qtPo. Таким образом, когда г перейдет в состояние quietпосле получения этого подтверждения, будет выполняться неравенство 0 r > qtPo,и поэтому в тот момент, когда процессу г вручат маркер, будет выполняться соотношение qtr > Ро.
Согласно описанию алгоритма процесс г не станет передаватьмаркер, вопреки тому, что маркер совершил полный обход по кругу.□Доказательство корректности, опирающееся на инварианты и функцию нормирования, предложено в работе ван Везеля [200]. Модификация рассмотренного алгоритма, не зависящая от кольцевой топологии, предложена в работе Хуана [109].8.5.
Упражнения к главе 88.5.1Упражнение 8.1. Опишите активные и пассивные состояния алгоритма А.2.Где можно найти эти состояния в алгоритме А. 1?8.5.2Сложность по времени алгоритма обнаружения завершения вычисленийопределяется количеством единиц времени, которое разделяют в худшем слу8.5. Упражнения к главе 8321чае (при идеализированных допущениях, указанных в определении 6.31) моментзавершения базового вычисления и момент вызова процедуры Announce.Упражнение 8.2.
Какова сложность по времени алгоритма Дейкстры—Шолтена?Упражнение 8.3. Алгоритм Шави—Франчеза применяется к произвольнойсети с уникальными отличительными признаками процессов, а для того, чтобыуменьшить издержки, связанные с передачей контрольных сообщений, в качестве волнового алгоритма используется алгоритм Галладжера—Хамблета—Спиры. Сложность по времени обнаружения завершения вычисления составляет величину О (A log А).Можно ли уменьшить эту оценку сложности по времени до величины 0(A) засчет дополнительного обмена 0(A) контрольными сообщениями?8.5.3Упражнение 8.4.
Почему предикат Pq, используемый при описании алгоритма Дейкстры—Фейджена—ван Гастерена, не опровергается, когда процессPj активизируется процессом pi так, что / sj t или i > t?Упражнение 8.5. Покажите, что для всякого т существует такое базовоевычисление, в котором происходит обмен т базовыми сообщениями, и при этомалгоритм Дейкстры—Фейджена—ван Гастерена совершает обмен т - (А —1) контрольными сообщениями.8.5.4Упражнение 8.6. Какие изменения следует внести в алгоритм 8.9, чтобыприменить правило 5а из алгоритма возвращения кредита, вместо правила 5Ь?Упражнение 8.7.
В алгоритме Раны предполагается, что процессы наделеныотличительными признаками. Предположим теперь, что все процессы анонимны, но обладают возможностью отправлять сообщения своим последователям покольцу, и при этом число процессов заранее известно.
Внесите в алгоритм 8.10необходимые изменения, позволяющие ему работать в рамках таких допущений.Упражнение 8.8. Обоснуйте корректность алгоритма Раны (алгоритма 8 .10)на основе инвариантов этого алгоритма.Упражнение 8.9. Внесите изменения в алгоритм Раны (алгоритм 8.10) так,чтобы для передачи сообщений можно было использовать произвольный волновой алгоритм, а не только кольцевой алгоритм.ГЛАВА9АНОНИМНЫЕ СЕТИВ предыдущих главах, для того чтобы различать процессы распределенной системы, обычно выдвигалось допущение об уникальности отличительных признаков. Это допущение справедливо применительно к большинству существующихраспределенных систем.
В качестве отличительного признака процесса часто выбирается адрес, по которому данному процессу отправляются сообщения. Однакодля упомянутой цели процессы можно также идентифицировать посредством косвенной адресации (см. §2.4.4), при которой каждый процесс выделяется средисвоих соседей за счет локально известных имен каналов.Совсем по-другому отличительные признаки использовались в гл. 7; в этойглаве при помощи отличительных признаков удавалось разрушать симметриюна множестве процессов.
Типичный пример подобного явления уже проявляетсяв простом алгоритме Ченя—Реверса (алгоритм 7.3), когда он инициируется двумяпроцессами р и q. В ходе его вычисления процесс р получает маркер, порожденный процессом q, a q получает маркер, порожденный процессом р. Ситуация былабы абсолютно симметричной, не будь у нас возможности упорядочить отличительные признаки процессов. Это упорядочение разрушает симметрию; наименьший из двух процессов выживает, а наибольший терпит неудачу. В гл. 7 можноотыскать и другие алгоритмы, которые дают более сложные примеры разрушениясимметрии при помощи сопоставления отличительных признаков.Отличительные признаки, обладающие глобальной уникальностью, применялись также и для обнаружения завершения вычислений, например в алгоритмеФинна (алгоритм 6 .8 ).
Процесс обнаруживает, что ему удалось косвенным образом собрать информацию о всех процессах, если совпадают два семейства имен,где одно из этих семейств Inc включает имена всех соседей процессов из множества Nine (более подробно это описано в §6.2.6 ). Подобное же использованиеотличительных признаков, но в гораздо более изощренной форме применяетсяи в алгоритме Галладжера—Хамблета—Спиры (см.
§7.3.2).В этой главе сравниваются вычислительные возможности анонимных сетей и именованных сетей: какие из задач, разрешимые для именованных сетей,можно также решить и в случае анонимных сетей? Этот вопрос совсем не праздный, хотя интересен он, главным образом, с чисто теоретической точки зрения,поскольку в большинстве распределенных систем все процессы снабжены уникальными именами. Но на практике мы можем столкнуться также и с анонимнымисетями, когда дешевые (например встроенные) устройства объединяются в сеть.Примером здесь могут служить игрушки вида Lego MindStorm: многочисленныеконтроллеры можно собрать в модели и соединить друг с другом, но при этом кон9.1.
Основные понятия323троллеры являются серийными микросхемами, и все они совершенно идентичны.Прежде всего, результаты, представленные в настоящей главе, выделяют классызадач, которые нельзя решить, не прибегая к существенной помощи имен процессов. Возможно, неожиданным примером здесь служит реализация синхронного обмена сообщениями (см. §9.1.4). Кроме того, представлены результаты,показывающие, что в случае конструирования сетей из идентичных процессоров,наподобие микросхем для транспьютеров или игрушек Lego MindStorm, должны быть соблюдены определенные условия. Компоненты должны быть снабжены генераторами случайных чисел, чтобы выполнять вероятностные алгоритмы,и размер сети должен быть известен процессорам, или же для сети необходимо применять централизованную инициализацию.
И действительно, контроллерыMindStorm снабжены случайными числами.В этой главе мы покажем, что в анонимных сетях можно разрушить симметрию, но невозможно обнаружить завершение вычисления, если размер сетизаранее не известен. Разрушить симметрию можно при помощи вероятностных алгоритмов. В таких алгоритмах процессы многократно «подбрасываютмонету», до тех пор пока не получат разные результаты; как только это случится,симметрия будет разрушена. Излишне говорить, что построить распределенныйалгоритм, обеспечивающий сравнение и повторное подбрасывание, оказывается гораздо сложнее, нежели строго сформулировать его принцип действия (см.§9.5.3). Обнаружение завершения возможно, если известен размер сети; подсчитывается число процессов, согласных с заявленным результатом, и завершениесчитается обнаруженным, если это число в точности равно размеру сети.
Обнаружить завершение вычисления, используя подбрасывание монеты, нельзя, поскольку существует очень малая вероятность того, что при таком подбрасываниипроцессы будут получать одинаковые результаты, после чего может быть принятоошибочное заключение о завершении вычисления (см. §9.5.4).Как уже было отмечено, вероятностные алгоритмы могут быть плодотворно использованы в анонимных сетях для разрушения симметрии; их формальноеопределение приведено в §9.5.1. В связи с этим возникает несколько различныхвероятностных определений корректности, которые приведены в том же параграфе. Вероятностью алгоритмы очень важны для анонимных сетей, но помимоэтого они представляют интерес и в других разделах теории распределенных вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
