Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 96

Во всяком выполнении вычисленное моментальное состояние системы располагается между тойконфигурацией, в которой началась запись состояния, и той, в которой эта записьзавершилась, о чем свидетельствует следующая теорема.Д о к а з а т е л ь с т в о. Усилим аргументацию, используемую при доказательстве теоремы 10.5. Построим последовательность событий f, сперва перечислив предмоментальные события выполнения E в порядке их осуществления в E,а затем занумеруем все постмоментальные события выполнения E в порядке ихосуществления в E. Такая нумерация не противоречит причинно-следственномупорядку в E и поэтому определяет некоторое выполнение F.Выполнение F содержит конфигурации s , ∗ , и e в указанном порядке, и отсюда следует утверждение теоремы.

Выполнение F содержит s , поскольку всесобытия из E, предшествующие s , являются предмоментальными событиями, и,следовательно, f начинается именно с этих событий и именно в том же порядке.Выполнение F содержит e , поскольку совокупность событий, предшествующихe в выполнении E, содержит все предмоментальные события. Значит, f начинается именно этими событиями (хотя, возможно, они следуют в другом порядке),и F содержит e на основании теоремы 2.21.10.3.3. Обнаружение устойчивых свойствРассмотрим устойчивое свойство P конфигураций; как только выполнениедостигает конфигурации, для которой выполняется P, это свойство будет продолжать выполняться и для каждой последующей конфигурации.

К устойчивымотносятся следующие свойства:1. Завершение вычисления. Если — это заключительная конфигурация, то = , и поэтому конфигурация также является заключительной.иСледовательно, задача обнаружения завершения (гл. 8) может быть решена засчет вычисления моментального состояния системы и анализа активных процессов и базовых сообщений в этом моментальном состоянии. Однако специальныерешения, предложенные в гл. 8 обычно более эффективны.2. Наличие тупиков. Если в конфигурации некоторое множество процессов S оказывается заблокированными, из-за того что все процессы из S пребывают в ожидании 3) других процессов из S, то такая же ситуация повторитсяи в последующих конфигурациях, хотя процессы вне множества S могут изменятьсвои состояния.

Задача обнаружения тупиков рассматривается в § 10.4.3. Потеря маркеров. Рассмотрим алгоритм, в котором маркеры циркулируют между процессами, а сами процессы могут поглощать маркеры. Свойствовида «Имеется не более k маркеров» является устойчивым, так как маркерымогут поглощаться, но не могут порождаться.3) поступлениясообщений от — Прим.

перев.Алгоритм Ченди—Лэмпорта. Все предмоментальные сообщения от p к qполучены перед тем, как сообщение hmkri было отправлено процессом p процессу q; даже, более того, только предмоментальные сообщения были получены допоступления маркера. Восстановить состояния канала в таком случае будет чрезвычайно просто: состояние канала pq представляет собой совокупность сообщений, полученных процессом q, после того как он сделал запись своего состояния,но до того, как он получил сообщение hmkri от процесса p.363Теорема 10.10.

Предположим, что имеется выполнение E, осуществимое моментальное состояние системы S∗ , запечатленное по ходу этоговыполнения, и соответствующая ему конфигурация системы ∗ . Пустьs — это конфигурация, в которой первый процесс записал свое состояние, а e — это конфигурация, в которой последний процесс записал свое∗состояние.

Тогда справедливо соотношение se.скоро все такие сообщения получены процессом q после запечатления его моментального состояния, q приступает к записи сообщений, после того как он записал свое состяние, и запись прекращается, как только все предмоментальныесообщения будут получены.10.3. Применение алгоритмов построения моментальных состояний362Гл. 10. Моментальные состояния системы10.3. Применение алгоритмов построения моментальных состоянийТеорема 10.12 (Полноты). Если выполнение E достигло конфигурации,в которой свойство P выполняется, то спустя конечный промежутоквремени алгоритм 10.6 присвоит переменной detect значение true.Д о к а з а т е л ь с т в о. Предположим, что — это первая конфигурация выполнения E, которая обладает свойством P. Рассмотрим конфигурацию s , следующую за (или совпадающую с ), в которой впервые после прохожденияпредпринято вычисление моментального состояния системы алгоритмом 10.6.Пусть ∗ — это моментальное состояние системы, вычисление которого началось∗, верно P( ∗),в конфигурации s .

Так как имеет место соотношениеsи алгоритм обнаружения завершает работу после этого тура.Алгоритм 10.6 можно использовать для решения всех задач по обнаружению устойчивых свойств, но при этом следует принять во внимание следующиезамечания.1. Для некоторых свойств P (распределенное) вычисление значения P( ∗)может потребовать применения достаточно сложных алгоритмов.

Такое случается для некоторых модельных вариантов задачи обнаружения тупиков (один изалгоритмов обнаружения тупиков в заданной конфигурации приведен в § 10.4).2. В некоторых случаях этим методом нельзя воспользоваться ввиду ограничений по объему памяти. Такое возможно в случае задачи по сбору «мусора»;сохранение в памяти всех ссылок и сообщений моментального состояния системы более чем вдвое увеличивает объем запрашиваемой памяти, и это можетоказаться слишком высокой ценой.Ранние алгоритмы по сбору «мусора» приостанавливали базовое вычисление при проведении оценки значения предиката, служащего индикатором наличия«мусора»; это решение представляется весьма простым, но обычно оно отвергается, поскольку приостановка базового вычисления представляется недопустимой.

Сравнительно недавно были разработаны алгоритмы, работающие «на лету»; вместо того чтобы заниматься отдельной конфигурацией, они взаимодействуют с базовым вычислением и не относятся к категории алгоритмов, применяющихвычисление моментального состояния системы (см. [187, глава 5] и [189]).3. Даже в тех случаях, когда решения, основанные на применении алгоритма 10.6, просты и эффективны, они могут оказаться не самыми простыми и ненаиболее эффективными. Это касается, например, задачи обнаружения завершения вычислений, для которой в гл. 8 были приведены совершенно простыерешения.Моментальные состояния системы можно использовать для вычисления монотонных функций, определенных на конфигурациях системы; функция f на: boolinit false ;∗;while notPholds dobegin вычислить глобальное моментальное состояниевычислить Pholds := P( ∗)end;detect := truevar detectАлгоритм 10.6.

Алгоритм обнаружения устойчивого свойстваВесьма общий механизм обнаружения представлен в алгоритме 10.6. В этомалгоритме требуется проводить проверку выполнимости свойства P для конфигурации, соответствующей моментальному состоянию системы, но обычно этоосуществляется при помощи сравнительно простой распределенной процедуры.В то время как задача алгоритма обнаружения состоит в том, чтобы отслеживать динамику поведения распределенного вычисления, такая процедура всеголишь анализирует статические данные (которые представлены в конфигурации).Вычисление процедуры Pholds можно провести либо централизованно, либо распределенно.

При централизованном вычислении каждый процесс отправляет своемоментальное состояние выделенному процессу, который восстанавливает полную конфигурацию и вычисляет Pholds. При распределенном вычислении всепроцессы участвуют в таком вычислении.Алгоритм 10.6 обладает свойствами корректности и полноты, о чем свидетельствуют следующие две теоремы; это как раз те свойства, которые требуютсяот всякого алгоритма обнаружения. Предположим, что алгоритм 10.6 следит занекоторым распределенным алгоритмом, который порождает выполнение E.Теорема 10.11 (Корректности).

Если алгоритм 10.6 присваивает значение true переменной detect, когда система пребывает в конфигурации ,то выполняется P( ).365Д о к а з а т е л ь с т в о. Пусть ∗ — это последнее из вычисленных моментальных состояний системы, а e — конфигурация выполнения E, в которой былозапечатлено последнее локальное состояние конфигурации ∗ .