Главная » Просмотр файлов » Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно)

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

Файл №1185664 Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf) 95 страницаВведение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664) страница 952020-08-25СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 95)

Так как в каналахподдерживается очередность сообщений, процесс q получил сообщение hmkri,до того как получил m, и в соответствии с приведенным алгоритмом процесс qзапечатлел свое моментальное состояние сразу по получении этого сообщенияили еще ранее того. Следовательно, получение сообщения m относится к числупостмоментальных событий.В алгоритме Ченди—Лэмпорта требуется совершить обмен 2|E| сообщениямиhmkri и использовать один дополнительный бит памяти (и, конечно же, к этому следует добавить память для хранения моментального состояния) в каждомпроцессе. Сложность по времени рассмотренного алгоритма составляет величинуO(D).10.2.2.

Алгоритм Лая—ЯнгаАлгоритм Лая—Янга (см. [122]) не опирается на свойство поддержания очередности сообщений в каналах. Поэтому отделить предмоментальные событияот постмоментальных при помощи маркеров, как это сделано в алгоритме Ченди—Лэмпорта, уже невозможно. Вместо этого каждое базовое сообщение снабжается пометкой, которая позволяет понять, является ли это сообщение предмоментальным или постмоментальным; для этого процесс p, отправляя сообщениепо ходу вычисления C, добавляет к нему значение taken p . Так как содержаниесообщений, относящихся к вычислению C, не играет здеь никакой роли, мы будемобозначать такие сообщения просто hmes, ci, где c — это значение переменной,включенное в состав сообщения процессом-отправителем.

Алгоритм построениямоментального состояния проверяет поступающие сообщения и записывает моментальное локальное состояние в том виде, в каком оно было до поступленияпервого постмоментального сообщения (см. алгоритм 10.5).var takenp: boolinit false ;Для запуска алгоритма:begin запомнить локальное состояние ; taken := true endДля отправления сообщения по ходу вычисления C:send hmes, takenp iЕсли поступило сообщение hmes, ci;begin receive hmes, ci ;if c and not takenp thenbegin запомнить локальное состояние ; taken := true end;изменить состояние на то, в котором пребывал процесспри получении сообщения в вычислении CendАлгоритм 10.5.

Алгоритм Лая-Янга построения моментального состояния360Гл. 10. Моментальные состояния системыВ алгоритме 10.5 нет обмена контрольными сообщениями, но он не можетгарантировать того, что каждый процесс рано или поздно запишет свое состояние; на самом деле бывает и так, что этой записи не происходит. Рассмотримпроцесс p, не являющийся инициатором алгоритма построения моментальногосостояния, и предположим, что ни один из соседей процесса p не отправляетпроцессу p сообщений, после того как этот сосед запечатлел свое моментальноелокальное состояние. В таком случае p никогда не проведет запись своего состояния, и алгоритм построения моментального состояния завершит работу, имеянеполное моментальное состояние.Решение этой проблемы зависит от того, что нам известно о вычислении C;если мы имеем гарантию, что связь с каждым процессом рано или поздно осуществится, то и полное моментальное состояние всегда можно будет запечатлеть.В противном случае алгоритм можно снабдить блоком, проводящим первоначальный обмен контрольными сообщениями между всеми процессами, как и в алгоритме 10.4.

Эти сообщения всего лишь гарантируют, что каждый процесс раноили поздно запишет свое состояние (как это установлено в лемме 10.6), но онине понадобятся при доказательстве осуществимости построенного моментальногосостояния системы. Так или иначе, вычисление полного моментального состояниясистемы обеспечено.Теорема 10.8. Алгоритм Лая—Янга (алгоритм 10.5) вычисляет толькозначимые моментальные состояния системы.Д о к а з а т е л ь с т в о. Рассмотрим моментальное состяние, вычисленноеалгоритмом, и пусть m = hmes, ci — это постмоментальное сообщение, отправленное процессом p процессу q.

Это значит, что c = true, и поэтому q запечатлевает свое состояние таким, каким оно было до получения сообщения m. Такимобразом, в состоянии, которое записал процесс q, не учитывается поступлениеm, и прием сообщения m относится к числу постмоментальных событий. (Следует напомнить, что существенным здесь является то, какое состояние записать,а не то, когда провести эту запись; в нашем случае запись состояния проводитсяодновременно с получением первого постмоментального события.)Использование подавления (замораживания). В алгоритме Ченди —Лэмпорта (алгоритм 10.4) маркеры используются для отделения предмоментальныхсообщений от постмоментальных, и поэтому в каналах требуется соблюдениеочередности сообщений.

В алгоритме Лая—Янга (алгоритм 10.5) в базовые сообщения явно вставляется пометка о том, является ли сообщение предмоментальным или постмоментальным, и, следовательно, здесь процессам должна бытьпредоставлена возможность реализовать принцип «оседлай поросенка» по отношению к информации, содержащейся в базовом сообщении. Тейлор в работе [186] показал, что если в канале не поддерживается очередность сообщений и «оседлать поросенка» невозможно, всякое решение проблемы построениямоментального состояния системы обязано быть ингибиторным, т.

е. полученоза счет временного приостановления базового вычисления. Классификация разных типов подавления и описание необходимых средств подавления при различ-10.3. Применение алгоритмов построения моментальных состояний361ных допущениях относительно коммуникационной среды представлены в работеКритчлоу и Тейлора [57] .10.3. Применение алгоритмов построения моментальныхсостояний10.3.1. Вычисление состояния каналаДо сих пор предполагалось, что состояние каждого процесса включает историю обмена информацией процесса и поэтому состояние всякого канала можновычислить на основе состояний примыкающих к нему процессов. В большинствеслучаев, однако, хранить в явном виде все сообщения, которые когда-либо отправлял или получал процесс, слишком накладно.

Мы покажем здесь, как можновосстанавливать состояние канала более эффективно.Редукция к значимой информации. В зависимости от предназначения моментального состояния системы может оказаться достаточным хранить толькоограниченный объем значимых сведений об истории обмена информацией. Например, мы можем вознамериться построить моментальное состояние алгоритма обмена маркерами (наподобие алгоритма Корача —Каттена—Морана), чтобыопределить, сколько маркеров все еще являются активными.

Чтобы определитьколичество маркеров в каждом канале, каждому процессу достаточно запоминать, сколько маркеров он отправил и сколько маркеров он получил. Вторымпримером может служить моментальное состояние системы для проверки завершенности вычисления (см. гл.

8). Для этого нужно всего лишь помнить о том, пустканал или нет, а для этого достаточно уметь считать сообщения, а не хранить ихв явном виде. (В обоих примерах при записи состояния каждого процесса можнотакже ограничиться небольшим объемом значимой информации, а именно числом маркеров, которыми обладает процесс, или, соответственно, указанием того,является ли процесс активным или пассивным.)Явное восстановление состояния канала.

Состояние канала можно восстановить в явном виде, опираясь на следующую лемму.Лемма 10.9. Если моментальное состояние системы является осуществимым, то sent∗pq \ rcvd∗pq образует в точности множество тех сообщений, отправление которых процессом p является предмоментальнымсобытием, а получение этих сообщений процессом q — постмоментальным событием.Д о к а з а т е л ь с т в о.

С одной стороны, нетрудно видеть, что сообщениеm ∈ sent∗pq \ rcvd∗pq отправлено предмоментально, а получено постмоментально.А с другой стороны, если сообщение m отправлено предмоментально и полученопостмоментально, то оно по определению включается в sent ∗pq , но не включаетсяв rcvd∗pq . Следовательно, такое сообщение принадлежит sent ∗pq \ rcvd∗pq .Процесс q восстанавливает состояние канала pq путем записи всех предмоментальных сообщений, которые были получены им постмоментально.

КольГл. 10. Моментальные состояния системыАлгоритм Лая—Янга. Если в канале не поддерживается очередность сообщений, процесс q может получать предмоменталные и постмоментальные сообщения поочередно; получение постмоментального сообщения не означает, чтовсе предмоментальные сообщения уже были доставлены. Поэтому, хотя и ясно,какие сообщения должны быть записаны процессом q (только те, которые помечены ярлыком false, являются предмоментальными), непонятно, в какой жемомент этот процесс уже завершил восстановление полного состояния каналаи может прекратить запись.Решение этой проблемы, предложенное Маттерном в работе [144] , состоитв том, чтобы заставить процесс p вести подсчет общего числа предмоментальныхсообщений, отправленных им процессу q, и уведомлять q об этом числе (либов отдельном сообщении, либо присоединяя это число к какому-либо постмоментальному сообщению по принципу «оседлать поросенка»).

Процесс q подсчитывает число полученных им предмоментальных сообщений (получение которыхбыло связано как с предмоментальными, так и с постмоментальными событиями) и завершает работу по восстановлению состояния канала, как только будетполучено достаточно большое число предмоментальных сообщений.10.3.2. Своевременность моментальных состояний системыМожно гарантировать, что моментальные состояния системы, которые строятся при помощи алгоритмов, рассмотренных в этой главе, являются значимымив тех вычислениях, для которых они были построены.

Но помимо этого нам хотелось бы, чтобы моментальное состояние было «свежим» в том смысле, чтоизвлеченная из такого состояния информация не должна быть слишком устаревшей. Коль скоро для оценки своевременности информации необходимо понятиевремени, мы будем привязывать моментальное состояние системы к конфигурациям, которые возникают при распределенном выполнении.

Характеристики

Тип файла
PDF-файл
Размер
2,78 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6488
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее