Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 83
Текст из файла (страница 83)
Чтобы найти выход из положения, нужно еще более ослабить требование P. Каждыйпроцесс будет придавать волне окраску white или black. Волна преобразуетсятаким образом, чтобы по ходу ее движения определялась самая темная из приданных ей окрасок; здесь следует напомнить, что волновые алгоритмы способнывычислять точные нижние грани, и в качестве таковой рассматривается «самаятемная окраска». Когда волна принимает решение, определяется самая темнаяиз всех приданных ей окрасок.
Это будет окраска white, если все процессы придали волне окраску white, и окраска black, если хотя бы один процесс привнесв волну окраску black. Мы будем полагать, что волна по ходу своего движенияимеет окраску white, если ни один процесс еще не привнес в нее окраску black;если же хотя бы одни процесс привнес в волну окраску black, то и вся волнабудет иметь цвет black.
Таким образом, всякий процесс после посещения еговолной либо привносит в волну окраску white, сохраняя ее цвет неизменным,либо привносит окраску black и окрашивает тем самым всю волну в цвет black.Требование P замещается еще более ослабленным условием (P 0 ∨ P1 ∨ P2),гдеP2 ≡ волна имеет окраску black.Это условие сохраняется при выполнении Это условие сохраняется при выполнении следующего правила.Правило 3. Всякий процесс, который посетила волна, придает волне своютекущую окраску.И действительно, обмен базовыми сообщениями, равно как и действия, связанные с прохождением волны, сохраняют указанное условие, и оно, таким образом, становится инвариантом. Волна оканчивается безрезультатно, если процессы, принимающие решения, находят, что волна окрашена в цвет black. Нов таком случае просто запускается очередная волна.
Эта новая волна можетпривести к успеху только тогда, когда процессы приобретут окраску white, а этослучится сразу после того, как их посетит эта волна.Правило 4. Процесс, принявший решение в том случае, когда волна имелаокраску black, запускает новую волну.Правило 5. Каждый процесс приобретает окраску white сразу после того,как его посетила очередная волна.314Гл. 8.
Обнаружение завершенияЭти правила позволяют гарантировать, что рано или поздно после завершения базового вычисления прохождение очередной волны будет успешным. Действительно, если базовое вычисление завершилось, то первая волна, запущеннаяпосле этого завершения вычисления, окрасит все процессы в цвет white и следующая за ней волна успешно завершится.В этом алгоритме в каждый момент времени может распространяться толькоодна волна. Если две волны, назовем их A и B, распространяются параллельно,то «побелка» процесса волной B может нарушить инвариант для волны A.
Поэтому если возникает необходимость в децентрализованном алгоритме обнаружениязавершения вычисления, то децентрализованный волновой алгоритм должен бытьприменен так, чтобы все инициаторы алгоритма обнаружения работали совместнонад одной и той же волной. Можно воспользоваться также и другим принципомобнаружения, согласно которому разные волны могут вычисляться параллельно,не вызывая нарушений в правильной работе алгоритма обнаружения завершениявычислений (см. § 8.4.2).8.4. Прочие решенияВ этом параграфе мы обсудим два других метода решения задачи обнаружениязавершения вычислений: алгоритм возвращения кредита и алгоритм штемпелявремени.8.4.1.
Алгоритм возвращения кредитаВ статье [142] Маттерн предложил алгоритм, позволяющий обнаруживатьзавершение вычисления очень быстро, точнее говоря, спустя не более одной единицы времени, после того как это случилось (принимая во внимание идеализированные допущения о времени, представленные в определении 6.31).
Алгоритмобнаруживает завершение централизованного вычисления при условии, что каждый процесс способен отправить сообщение непосредственно самому инициаторувычисления (т. е., сеть содержит подграф, имеющий форму звезды, в центре которой расположен инициатор).В этом алгоритме каждому сообщению и каждому процессу вручается некоторый кредит; его значением служит вещественное число, расположенное между0 и 1 (включительно). Алгоритм стремится сохранить инвариантность следующихутверждений.S1.
Суммарный кредит, выданный сообщениям и процессам, равен 1.S2. Всякому базовому сообщению вручается положительный кредит.S3. Всякому активному процессу вручается положительный кредит.Процессы, имеющие положительный кредит и не подпадающие под перечисленные законы (т. е. пассивные процессы), возвращают кредит инициатору. Инициатор поступает подобно банку и собирает все кредиты, которые ему отправляют,в переменной ret (возвращенные кредиты).Когда инициатор владеет всеми кредитами, из требований, предписывающихактивным процессам и базовым сообщениям обладать положительным креди-8.4. Прочие решения315том, следует, что таковые процессы и сообщения отсутствуют.
Следовательно,предикат term будет истинен.Правило 1. Если ret = 1, то инициатор вызывает процедуру Announce.Чтобы выполнялось необходимое условие корректности, нужно обеспечитьвозвращение всех кредитов инициатору по завершении базового вычисления.Если базовое вычисление завершилось, то никаких базовых сообщений уже нети нам нужно разобраться с теми кредитами, которыми обладают процессы.Правило 2. Как только процесс становится пассивным, он отправляет свойкредит инициатору.var statepcredpret: (active, passive) init if p = p0 then active else passive ;: fractioninit if p = p0 then 1 else 0 ;: fractioninit 0 ; for p0 onlySp : { statep = active } (* Правило 3 *)begin send hmes, credp /2i ; credp := credp /2 endRp : { сообщение hmes, ci поступило процессу p }begin receive hmes, ci ; statep := active ;credp := credp + c (* Правила 4 и 5b *)endIp :{ statep = active }begin statep := passive ;send hret, credp i to p0 ; credp := 0end(* Правило 2 *)Ap0 : { Сообщение hret, ci поступило процессу p0 }begin receive hret, ci ; ret := ret + c ;if ret = 1 then Announce (* Правило 1 *)endАлгоритм 8.9.
Алгоритм возвращения кредитаВ начальной конфигурации активен один лишь инициатор, и он имеет положительный кредит, равный 1, причем ret = 0, а это означает, что требования S1 –S3соблюдены. По ходу вычисления нужно поддерживать инвариантность этих соотношений. Для этого служат следующие правила. Во-первых, каждому базовомусообщению должен быть выделен положительный кредит, когда оно отправляется; к счастью, отправитель сообщения активен и поэтому имеет положительныйкредит.Правило 3.
Когда активный процесс p отправляет сообщение, имеющийся вего распоряжении кредит разделяется между самим процессом p и этим сообщением.316Гл. 8. Обнаружение завершенияВсякому процессу должен быть выделен положительный кредит, когда он активизируется; к счастью, то сообщение, получение которого способствовало активизации, обладает положительным кредитом.Правило 4.
Когда процесс активизируется, ему вручается кредит, которымобладало активизировавшее его сообщение.И лишь одну возможность не охватывают перечисленные правила — получение активным процессом базового сообщения. Такой процесс уже располагает положительным кредитом и поэтому для выполнения требования S3 он ненуждается в том кредите, которым обладает указанное сообщение; однако этимкредитом нельзя пренебречь, ибо в таком случае было бы нарушено требованиеS1. Активный процесс, получивший сообщение, может распорядиться кредитомдвумя способами, и оба способа приводят к корректному алгоритму.Правило 5a.
Как только активный процесс получает базовое сообщение, кредит, которым обладало это сообщение, возвращается инициатору.Правило 5b. Как только активный процесс получает базовое сообщение, кредит, которым обладало это сообщение, добавляется к тому кредиту, которым располагал сам процесс.Описанные правила приводят к алгоритму 8.9 (здесь приведен вариант, в котором реализовано правило 5b). В этом алгоритме предполагается, что каждыйпроцесс осведомлен об имени инициатора (по крайней мере, в тот момент, когдапроцесс впервые становится пассивным). Когда инициатор становится пассивным, он отправляет сообщение самому себе.Теорема 8.11. Алгоритм возвращения кредита (алгоритм 8.9) является корректным алгоритмом обнаружения завершения вычислений.Д о к а з а т е л ь с т в о.
Алгоритм применяет правила 1 –5, и поэтому формула S1 ∧ S2 ∧ S3 , где X X Xc +credp +c + retS1 ≡ 1 =hmes,cip∈Phret,ciS2 ≡ ∀ hmes, ci на этапе пересылки : c > 0S3 ≡ ∀p ∈ P : (statep = passive =⇒ credp = 0)∧ (statep = active =⇒ credp > 0),является инвариантом алгоритма. Завершение вычисления обнаруживается, когда ret = 1. С учетом инварианта это означает, что предикат term истинен.Чтобы обосновать необходимое условие корректности, заметим, что после завершения вычисления не выполняется ни одно базовое действие.
Следовательно,происходит только прием сообщений hret, ci, и с каждым приемом число сообщений на этапе пересылки сокращается на единицу. Поэтому алгоритм достигаетзаключительной конфигурации. В такой конфигурации базовые сообщения отсутствуют (по определению предиката term), для всех процессов p выполняетсяравенство credp = 0 (по определению предиката term и в силу требования S 3)и отсутствуют сообщения hret, ci (ибо конфигурация является заключительной).8.4. Прочие решения317Это означает, что ret = 1 (в силу требования S1) и завершение вычисления будетобнаружено.Если применяется правило 5a, то число контрольных сообщений на единицупревосходит число базовых сообщений (мы принимаем в расчет также и сообщения, которые процесс p0 отправляет самому себе, когда становится пассивным).
Если применяется правило 5b, то число контрольных сообщений на единицупревосходит число внутренних событий в базовом вычислении, которое, в своюочередь, не более чем на единицу превосходит число базовых сообщений. Представляется, что правило 5b более предпочтительно с точки зрения сложностипо числу сообщений контрольного алгоритма. Совсем иначе дело обстоит, когдаречь заходит о битовой сложности. По правилу 5a каждая доля кредита в системе, за исключением ret, — это некоторая отрицательная степень числа 2 (т. е.она равна 2−i для некоторого натурального i).
Представляя кредит логарифмомпо основанию 1/2, мы сокращаем битовую сложность передаваемых сообщений.Алгоритм возвращения кредита — единственный алгоритм в этой главе, который предусматривает включение дополнительной информации (значение кредита)в базовые сообщения. Этот прием, при котором к базовым сообщениям присоединяется дополнительная информация, называют «оседлать поросенка».
Еслитакой эффект нежелателен, то кредит, выделенный базовому сообщению, можетбыть передан с контрольным сообщением, которое отправляется сразу же послеэтого базового сообщения. (В алгоритме, который представлен в следующем параграфе, также требуется «оседлать поросенка», если при реализации алгоритмаиспользуются логические часы Лампорта.)Проблема может возникнуть, если кредит (выделяемый сообщениям и процессам) составляет фиксированное число битов. В таком случае существует наименьший положительный кредит и разделить эту величину кредита на два уженевозможно. Когда нужно разделить наименьший возможный кредит, базовоевычисление приостанавливается, до тех пор пока процесс не востребует дополнительного кредита от инициатора.
Инициатор вычитает эту величину из ret (и в результате ret может принять отрицательное значение) и передает кредит запрашивающему процессу. После получения кредита базовое вычисление возобновляется. Это повышение кредита приводит к блокировке базового вычисления вопрекитребованию, гласящему, что алгоритм обнаружения завершения вычисления недолжен оказывать влияния на базовое вычисление. К счастью, такие операциислучаются редко.8.4.2. Решения, использующие штемпель времениВ этом параграфе рассматриваются решения задачи обнаружения завершениявычисления, использующие в своей основе штемпели времени. Предполагается,что все процессы снабжены часами (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
