Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 93
Текст из файла (страница 93)
Покажите, что существует детерминированный алгоритмизбрания лидера, оканчивающий работу по завершении обменов сообщениями,в непериодическом псевдо-анонимном кольце заранее известного размера.Упражнение 9.13. Покажите, что не существует вероятностного алгоритмаизбрания лидера, оканчивающего вычисления по завершении работы процессов,в непериодическом псевдоанонимном кольце заранее неизвестного размера, который выдавал бы правильные результаты с положительной вероятностью.9.5.4Гл. 9. Анонимные сетиГ Л А В А 10МОМЕНТАЛЬНЫЕ СОСТОЯНИЯ СИСТЕМЫРассмотренные нами до сих пор алгоритмы (за исключением тех, что изучались в гл.
8) выполняют задачи, связанные с внутренним устройством сети илис глобальным функционированием сети. В этой главе мы обсудим алгоритмы,задача которых состоит в анализе свойств вычислений, порождаемых, как правило, другими алгоритмами. Однако обнаруживается, что следить за вычислениями распределенной системы изнутри самой системы — это невероятно труднаязадача.
При проектировании алгоритмов, работающих с системными вычислениями, важным конструктивным блоком служит процедура расчета и сохраненияв памяти отдельной конфигурации этого вычисления, так называемого моментального состояния системы.Согласно определению 2.22, распределенное вычисление описывается различными последовательностями конфигураций, и в этих последовательностях представлены разные совокупности конфигураций. Поэтому совсем неясно, какие изконфигураций рассматриваются в качестве конфигураций того или иного вычисления. Этот вопрос будет поставлен в § 10.5.1, где мы свяжем воедино понятиясечения, согласованного сечения и моментального состояния системы.
Эти понятия тесно связаны с понятием причинно-следственной зависимости, введеннымв § 2.Построение моментальных состояний системы объясняется их использованием в целом ряде приложений, и здесь мы рассмотрим три из них.Во-первых, свойства вычисления, в той мере, в какой они представлены в отдельной конфигурации, можно анализировать в режиме off-line, т. е.
при помощиалгоритма, который исследует (фиксированное) моментальное состояние всей системы, а не (изменчивые) текущие состояния процессов. К числу таких свойствотносится устойчивые свойства; свойство P конфигураций называется устойчивым, если справедливо соотношение=⇒ P( ).P( ) ∧Упражнение 9.14. Пусть функция g определена так же, как в упражнении 9.10.
Постройте вероятностный алгоритм избрания лидера, оканчивающийработу по завершении обменов сообщениями и правильно вычисляющий g в кольце заранее неизвестного размера с вероятностью 1 − .Упражнение 9.15. Можно ли обнаружить завершаемость алгоритма Айтаи—Роде (алгоритм 9.5) при помощи алгоритма Сафры обнаружения завершения (алгоритм 8.7)?Можете ли вы предложить для этой цели другой алгоритм обнаружения завершения из числа тех, которые обсуждались ранее?Иными словами, если вычисление достигает конфигурации , обладающей свойством P, то, начиная с этого момента, свойством P будет обладать каждая последующая конфигурация .
Следовательно, если будет обнаружено, что свойствоP выполняется для моментального состояния некоторой конфигурации системы, то отсюда можно сделать вывод о выполнимости P для всех последующихконфигураций. К устойчивым свойствам относятся завершенность вычисления,блокировка (попадание в тупиковую ситуацию), потеря маркера, а также недостижимость объектов в структурах динамической памяти. В § 10.4 мы применим350352Гл. 10. Моментальные состояния системымоментальные состояния системы для решения проблемы обнаружения тупиковых ситуаций.Во-вторых, моментальные состояния системы можно использовать вместо начальных конфигураций, если требуется перезапустить вычисление ввиду отказакакого-либо процесса. Для этого процесс p следует переустановить в то локальное состояние cp , которое было запечатлено в моментальном состоянии системы,после чего работа алгоритма будет продолжена.В третьих, моментальные состояния системы являются полезным средствомотладки распределенных программ.
Проведя в режиме off-line анализ конфигурации, «выхваченной» из ошибочного выполнения, можно обнаружить причину,по которой программа ведет себя не так, как этого ожидают.10.1. Начальные сведениякоторое называется моментальным локальным состоянием процесса p. Если(i)моментальным локальным состоянием процесса является c p , т. е. p проводит моментальный снимок состояния в промежутке между осуществлением событий e p(i)(i+1)(j)и ep , то события ep , для которых j 6 i, называются предмоментальнымисобытиями процесса p, а те события, для которых j > i, называются постмоментальными событиями процесса p. На временных диаграммах запечатлениелокального состояния процесса будет отмечаться незакрашенным кружком тогосостояния процесса, которое стало его моментальным состоянием (см.
рис 10.1и 10.2).(0)cp10.1. Начальные сведенияРассмотрим вычисление C распределенной системы, состоящей из некоторого множества процессов P; обозначим символом Ev множество событий этоговычисления. Мы будем исходить из допущения слабой справедливости, которое заключается в том, что каждое сообщение будет доставлено по назначениюспустя конечный промежуток времени. Мы будем предполагать также, что сетьявляется сильно связной. Локальное вычисление процесса p представляет собой(0)(1)(0)последовательность cp , cp , .
. . состояний процесса, где cp — это начальное(i−1)(i)в состояние cp обусловленсостояние процесса p. Переход из состояния cp(i)осуществлением события ep в процессе p (см. рис. 10.1). Таким образом, Ev == ∪p∈P {ep(1) , ep(2) , . . .}.На множестве событий процесса p введем причинно-следственный порядок при помощи соотношенияep(i) p ep(j) ⇐⇒ i 6 j.Каждое событие может быть событием отправления сообщения, приема сообщения или внутренним событием (соответствующие определения представлены в гл.
2). Для упрощения описания алгоритмов и формулировки теорем мыбудем всегда придерживаться допущения о том, что вся история обмена информацией с процессом определяется его состоянием. Это означает, что если суще(i)ствует канал связи, ведущий из p в q, то состояние c p процесса p включает в себя(i)список sentpq сообщений, которые процесс p отправил процессу q при осуществ(1)(i)(i)лении событий начиная с ep и оканчивая ep . Кроме того, состояние cq процесса(i)q содержит список rcvdpq сообщений, которые процесс q получил от процесса p(1)(i)при осуществлении событий, начиная с eq и оканчивая eq .
В § 10.3.1 будет показано, как можно устранить это допущение, чтобы избежать явного храненияв памяти историй обмена информацией в приложениях наших алгоритмов.Алгоритм построения моментального состояния системы предназначен дляреконструкции глобальной конфигурации, которая образуется из локальных состояний (моментальных состояний) всех процессов. Процесс p запечатлеваетсвое локальное состояние, записывая в память одно локальное состояние c ∗p ,3536u6e (1)(1)cpu u6e (i)ppНачальное состояние(i)cpe6c∗p = cp(i)u6e (i+1)u-pЗапечатлениемоментального состоянияРис.
10.1. Вычисление процесса pГлобальное моментальное состояние S∗ образуется из моментальных состояний c∗p всех процессов p, входящих в множество P. Для обозначения этогомы будем использовать запись S∗ = (c∗p1 , . . . , c∗pN ). Так как локальные состояния включают в себя истории обменов информацией, моментальное состояниеS∗ определяет конфигурацию ∗ , если состоянием канала pq считать множествосообщений, отправленных 1) процессом p (согласно состоянию c∗p), но еще недоставленных процессу q (согласно состоянию c ∗q).
Иными словами, состояниеканала pq в моментальном состоянии S∗ определяется множеством сообщенийsent∗pq \ rcvd∗pq . Конфигурацию, состоящую из моментальных состояний процессови определенных таким образом состояний каналов, обозначим символом ∗ .При построении указанной конфигурации появляются некоторые отклонения,если множество rcvd∗pq не является подмножеством sent∗pq (см. рис 10.2).
Судяпо локальному состоянию c∗p1 в формируемом моментальном состоянии системы, сообщение было отправлено процессом p1 процессу p3 , но, как отмеченов локальном состоянии c∗p3 , никакого сообщения от p1 не было получено. Такимобразом, в данном моментальном состоянии системы канал p 1 p3 содержит одно сообщение; говорят, что в этом моментальном состоянии системы указанноесообщение пребывает «на этапе пересылки».Обратимся теперь к сообщению, которое процесс p 1 отправил процессу p2 .Отправление этого сообщения относится к числу постмоментальных событий,тогда как его получение является предмоментальным событием. Значит, в соответствии с состоянием c∗p1 никакие сообщения по каналу p1 p2 не отправлялись,тогда как в состоянии c∗p2 отмечено, что по этому каналу было получено некоторое сообщение.
Поскольку rcvd∗p1 p2 6 ⊆sent∗p1 p2 , никакого осмысленного состояния1) Поэтому каналу. — Прим. перев.354Гл. 10. Моментальные состояния системыканалу p1 p2 придать нельзя. Это побуждает нас обратиться к следующему определению.Определение 10.1. Моментальное состояние S∗ называется осуществимым, если для всякой пары соседних процессов p и q выполняется включениеrcvd∗pq ⊆ sent∗pq .Осуществимость моментального состояния означает, что при построении соответствующей конфигурации в rcvd∗pq не останется ни одного сообщения, котороенельзя удалить из sent∗pq .
Сообщение, отправление которого является предмоментальным (постмоментальным) событием, будем называть предмоментальным(соответственно, постмоментальным) сообщением.Существует взаимнооднозначное соответствие между моментальными состояниями и конечными сечениями на совокупности событий вычисления. Сечениемназывается совокупность событий, замкнутая влево относительно отношения локальной причинно-следственной зависимости.10.1. Начальные сведенияи поэтому оно не определяется вычислением однозначно.
Таким образом, мы будем считать разумным всякий результат работы алгоритма, если он приводитк построению какой-либо конфигурации, которая окажется возможной для заданного вычисления (т. е. случится в некоторой реализации этого вычисления).Определение 10.3. Моментальное состояние S∗ называется значимым в вычислении C, если существует такая реализация E ∈ C, что ∗ является конфигурацией E.Мы будем требовать от алгоритма построения моментального состояния такойкоординации регистрации локальных моментальных состояний, чтобы полученное в результате этого глобальное моментальное состояние оказалось значимым.Своевременность запечатления моментальных состояний обсуждается в § 10.3.2.p1p2Определение 10.2.
Сечением на множестве Ev называется такое подмножество L ⊆ Ev, для которого выполняется соотношениеp3e ∈ L ∧ e0 p e =⇒ e0 ∈ L.Сечение L2 считается более поздним, чем сечение L1 , если верно включениеL1 ⊆ L 2 .С одной стороны, нетрудно видеть, что для каждого моментального состоянияS∗ совокупность L всех пред-моментальных событий является конечным сечением. Рассмотрим теперь произвольное конечное сечение L. Для каждого процесса p либо ни одно событие, произошедшее в p, не входит в L (в таком случае(m )будем полагать mp = 0), либо в L существует наибольшее событие e p p и при(m )этом все события e p ep p также содержатся в L.
Поэтому L представляет собой в точности множество предмоментальных событий моментального состояния(mp )(mp )S∗ = (cp1 1 , . . . , cpN N ).Моментальное состояние будет использоваться для извлечения информациио том вычислении, которое оно запечатлевает, но произвольно выбранное моментальное состояние системы дает очень мало информации о таком вычислении.Рассмотрим, например, алгоритм, в основу которого положена передача уникального маркера; к таковым относятся алгоритмы обхода из § 6.6.3. Допустим,что процесс p запечатлел свое состояние, когда он обладал маркером, и спустянекоторое время процесс q также запечатлел свое состояние, когда он, в своюочередь, обладал маркером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
