|
Реферат: Распределенные алгоритмыДля конфигурация называется v-решенной, если для некоторого ; конфигурация называется решенной, если она 0-решенная или 1-решенная. В -решенной конфигурации какой-нибудь процесс принял решение . Конфигурация называется v-валентной, если все решенные конфигурации, достижимые из нее, v-решенны. Конфигурация называется бивалентной, если из нее достижимы как 0-валентные, так и 1-валентные конфигурации, и унивалентной, если она либо 1-валентная, либо 0-валентная. В унивалентной конфигурации, хотя никакое решение не было обязательно принято никаким процессом, окончательное решение уже неявно определено. Конфигурация -устойчивого протокола называется развилкой, если существует множество (самое большее) из процессов и конфигурации и такие, что , , и -валентна. Неформально, - развилка, если подмножество из процессов может добиться 0-решенности так же, как и 1-решенности. Следующее утверждение формально фиксирует, что в любой момент оставшиеся процессы должна вынести аварию самое большее процессов. Утверждение 13.4 Для каждой достижимой конфигурации t-устойчивого алгоритма и каждого подмножества S по меньшей мере из N-t процессов существует решенная конфигурация такая, что . Доказательство. Пусть и удовлетворяют условию и рассмотрим выполнение, которое достигает конфигурации и содержит бесконечно много событий в каждом процессе из впоследствии (и никаких шагов процессов не из ). Это выполнение - t-аварийное законное, и процессы в корректны; следовательно они достигают решения o Лемма 13.5 Достижимой развилки не существует. Доказательство. Пусть - достижимая конфигурация и - подмножество самое большее из процессов. Пусть будет дополнением , т.е., . В по меньшей мере N-t процессов, следовательно существует решенная конфигурация такая, что (Утверждение 13.4). Конфигурация либо 0-, либо 1-решенная; положим, что она 0-решенная. Сейчас будет показано, что ни для какой 1-валентной ; пусть - любая такая конфигурация, что . Так как шаги в и заменяются (Утверждение 13.1), есть конфигурация , которая достижима и из , и из. Так как - 0-решенна, то и- тоже, что показывает не 1-валентность . o 13.1.2 Доказательство невозможности Сначала, используя нетривиальность проблемы, покажем что существует бивалентная начальная конфигурация (Лемма 13.6). Вполедствии будет показано, что начиная с бивалентной конфигурации, каждый доступный шаг можно исполнять без перехода в унивалентную конфигурацию (Лемма 13.7). Этого достаточно, чтобы показать невозможность алгоритмов согласия (Теорема 13.8). В дальнейшем, пусть А - 1-аварийно-устойчивый алгоритм согласия. Лемма 13.6 Для А существует бивалентная начальная конфигурация. Доказательство. Так как А нетривиален (Определение 13.3), то есть достижимые 0- и 1-решенные конфигурации; пусть и - начальные конфигурации такие, что -решенная конфигурация достижима из . Если , эта начальная конфигурация бивалентна и результат имеет силу. Иначе, есть начальные конфигурации и такие, что -решенная конфигурация достижима из , и и различаются входом одного процесса. Действительно, рассмотрим последовательность начальных конфигураций, начинающуюся с и заканчивающуюся , в которой каждая следующая начальная конфигурация отличается от предыдущей в одном процессе. (Эта последовательность получается инвертированием входных битов одного за другим.) Из первой конфигурации в последовательности, , достижима 0-решенная конфигурация, и из последней, , достижима 1-решенная конфигурация. Так как решенная конфигурация достижима из каждой начальной конфигурации, описанные и можно найти в последовательности. Пусть - процесс, в котором и различны. Рассмотрим законное выполнение, начинающееся с , в которой не делает шагов; это выполнение 1-аварийно законное и следовательно достигает решенной конфигурации . Если 1-решенная, бивалентна. Если 0-решенная, заметьте, что отличается от только в , а не делает шагов в выполнении; следовательно достижима из , что показывает бивалентность . (Более точно, конфигурация достижима из , где отличается от только в состоянии ; следовательно 0-решенная.) o Чтобы поñòðîèòь законное выполнение без принятия решения мы должны показать, что каждый процесс может сделать шаг, и что каждое сообщение может быть получено не обуславливая принятие решения. Пусть шаг s обозначает получение и обработку отдельного сообщения или спонтанное действие (внутреннее или посылки) отдельного процесса. Состояние процесса, делающего шаг, может привести к различным событиям. Прием сообщения применим, если оно в пути, и спонтанный шаг всегда применим. Лемма 13.7 Пусть - достижимая бивалентная конфигурация и s - применимый шаг для процесса p в . Существует последовательность событий такая, что s применим в , и бивалентна. Доказательство. Пусть С - множество конфигураций, достижимых из без применения s, т.е., С = {: s не происходит в }; s применим в каждой конфигурации С (напомним, что s - шаг, а не отдельное событие). В С есть конфигурации и такие, что из достижима v-решенная конфигурация. Чтобы убедится в этом, заметим, что, т.к. бивалентна, из нее достижимы v-решенные конфигурации для v =0,1. Если (т.е. для достижения решенной конфигурации s не применялся), заметим, что , тем не менее, v-решенная, поэтому выберем . Если (т.е. для достижения решенной конфигурации s применялся), выберем как конфигурацию, из которой применялся s. Если , - искомая бивалентная конфигурация. Предположим, что , и рассмотрим конфигурации на путях от до и . Две конфигурации на этих путях называются соседними, если одна получается из другой за один шаг. Так как 0-решенная конфигурация достижимаа из и 1-решенная конфигурация достижима из , то (1) на путях есть конфигурация такая, что бивалентна; или (2) есть соседи и такие, что 0-валентна и - 1-валентна. В первом случае - искомая бивалентная конфигурация и лемма доказана. Во втором случае, одна конфигурация из и - развилкой, что является противоречием. Действительно, предположим, что получена за один шаг из , т.е., для события e в процессе q. Теперь - это и, следовательно, 1-валентна, но не 1-валентна, т.к. уже 0-валентна. Итак, е и s не заменяются, что подразумевает (Теорема 2.19) , что p = q, но тогда достижимая конфигурация удовлетворяет и . Так как первая 0-валентна, а последняя 1-валенттна, - развилка, что является противоречием. o Теорема 13.8 Асинхронного, детерминированного, 1-аварийно-устойчивого алгоритма согласия не существует. Доказательство. Если предположить, что такой алгоритм существует, можно построить законное выполнение без принятия решения, начиная с бивалентной начальной конфигурации . Когда построение дойдет до конфигурации , выберем в качестве применимый шаг, который был применим самое большое число раз. По предыдущей лемме, выполнение можно расширить так, что исполняется и достигается бивалентная конфигурация . Такое построение дает бесконечное законное выполнение, в котором все процессы корректны, но решение никогда не будет принято. o 13.1.3 Обсуждение Вывод утверждает, что не существует асинхронных, детерминированных, 1-аварийно-устойчивых алгоритмов решения для проблемы согласия; это исключает алгоритмы для класса нетривиальных проблем. (см. Подраздел 12.2.2). К счастью, некоторые предположения, лежащие в основе результата Фишера, Линча и Патерсона, можно выразить явно, и результат, как оказывается, очеть чувствителен к ослаблению любого из них. Несмотря на вывод о невозможности, многие нетривиальные проблемы имеют решения, даже в асинхронных системах и где процессы могут отказывать. (1) Ослабленная модель отказов. Раздел 13.2 рассматривает модель отказов изначально-мертвых процессов, которая слабее, чем модель аварий, и в этой модели согласие и выборы детерминированно достижимы. (2) Ослабленная координация. Раздел 13.3 рассматривает проблемы, которые требуют менее тесной координации между процессами, чем согласие, и показывает, что некоторые из этих проблем, включая переименование, разрешимы в модели аварий. (3) Рандомизация. Раздел 13.4 рассматривает протоколы с уравненными вероятностями, где требование завершения достаточно ослаблено, чтобы обеспечить решения даже при присутствии Византийских отказов. (4) Слабое требование завершения. Раздел 13.5 рассматривает другое ослабление требования завершения, а именно где разрешение требуется только когда данный процесс корректен; здесь также возможны Византийско-устойчивые решения. (5) Синхронность. Влияние синхронности изучается далее в Главе 14. Возможны довольно тривиальные решения, если одно из трех требований Определения 13.3 просто опущено; см. Упражнение 13.1. Исключение предположения (неявно использованного в доказательстве Леммы 13.6) о том, что возможны все комбинации входов, изучается в Упражнении 13.2. 13.2 Изначально-мертвые Процессы В модели изначально-мертвых процессов, ни один процесс не может отказать после исполнения события, следовательно, при законном выполнении каждый процесс исполняет либо 0, либо бесконечно много событий. Определение 13.9 t-изначально-мертвых законное выполнение - выполнение, в котором по крайней мере N-t процессов активны, каждый активный процесс исполняет бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, принимается. В t-изначально-мертвых-устойчивом алгоритме согласия, каждый корректный процесс принимает решение в каждом t-изначально-мертвых законном выполнении. Согласованность и нетривиальность определяются так же, как в модели аварий. var , , : sets of processes init 0; begin shour <name, >; (* т.е.: forall do send<name, > to *) while < L do begin receive<name, >; end; shout<pre, , >; ; while do begin receive<pre, , >; ; ; end; Вычислить узел в G end Алгоритм 13.1 Вычисление узла. Так как процессы не отказывают после посылки сообщения, то для процесса безопасно ждать приема сообщения от , зная, что уже послал по меньшей мере одно сообщение. Будет показано, что проблемы согласия и выборов разрешимы в модели изначально-мертвых, пока отказывает меньшинство процессов (t < N/2). Большее число изначально-мертвых процессов не допускается (см. Упражнение 13.3). Соглашение о подмножестве корректных процессов. Сначала представляется алгоритм Фишера, Линча и Патерсона [FLP], с помощью которого каждый из корректных процессов вычисляет одну и ту же совокупность корректных процессов. Способность восстановления этого алгоритма ; пусть равно , и заметим, что корректных процессов по меньшей мере . Алгоритм работает в два этапа; см. Алгоритм 13.1. Заметим, что процессы посылают сообщения сами себе; это делается во многих устойчивых алгоритмах и облегчает анализ. Здесь и в дальнейшем, операция “shout<mes>” означает forall do send<mes> to . Эти процессы строят ориентированный граф , “выкрикивая” свой идентификатор (в сообщении <name, >) и ожидая приема сообщений. Так как корректных процессов по меньшей мере , каждый корректный процесс получает достаточно много сообщений для завершения этой части. Преемники в графе - вершины , из которых получил сообщение <name, >. Изначально-мертвый процесс не получал и не посылал никаких сообщений, следовательно он формирует изолированную вершину в ; у корректного процесса есть преемников, следовательно, он не изолирован. Узел - это сильносвязный компонент без исходящих дуг, содержащий по меньшей мере две вершины. В есть узел, содержащий корректные процессы, и, так как каждый корректный процесс имеет степень выхода , этот узел имеет размер по меньшей мере . В результате, так как , существует ровно один узел; назовем его . В конечном счете, так как корректный процесс имеет преемников, по меньшей мере один из них принадлежит , что означает, что все процессы в - потомки . Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42 |
|
|||||||||||||||||||||||||||||
|
Рефераты бесплатно, реферат бесплатно, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения, курсовые, дипломы, научные работы и многое другое. |
||
При использовании материалов - ссылка на сайт обязательна. |