Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 85
Текст из файла (страница 85)
Обоснуйте корректность алгоритма Раны (алгоритма 8.10)на основе инвариантов этого алгоритма.Упражнение 8.9. Внесите изменения в алгоритм Раны (алгоритм 8.10) так,чтобы для передачи сообщений можно было использовать произвольный волновой алгоритм, а не только кольцевой алгоритм.9.1. Основные понятияГЛАВА 9АНОНИМНЫЕ СЕТИВ предыдущих главах, для того чтобы различать процессы распределенной системы, обычно выдвигалось допущение об уникальности отличительных признаков. Это допущение справедливо применительно к большинству существующихраспределенных систем. В качестве отличительного признака процесса часто выбирается адрес, по которому данному процессу отправляются сообщения.
Однакодля упомянутой цели процессы можно также идентифицировать посредством косвенной адресации (см. § 2.4.4), при которой каждый процесс выделяется средисвоих соседей за счет локально известных имен каналов.Совсем по-другому отличительные признаки использовались в гл.
7; в этойглаве при помощи отличительных признаков удавалось разрушать симметриюна множестве процессов. Типичный пример подобного явления уже проявляетсяв простом алгоритме Ченя—Реверса (алгоритм 7.3), когда он инициируется двумяпроцессами p и q. В ходе его вычисления процесс p получает маркер, порожденный процессом q, а q получает маркер, порожденный процессом p. Ситуация былабы абсолютно симметричной, не будь у нас возможности упорядочить отличительные признаки процессов.
Это упорядочение разрушает симметрию; наименьший из двух процессов выживает, а наибольший терпит неудачу. В гл. 7 можноотыскать и другие алгоритмы, которые дают более сложные примеры разрушениясимметрии при помощи сопоставления отличительных признаков.Отличительные признаки, обладающие глобальной уникальностью, применялись также и для обнаружения завершения вычислений, например в алгоритмеФинна (алгоритм 6.8). Процесс обнаруживает, что ему удалось косвенным образом собрать информацию о всех процессах, если совпадают два семейства имен,где одно из этих семейств Inc включает имена всех соседей процессов из множества NInc (более подробно это описано в § 6.2.6 ). Подобное же использованиеотличительных признаков, но в гораздо более изощренной форме применяетсяи в алгоритме Галладжера—Хамблета—Спиры (см.
§ 7.3.2).В этой главе сравниваются вычислительные возможности анонимных сетей и именованных сетей: какие из задач, разрешимые для именованных сетей,можно также решить и в случае анонимных сетей? Этот вопрос совсем не праздный, хотя интересен он, главным образом, с чисто теоретической точки зрения,поскольку в большинстве распределенных систем все процессы снабжены уникальными именами.
Но на практике мы можем столкнуться также и с анонимнымисетями, когда дешевые (например встроенные) устройства объединяются в сеть.Примером здесь могут служить игрушки вида Lego MindStorm: многочисленныеконтроллеры можно собрать в модели и соединить друг с другом, но при этом кон-323троллеры являются серийными микросхемами, и все они совершенно идентичны.Прежде всего, результаты, представленные в настоящей главе, выделяют классызадач, которые нельзя решить, не прибегая к существенной помощи имен процессов. Возможно, неожиданным примером здесь служит реализация синхронного обмена сообщениями (см.
§ 9.1.4). Кроме того, представлены результаты,показывающие, что в случае конструирования сетей из идентичных процессоров,наподобие микросхем для транспьютеров или игрушек Lego MindStorm, должны быть соблюдены определенные условия. Компоненты должны быть снабжены генераторами случайных чисел, чтобы выполнять вероятностные алгоритмы,и размер сети должен быть известен процессорам, или же для сети необходимо применять централизованную инициализацию.
И действительно, контроллерыMindStorm снабжены случайными числами.В этой главе мы покажем, что в анонимных сетях можно разрушить симметрию, но невозможно обнаружить завершение вычисления, если размер сетизаранее не известен. Разрушить симметрию можно при помощи вероятностных алгоритмов. В таких алгоритмах процессы многократно «подбрасываютмонету», до тех пор пока не получат разные результаты; как только это случится,симметрия будет разрушена. Излишне говорить, что построить распределенныйалгоритм, обеспечивающий сравнение и повторное подбрасывание, оказывается гораздо сложнее, нежели строго сформулировать его принцип действия (см.§ 9.5.3).
Обнаружение завершения возможно, если известен размер сети; подсчитывается число процессов, согласных с заявленным результатом, и завершениесчитается обнаруженным, если это число в точности равно размеру сети. Обнаружить завершение вычисления, используя подбрасывание монеты, нельзя, поскольку существует очень малая вероятность того, что при таком подбрасываниипроцессы будут получать одинаковые результаты, после чего может быть принятоошибочное заключение о завершении вычисления (см. § 9.5.4).Как уже было отмечено, вероятностные алгоритмы могут быть плодотворно использованы в анонимных сетях для разрушения симметрии; их формальноеопределение приведено в § 9.5.1.
В связи с этим возникает несколько различныхвероятностных определений корректности, которые приведены в том же параграфе. Вероятностые алгоритмы очень важны для анонимных сетей, но помимоэтого они представляют интерес и в других разделах теории распределенных вычислений. Так, в гл. 14 будет показано, что они играют важную роль для достижения отказоустойчивости распределенных систем. Кроме того, для некоторыхзадач, разрешимых при помощи детерминированных алгоритмов, существуют вероятностные решения, имеющие меньшую сложность; однако далее эту тему мыв нашей книге обсуждать не будем.9.1. Основные понятияАнонимной сетью называется сеть, в которой невозможно различать процессы по индивидуальным отличительным признакам.
Предполагается также, чтонет и заранее выделенного лидера. Следовательно, процессы, подключенные к одному и тому же числу каналов, совершенно идентичны. Энглуин в работе [8]Гл. 9. Анонимные сети325Вероятностные алгоритмы. Модель вероятностного процесса образуется за счет того, что некоторый процесс подбрасывает монету на каждом шаге своего выполнения. Совокупность очередных возможных шагов зависит не толькоот состояния процесса, но также и от исходов подбрасывания монеты на предыдущих шагах процесса.
Первый шаг процесса зависит от исхода подбрасывания,совершенного в начальном состоянии.Невероятностные процессы (или алгоритмы) обычно называют детерминированными процессами (или алгоритмами); однако этот термин не исключаетвозможности того, что сеть невероятностных процессов функционирует недетерминированно. Такого рода сети ведут себя недетерминированно в соответствиис моделью из гл. 2, но при этом выбор обусловлен расписанием событий в вычислении, и он не поддается никакому вероятностному анализу. А вот выбор,возникающий в связи с рандомизацией, подчиняется вероятностному анализу,благодаря которому на множестве вычислений системы вводится распределение вероятностей. Чтобы сделать это распределение явным, в формальной модели предполагается, что вся последовательность подбрасываний монеты, котораяосуществляется процессом по ходу его выполнения, задана заранее до началавыполнения.Чтобы лучше понять формальное определение, мы вначале рассмотрим процессы, допускающие только внутренние события.
Вероятностный процесс задается четверкой p = (Z, I, `0 , `1), где элементы множеств Z и I точно такие же,В этом параграфе будет показано, как можно обобщить модель распределенных систем, введенную нами в гл. 2, чтобы охватить алгоритмы, опирающиесяна рандомизацию. Рандомизация состоит в том, чтобы при помощи «электронного подбрасывания монеты» и генератора случайных чисел добиться случайногоповедения процесса, причем каждое из возможных случайных поведений проявляется с известной вероятностью.
Рандомизацию следует отличать от недетерминизма, обусловленного как непредсказуемостью относительного быстродействияпроцессов, так и тем обстоятельством, что всякий процесс наделен возможностьюпо-разному продолжить одно и то же вычисление за счет реализации различныхсобытий.
Мы применяем программное средство, чтобы определить распределениевероятностей на совокупности вычислений системы, и благодаря этому получаемвозможность говорить о том, что свойства алгоритма соблюдаются с определенной вероятностью. Недетерминизм, присущий распределенным системам, нельзяконтролировать, и поэтому проектировщик алгоритмов должен всегда уметь совладать с наихудшим из всех вариантов выбора, возникающим в связи с неустранимым недетерминизмом.9.1.1. Определениякак и в определении 2.4, а `0 и `1 — это бинарные отношения на Z. Процесссовершает i-й шаг согласно отношению `0 , если исходом i-го подбрасывания монеты был ноль, и согласно отношению `1 в противном случае.
Рассмотрим бесконечную последовательность = ( 0 , 1 , . . .) исходов подбрасывания монеты, т. е.последовательность, состоящую из нулей и единиц. Тогда -выполнением процесса p назовем такую максимальную последовательность состояний c 0 , c1 , . . .,что c0 ∈ I и (ci , ci+1) ∈ ` i . Отметим, что неустранимый недетерминизм по-прежнему присутствует, поскольку заданному исходу подбрасывания монеты могутотвечать различные события. Однако никаких вероятностных допущений относительно их выбора сделать нельзя. А вот что касается вероятностного выбора,то здесь делается допущение о том, что для всякого k > 0 любая последовательность из k битов осуществляется в качестве префикса с одной и той же вероятностью (а именно 2−k).
Если последовательность задана, то вероятностныйпроцесс ведет себя так же, как и детерминированный процесс, который можнорассматривать как частный случай вероятностного процесса.Чтобы ввести обмен сообщениями между процессами, всякий процесс определяют восьмеркой, состоящей из множества состояний, множества начальныхсостояний и шести отношений событий, а именно событий отправления, событийприема и внутренних событий как для нулевого, так и для единичного исхода подбрасывания монеты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
