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

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

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

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

Распределенные алгоритмы41прошедшее между моментом отправления этой информации и моментом принятиярешения, состояние других узлов может измениться, и это обстоятельство делаетустаревшую информацию неактуальной.Узлы системы не способны оценить состояние коммуникационной подсисте­мы (в частности, они не могут знать о том, какие сообщения пребывают на этапепересылки в тот или иной момент времени), поскольку содержимое каналов свя­зи не поддается прямому наблюдению со стороны узлов.

Эти сведения можнополучить косвенным образом, проведя дедуктивный анализ информации о техсообщениях, которые были отправлены и получены всеми узлами системы.2. Отсутствие глобальной шкалы времени. Все события, которые возни­кают при выполнении централизованного алгоритма, можно вполне упорядочитьестественным образом в зависимости от времени их осуществления; для каждойпары событий одно из них происходит ранее или позднее другого. Подобное отно­шение предшествования по времени, введенное на множестве событий, которыевозникают при выполнении распределенного алгоритма, не является тотальным:для некоторых пар событий есть основания считать, что одно из них происходитранее или позднее другого, но есть и такие пары событий, ни одно из которыхнельзя счесть произошедшим ранее или позднее другого [124].В централизованной системе очень просто добиться взаимно исключенногодоступа к ресурсу: если процесс р обращается к ресурсу позже процесса q, тои доступ к ресурсу будет предоставлен процессу р только после того, как про­цесс q освободит этот ресурс.

И в самом деле, все события, о которых идет речь(начало и окончание доступа к ресурсу процессами р и q), вполне упорядоченыотношением предшествования по времени. В распределенных системах такогоможет не быть, и этой стратегии уже недостаточно. Процессы р и q могут об­ратиться к ресурсу, но ни для одного из этих процессов начало его обращенияк ресурсу не предшествует по времени началу обращения другого.3. Недетерминизм. Для заданных входных данных централизованная про­грамма строит одно-единственное вычисление, оно разворачивается совершеннооднозначно и недвусмысленно.

А вот выполнение распределенной системы, на­против, обычно бывает недетерминированным, ввиду того что быстродействиеразличных компонентов системы оказывается разным.Рассмотрим ситуацию, когда процесс-сервер ожидает поступления заранеенеизвестного числа запросов от клиентских процессов. Сервер не может отло­жить обработку запросов, пока они все не будут ему доставлены, поскольку он незнает, как много сообщений ему поступит.

Значит, каждый запрос должен бытьобработан немедленно, и обрабатываться запросы должны в порядке их поступ­ления. Даже если известен порядок отправления этих запросов клиентами, за­держки, возникающие при их передаче, никогда точно не известны, и поэтомузапросы могут поступать совсем в другом порядке.Все это вместе взятое — отсутствие сведений о глобальном состоянии, отсут­ствие глобальной шкалы времени и недетерминизм — приводит к тому, что задачапроектирования распределенных алгоритмов становится весьма замысловатой,из-за того что эти три особенности могут встречаться в самых разнообразныхсочетаниях.42Гл. 1. Введение: распределенные системыПонятия времени и состояния очень тесно связаны друг с другом: в цен­трализованных системах понятие времени вводится на основе последователь­ности состояний, которые достигаются по ходу выполнения программы. И хотядля распределенных систем можно определить понятие глобального состояния ивыполнение программы можно мыслить как последовательность глобальных со­стояний (см.

определение 2.2), подобная точка зрения представляется довольноограниченной, поскольку то же самое выполнение может быть образовано другойпоследовательностью глобальных состояний (теорема 2.21). Такие альтернатив­ные последовательности обычно состоят из разных глобальных состояний, и по­этому нет особого смысла говорить о том, что то или иное состояние достигаетсяпо ходу выполнения распределенной программы.Отсутствие сведений о глобальном состоянии можно было бы возместить воз­можностью предвидеть достижимость этого состояния по ходу выполнения ис­ходя из устройства алгоритма. К сожалению, и этого нельзя сделать из-за недетерминизма, неизбежно возникающего при выполнении распределенных систем.1.3.2.

Пример связи с передачей одного сообщенияМы проиллюстрируем те затруднения, которые обусловлены отсутствием све­дений о глобальном состоянии и отсутствием глобальной шкалы времени, на при­мере одной задачи надежного обмена информацией по ненадежному каналу свя­зи, которая обсуждается в работе Бельснеса [26]. Рассмотрим два процесса аи Ь, связанных друг с другом в какой-либо сети, которая позволяет передаватьданные от одного процесса к другому. Сообщение может быть доставлено скольугодно поздно после своего отправления, а может и вообще потеряться в сети.Надежность коммуникации можно повысить, если воспользоваться процедурамиуправления сетью (NCPs 17^), при помощи которых процессы а и b получают до­ступ к сети.

Процесс а начинает устанавливать соединение, передав одну единицуинформации т процедуре А. Взаимодействие между процедурами управления се­тью (через сеть передачи данных DN 18^) должно быть организовано так, чтобыинформация т была доставлена процессу Ь (при посредничестве NCP В), и по­сле этого процесс должен быть оповещен об этой доставке (при посредничествеNCP А).

Структура коммуникаций изображена на рис. 1.5.Даже в том случае, когда процесс а должен передать процессу b тодько однуединицу информации, ненадежность сети вынуждает NCP А и NCP В вступитьв диалог, который сопровождается обменом целым рядом сообщений. Эти проце­дуры сохраняют информацию о том, в каком состоянии находится этот диалог, новвиду того что число партнеров, с которыми каждый процесс вступает в диалог,может быть очень велико, после завершения обмена сообщениями вся инфор­мация о состоянии диалога стирается.

Инициализация информации о состояниидиалога называется открытием диалога, а сброс информации о его состоянииназывается закрытием диалога. Нужно иметь в виду, что после закрытия диа17)18)Network Control Procedures. — Прим, перев.Data Network. — Прим, перев.1.3. Распределенные алгоритмы43Рис. 1.5. Упрощенная архитектура сетилога NCP перейдет как раз в то состояние, в котором эта процедура пребывалаперед открытием этого диалога; это состояние мы будем называть закрытымсостоянием.Говорят, что блок информации т был потерян , если процесс а был оповещено приеме этого блока процессом Ь, но сам блок при этом так и не был никогдадоставлена процессу Ь. Говорят, что блок информации т был дублирован , еслион была доставлен дважды. Надежное средство связи должно предотвращатькак потери, так и дублирования.

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

К этому выводу можно прийтинезависимо от устройства сети передачи данных и процедур управления этой се­тью, основываясь лишь на предположении о том, что NCP может утрачиватьинформацию о ведущемся диалоге.Чтобы убедиться в этом, предположим, что, после того как процесс а иници­ировал соединение, процедуры А н В вступают в диалог, в ходе которого NCP Вдолжна доставить информацию т процессу Ь после получения сообщения М отNCP А. Рассмотрим случай, когда NCP В выходит из строя и перезапускаетсяв закрытом состоянии, после того как NCP А уже отправила сообщение М.

В этойситуации ни NCP А, ни NCP В не могут сказать, была ли информация т ужедоставлена в тот момент, когда NCP В вышла из строя. Процедура А не можетэтого сделать, потому что она не может судить о том, какие события произошлив NCP В (из-за отсутствия сведений о глобальном состоянии), а процедура Вне может этого сделать, потому что она вышла из строя и была перезапущенав закрытом состоянии. Ошибка может возникнуть независимо от того, как про­цедуры управления сетью продолжат свой диалог. Если NCP А вновь отправитсообщение NCP В и NCP В доставит это сообщение, то произойдет дублирова­ние информации. А если подтверждение а будет отправлено, тогда как доставкаинформации т не состоялась, то случится потеря информации.44Гл.

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

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

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

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