Лекция 2. Распределенные задачи и алгоритмы - Лекция, раздел Философия, Распределенные системы и алгоритмы С Системой S Связана Цель G, Ради Которой Система Функционирует...
С системой S связана цель G, ради которой система функционирует. Эта цель ставится самой системой (если система – активная), или поставлена извне. Для достижения цели в системе должна решаться задача – некоторая математическая формализация цели с четко определенным набором исходных данных и требуемых результатов.
Решение задачи предполагается получать с помощью алгоритма, т.е. предписания с указанием исполнителя (исполнителей) и последовательности элементарных шагов, которые должны быть сделаны исполнителями.
Распределенная система порождает распределенную задачу, поскольку исходные данные для задачи возникают в различных точках пространства. Также в различных точках требуются те или иные результаты решения задачи. Зачастую, задачу можно разбить в совокупность подзадач, некоторые из них могут быть сосредоточенными: все исходные данные возникают в одной точке пространства, и там же требуются результаты решения подзадачи.
Распределенная задача решается распределенным алгоритмом, собирающим исходные данные из разных точек и посылающим результаты расчетов в разные точки. Дополнительным фактором распределенности алгоритма может быть наличие нескольких исполнителей, находящихся в разных точках пространства (распределенный исполнитель).
Известно, что алгоритм оперирует кроме исходных данных, еще и промежуточными данными, а в больших системах работает с базами данных. Для распределенного алгоритма закономерно встает вопрос: как будут организованы эти данные – в виде сосредоточенной или распределенной базы данных?
Один из видов распределенных алгоритмов – протоколы. Протокол характеризуется тем, что имеется как минимум две стороны, разделенные каналом связи. На каждой из сторон выполняется локальный (сосредоточенный) алгоритм Ak . Локальный алгоритм A1 выполняется до некоторого момента времени, когда для продолжения работы ему требуются данные от другого локального алгоритма A2 . Он посылает через линию связи запрос на данные локальному алгоритму A2 . Алгоритм A2 отвечает, пересылая сообщение по линии связи. После этого локальный алгоритм A1 продолжает свою работу.
Протоколы, обычно, играют техническую роль и служат для установления режимов приема/передачи данных между удаленными объектами. В вычислительном отношении локальные алгоритмы – части протокола – не являются сложными.
Особый вид распределенных алгоритмов – криптографические протоколы. Они предназначены для доказательства одной или обеими сторонами, что они именно те, за кого себя выдают, для обмена конфиденциальной информацией и других подобных целей.
Рассмотрим один из простейших криптографических протоколов – распределенных алгоритмов.
В разных точках пространства находятся два объекта, O1 и O2 , каждый из которых решает свою часть (P1 или P2) общей задачи P. Вместе с тем, кроме стремления решить общую задачу, объекты имеют и свои частные задачи, Q1 и Q2 . Таким образом, объект O1 решает одновременно задачи P1 и Q1 , а объект O2 – задачи P2 и Q2 . И, если задачи P1 и P2 совместимы и взаимно дополняют друг друга, то задачи Q1 и Q2 – противоречат друг другу.
Следовательно, объекты O1 и O2 сотрудничают, но, одновременно, и конкурируют. А можно сказать и, что объекты конкурируют, но вынуждены сотрудничать. Смотря как расставить акценты, какая из задач, Pi или Qi , важнее для объекта Oi .
Описанная ситуация встречается очень часто. Университеты заинтересованы в решении задачи совершенствования подготовки специалистов и в этой задаче они сотрудничают. В то же время ежегодно вузы конкурируют из-за способных абитуриентов. Научные организации часто проводят совместные исследования на стыке их интересов (на стыке наук). Но они же конкурируют при распределении финансов. Два различных подразделения фирмы работают для достижения общих целей фирмы, но каждое из них хочет получить в рамках фирмы большее развитие, чем другое подразделение. В общем, друзья-соперники. Частичная конкуренция.
В нашей задаче объекты O1 и O2 должны прийти к общему компромиссному решению в интересах решения задачи P. Предположим, что имеется два равноценных (с точки зрения задачи P) решения. Одно из них также устраивает объект O1 , а другое – устраивает объект O2 . Тогда объекты O1 и O2 решают бросить жребий. Это можно сделать: написать каждое решение на своей бумажке, свернуть бумажки в трубочку, прокрутить в лототроне и одну из бумажек вытащить. Это и будет компромиссное решение.
Сложность состоит в том, что объекты O1 и O2 находятся на большом расстоянии друг от друга, и не могут провести процедуру с лототроном. Процедура с лототроном выполняется в одном месте, она возможна для сосредоточенной системы. Наша система – распределенная.
Процедуру с лототроном мог бы выполнить объект O1 и сообщить результат объекту O2 .Однако объект O2 не вполне доверяет объекту O1 . Даже телевизионная трансляция выполнения процедуры не является убедительным доказательством – это может быть искусно смонтированная запись.
Выход состоит в следующем. Обозначим одно из решений числом 0, другое – числом 1. Каждый из объектов независимо от другого должен назвать какое-нибудь целое число ni в пределах, например, от 0 до 99. Затем объекты обмениваются числами ni и вычисляют результат n1 + n2 (mod 2). Это и будет решение, т.е. число 0 или 1.
Абсолютно одновременно переслать друг другу числа ni объекты не могут. Кто-то пришлет свое число первым и окажется в невыигрышном положении. Например, O1 переслал свое число n1 объекту O2 , заинтересованному в том, чтобы выиграло решение «1». Тогда O2 , зная n1 , решает уравнение n1 + n2 (mod 2) = 1 относительно переменной n2 , и посылает O1 найденное значение n2 . Решение уравнения практически не требует времени: получив от O1 четное число, O2 должен ответить нечетным, и наоборот.
Эта несправедливость должна быть устранена. При этом ясно, что все равно какая-то из сторон обмена сообщениями первой пришлет свое число. Необходимо сделать так, чтобы у второй стороны не хватило времени на «подбор ответа».
Объекты O1 и O2 могут договориться, что вся процедура «бросания жребия» на расстоянии должна завершиться за несколько минут. Если, при этом, оба объекта знают, что подбор ответа требует нескольких часов работы суперЭВМ, то они могут быть спокойны за то, что решение не «подстроено» другой стороной.
Для обеспечения таких временных параметров в вычислениях должна использоваться функция f(x), значение которой y = f(x) при известном аргументе x вычислить можно относительно быстро. Но вот решить уравнение f(x) = y, т.е. отыскать неизвестное x при известном значении y, быстро нельзя. Более того, желательно, чтобы не было известно никаких математических методов для решения этого уравнения, кроме полного перебора или подобного ему по сложности.
Конечно, область определения функции f(x) должна быть при этом очень большой, чтобы сделать практически невозможным полный перебор. Область из двух элементов, 0 и 1, мала, область от 0 до 99 тоже недостаточна. Целые числа, с которыми приходится оперировать, должны иметь в десятичной записи не менее 150-200 цифр или не менее 512 бит в двоичной записи. Такие числа называют «длинными».
Пусть f(x) и h(z, v, w) – две таких трудно обращаемых функции. В функции h(z, v, w) первые два аргумента – длинные числа, а третий – битовый. Функции f и h известны объектам O1 и O2 , и они владеют алгоритмами быстрого вычисления значений этих функций при заданных значениях аргументов, но не умеют быстро обращать эти функции, т.е. решать уравнения.
Распределенный алгоритм бросания жребия состоит из следующих шагов.
1. Объект O2 выбирает случайным образом число x из большого интервала [0, q – 1]. Вычисляет y = f(x).
2. Объект O2 пересылает число y объекту O1 . Объект O1 не сможет восстановить число x.
3. Объект O1 выбирает случайным образом число z из большого интервала [0, q – 1]. Объект O1 выбирает случайный бит w. Эти действия могут выполняться одновременно с п.1.
4. Объект O1 вычисляет s = h(z, y, w). Число z здесь необходимо для «маскировки» бита w, а число y – для «проверки» объектом O2 правильности действий объекта O1 .
5. Объект O1 пересылает число s объекту O2 . Бит w отправляется объекту O2 , но он «запрятан» в числе s. Объект O2 не сможет восстановить этот бит. Объект O2 не сможет восстановить и число z.
6. Объект O2 выбирает случайный бит c.
7. Объект O2 отправляет бит c объекту O1 . Открытая пересылка.
8. Объект O1 пересылает число z и бит w объекту O2 . Открытая пересылка. Объект O1 уже может определить результат бросания жребия: c + w (mod 2).
9. Объект O2 вычисляет t = h(z, y, w). Здесь z и w только что получены от O1 , а y было вычислено в п.1.
10. Объект O2 сравнивает t и s, ранее полученное от объекта O1 .
11. Если t = s, то объект O2 вычисляет результат бросания жребия: c + w (mod 2).
Функции f и h могут быть различными. В частности, используются функции:
f(x) = gx (mod p) и h(z, v, w) = vwgz (mod p).
Здесь «секретные» значения x, w, z находятся в показателях степеней, и для того, чтобы найти их, требуется решить задачу дискретного логарифмирования, для которой эффективный алгоритм, существенно лучший полного перебора, неизвестен.
Константы p, q, g должны быть известны тому и другому объектам. Число p – длинное простое число. Число q – также длинное простое число, являющееся делителем числа p – 1. Число g < p, не равное 1, удовлетворяет условию gq = 1 (mod p).
Одно из направлений в разработке распределенных алгоритмов – высокопроизводительные вычисления. Распределенная компьютерная система в этом случае используется как один мощный вычислитель, решающий одну задачу. Известным примером является задача «взлома» шифра, созданного алгоритмом шифрования DES. Дешифровка текста не представляет трудностей, если известен ключ шифрования. Если ключ не известен, то дешифровку можно попытаться выполнить путем полного перебора. Но метод полного перебора требует очень большого времени даже для самых быстрых однопроцессорных ЭВМ.
Решение задачи можно ускорить, используя многопроцессорную ЭВМ. В этом случае вычисления распараллеливаются, т.е. все процессоры одновременно, выполняя одинаковые или различные команды, участвуют в решении задачи. Как именно происходит распараллеливание – зависит от архитектуры многопроцессорной ЭВМ. При наличии в ее составе n процессоров в идеальной ситуации ускорение вычислений может достигать величины, близкой к n раз. Реально, алгоритмы не полностью распараллеливаются, часть процессоров может простаивать в отдельные периоды времени, и производительность увеличивается менее чем в n раз.
Современные многопроцессорные машины имеют десятки и сотни процессоров, отдельные – тысячи процессоров. Но такие уникальные машины очень дороги, установлены в специальных суперкомпьютерных центрах или в военных организациях и не всегда доступны рядовым пользователям.
Альтернативой является использование отдельных компьютеров, соединенных глобальными сетями связи и принадлежащих частным лицам и различным организациям. Компьютеры могут иметь относительно невысокую производительность, но использование в сети сразу нескольких десятков или сотен тысяч компьютеров для решения одной задачи создает эффект того же суперкомпьютера, но, может быть, еще более мощного.
Именно такая распределенная компьютерная система использовалась для упомянутой задачи дешифрования. Это не была «жесткая» система – компьютеры использовались на добровольной основе, в любой момент времени любой компьютер мог выйти из системы. Но точно также и новые компьютеры могли присоединяться к уже работающим.
Идея и соответствующая технология использования глобальной сети компьютеров для решения сложной задачи получила название Grid. Если Web обеспечивает доступ к глобальным информационным ресурсам, то Grid должен обеспечить доступ к глобальным вычислительным (обрабатывающим) ресурсам. Основные проекты использования Grid в настоящее время связаны с обработкой большого числа (терабайты, пентабайты) экспериментальных данных в физике элементарных частиц, наблюдений в астрономии, расшифровкой генома человека в биологии.
Распределенные системы и алгоритмы... Курс лекций...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Лекция 2. Распределенные задачи и алгоритмы
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Сосредоточенные и распределенные системы
Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функц
Тандемы распределенных систем
Рассмотрим две системы, S1 и S2 . Первая система функционирует для достижения некоторой цели G1 . При этом в любой момент времени имеется некот
Лекция 3. Надежность и безопасность распределенных систем
Сравним сосредоточенную и распределенную системы с точки зрения надежности и безопасности.
Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во в
Структура информационного пространства
Хотя термин «информационное пространство» является лишь метафорой, обратимся к проблеме анализа структуры этого пространства. Математики привыкли связывать с любым пространством некоторую структуру
Структуры РРИСО
Структуру РРИСО можно рассматривать с нескольких точек зрения. Прежде всего, это наиболее очевидная – географически ориентированная структура. Многие (но не все) элементы информационной системы при
Подсистемы. Взаимоотношения структур
Каждая из структур РРИСО строится по своим законам, поэтому, не стоит ожидать изоморфизма между парами структур. Идеально, если одни структуры являются надстройками над другими, использующими механ
Условная корпоративность
Хотя мы называем РРИСО корпоративной системой в силу того, что имеется определенный административный «каркас» на множестве ее пользователей, и у нее довольно четкая целевая направленность, тем не м
Неоднородность
Неоднородность – одна из важнейших характеристик РРИСО. Если многие корпоративные системы являются однородными, или неоднородность имеет место в одном - двух аспектах построения системы, то неоднор
Интегрируемость
Это одно из ключевых свойств в характеристике РРИСО. Это и «врожденное» и приобретаемое свойство.
Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы дан
Лекция 6. Моделирование распределенных систем. Язык Triad
Исследование распределенных систем – трудная задача. Прежде всего, распределенная система должна быть описана, т.е. должна быть построена модель системы. Для этой цели можно использовать различные
For i:= 1 to n do
routine(System2.Node[i]) := Generator
endf.
При этом создается n экземпляров рутины Generator. Для каждого экземпляра рутины создается свой комплект локальных пер
For i:= 1 to n – 1 do
System := System + (System.Node[i] « System.Node[i + 1])
endf;
System := System + (System.Node[n] « System.Node[1])
В цикле к системе добавляются ребра м
Лекция 7. Распределенное имитационное моделирование
В одной из лекций шла речь о методах исследования распределенных систем. В качестве одного из методов рассматривался метод имитационного моделирования.
Если предположить, что предметом исс
Причины для перехода к распределенному моделированию
Использование распределенного моделирования объясняется:
- возможностью использования вычислительных ресурсов нескольких процессоров (компьютеров) для выполнения имитационного эксперимента
Два направления в развитии распределенных систем моделирования
Развитие распределенного имитационного моделирования идет по двум направлениям. Это монолитные системы моделирования и готовые системы моделирования, объединенные с помощью специального программног
Физическое время
Рассмотрим пример: пусть на нескольких компьютерах (клиентах) располагаются директории с файлами – списки товаров, на сервере – сводная директория, которая периодически обновляется. Приложение, рас
Управление временем в распределенном моделировании
Управление временем в распределённом моделировании должно обеспечивать выполнение событий в правильном хронологическом порядке. Более того, на алгоритмы синхронизации возлагается обязанность коррек
Парадоксы времени
Алгоритм управления временем должен следить за тем, чтобы события выполнялись в хронологическом порядке. Эта задача не является тривиальной. Действительно, логический процесс заранее не может знать
Консервативное управление временем
Первые алгоритмы синхронизации использовали консервативный подход. Принципиальная задача консервативного протокола – определить время, когда обработка очередного события из списка необработанных со
Алгоритм с нулевыми сообщениями
Первыми консервативными алгоритмами считаются алгоритмы, разработанные Bryant, Chandy, Misra.
Алгоритм предполагает:
- Топология процессов, которые посылают сообщения друг другу,
Оптимистическое управление временем
В отличие от консервативных алгоритмов, не допускающих нарушения ограничения локальной каузальности, оптимистические методы не следят за этим ограничением. Однако этот подход гарантирует выявление
Лекция 9. Балансировка нагрузки в распределенных системах
Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка
Статическая и динамическая балансировки
Следует различать статическую и динамическую балансировки.
Статическая балансировка выполняется до начала выполнения распределенн
Оценка загрузки
На этом этапе осуществляется приблизительная оценка загрузки каждого процессора. Полученная информация о загрузке используется в качестве базы данных для процесса балансировки, во-первых, для опред
Инициализация балансировки загрузки
Слишком частое выполнение балансировки загрузки может привести к тому, что выполнение имитационной модели только замедлится. Затраты на саму балансировку могут превзойти возможную выгоду от ее пров
Балансировка загрузки распределенной имитационной модели
В одной из предыдущих лекций мы рассматривали вопросы реализации распределенных систем имитации. Балансировку необходимо выполнять и при проведении распределённого моделирования. Первоначальная цел
Динамическая балансировка и перенос нагрузки
Алгоритм динамической балансировки использует характеристики состояния системы и принимает решение о том, с какого компьютера и на какой следует перенести работу во время моделирования. Это подход
RCL – cтратегия переноса нагрузки
Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communica
Действия первого уровня
В начале действий по переносу нагрузки информации все компьютеры прекращают свою работу, и каждый получает информацию о локальной нагрузке в текущий момент времени. Информация о локальной нагрузке
Действия второго уровня
Действия второго уровня охватывают все рабочие станции распределённой системы. Конкретной количество нагрузки посылается с одной рабочей станции на другую. Основные действия связаны с выбором нагру
Реализация
Стратегия динамического переноса нагрузки RCL была разработана для SPEEDES с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют н
Распределенные веб-сервисы
В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует в
Использование мобильных агентов
Наряду с традиционными подходами (парадигма обмена сообщениями) рассмотрим другой – мультиагентный подход.
Напомним, что мобильный агент – это программный компонент, который может автомати
Мультиагентный подход к балансировке
Мобильные агенты используются для поддержки балансировки загрузки в параллельных и распределенных вычислениях. Рассмотрим кратко несколько проектов.
Проект Traveller
Проект
Агенты и МАС
Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.
В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, по
Лекция 11. Распределенное хранение информации
Источники информации часто, как говорилось ранее, находятся в различных точках физического пространства. Если информация из этих источников не используется сразу, а потребность в ней возникает лишь
Фрагментация
Реляционные базы данных хранят отношения – таблицы, состоящие из строк и столбцов. Строка отношения называется кортежем и представляет собой запись (record в смысле языка программирования, н
Репликация
Под репликацией понимается создание копий некоторых фрагментов отношений и одновременное хранение нескольких копий на разных сайтах (в разных локальных БД). Репликация используется для того,
Схемы владения данными в распределенной БД
Выше, рассматривая распределенную базу данных, состоящую из локальных сайтов, мы неявно предполагали, что для каждой единицы данных существует вполне определенный единственный сайт, владеющий этими
Лекция 12. Волновые алгоритмы распространения информации
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей систем
Алгоритм для кольцевой архитектуры
Если сайты распределенной системы соединены однонаправленными каналами связи так, что образуют граф – ориентированный цикл, применим следующий волновой алгоритм.
Суть его в следующем. Один
Алгоритм для структуры – дерева
Предположим, что соединение сайтов распределенной системы каналами образует граф – неориентированное дерево. Из теории графов известны следующие факты для деревьев:
1) дерево – связный аци
Алгоритм голосования
Алгоритм голосования применяется для распределенных систем, имеющих структуры полных графов. В этом случае инициатором может быть любой сайт. Для графа – звезды его тоже можно использовать, но иниц
Фазовый алгоритм
Фазовый алгоритм является децентрализованным алгоритмом для произвольных ориентированных графов. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встреч
Алгоритм Финна
Алгоритм Финна – еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает
Распространение информации с обратной связью
Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задач
Синхронизация
Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q
Вычисление нижней грани
Продемонстрируем применение волновых алгоритмов для вычисления функций, значения которых зависят от входов процесса на каждом сайте. В качестве представителей таких функций будут рассмотрены алгори
Лекция 13. Алгоритмы обхода сайтов
Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.
1) В каждом вычислении один сайт-инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщен
Алгоритм обхода тора
Граф вида «тор» представляет собой решетку с дополнительными ребрами, соединяющими вершины из верхнего ряда («строки») решетки с вершинами из нижнего ряда, а также с ребрами, соединяющими вершины и
Алгоритм обхода гиперкуба
В теории графов известен класс графов Qn , называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2
Алгоритм Тарри
Алгоритм обхода для произвольных связных графов был дан Тарри. Алгоритм основан на следующих двух правилах.
1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
Лекция 14. Алгоритмы выбора сайтов
Во многих распределенных системах один из сайтов играет роль координатора при выполнении распределенного алгоритма. Иногда координатором является сайт, который инициировал выполнение алгоритма. Но
Алгоритм смещения
Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) сво
Выбор с помощью алгоритма для деревьев
Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концев
Алгоритмы выбора для кольцевых архитектур
В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с на
Лекция 15. Поиск в пиринговых системах
Пиринговые системы (peer-to-peer, P2P) – это такие компьютерные сети, в которых не используется классическая схема клиент-сервер, разделяющая множество всех узлов на два подмножества – серверов и к
Лекция 16. Тенденции в области распределенных систем
В одной из своих статей в 2001 году Дж. Бэкус отметил, что компьютерная революция испытала три волны. Первая волна началась с коммерциализацией кремниевых чипов и продолжалась 10-15 лет. Вторая вол
Архитектура Грид
Следуя традиционному построению распределенных систем, можно описать архитектуру Грид, состоящую из четырех слоев:
1. Пользовательские интерфейсы, приложения и среда решения задач (problem
Мобильный компьютинг
Самостоятельным направлением является мобильный компьютинг. В его основе (в дополнение к распределенному компьютингу) лежат:
1) сети, обеспечивающие подключение к ним
Тотальный компьютинг
Английский термин pervasive computing обозначает проникающий, распространяющийся повсюду, всеобъемлющий, глубоко влияющий (компьютинг). Тотальный компьютинг ставит во главу угла конечного пользоват
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов