рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Агенты и МАС

Агенты и МАС - Лекция, раздел Философия, Распределенные системы и алгоритмы Развитие Интеллектуальных Агентов И Мас Очень Популярны В Среде Исследователе...

Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.

В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, пользователей, оборудования, для поддержки принятия решений, управления знаниями.

Существенными в понятии агента являются понятия делегирования и автономии. Это означает ограниченное непосредственное управление и значительный плюрализм (разнообразие) в системах, в которых работают сразу несколько агентов.

Исследования в области МАС отличаются от исследований в области распределенного ИИ. В ИИ функционирование системы распределено по множеству вершин для совместного решения проблемы. В МАС агенты имеют свои собственные цели, которые могут вступать в противоречие с целями других агентов. Тем не менее, группа логически децентрализованных агентов решает работать вместе для достижения общей цели. Это возможно сделать различными путями. Один из путей – разделить задачу на части между агентами. Другой – позволить каждому из агентов решать исходную задачу своим способом. В случае отыскания приближенных решений затем может быть выбрано наилучшее. Либо может применяться процедура голосования агентов за то или иное решение.

 

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

Парадигма мультиагентного проектирования и реализации систем состоит в том, что программные агенты для достижения цели (выполнения некоторой работы) перемещаются с одного сервера на другой. Агенты выполняют свою работу локально на том сервере, на котором они в данный момент находятся. Обмен сообщениями (между серверами) по сети агенты, как правило, не используют. Т.Комийя, Т.Енокидо и М.Такидзава рассмотрели следующую модель.

Пусть в системе имеются серверы Serv1 , Serv2 , …, Servm , соединенные каналами связи, и агенты A1 , A2 , …, An , пользующиеся услугами этих серверов. Агенты автономно выполняются на серверах. Агент самостоятельно инициализируется на сервере: процедура и данные агента записываются в память сервера объектов, если на этом сервере достаточно ресурсов для работы агента. Говорят, что агент Ak размещается (land – «приземляется») на сервере Servi и этот сервер становится для агента текущим.

Для размещения на сервере важны два условия:

1) достаточность ресурсов сервера таких, как объем доступной памяти и вычислительная мощность компьютера (с учетом того, что часть памяти и вычислительных мощностей сервера в этот момент времени может быть занята выполнением других задач);

2) отсутствие на сервере в этот момент времени других агентов, конфликтующих с агентом Ak . Конфликт может быть вызван различными причинами, например, тем, что два агента будут работать с одним и тем же объектом в режиме изменения этого объекта (в режиме записи).

После выполнения работы с объектами на сервере Servi агент Ak может переместиться на сервер Servj для выполнения работы с находящимися там объектами. Перемещения агента зависят от того, какая перед ним стоит цель и на каких серверах находятся нужные ему объекты.

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

1) создание агента (по некоторому описанию). Создание происходит всегда на некотором сервере. Этот сервер называют «домашним» для созданного агента;

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

3) расслоение агента A. Агент A разделяется на несколько агентов A1 , A2 , …, Al , начинающих самостоятельное существование в системе. Это разделение может коснуться программ и данных агента, а также его целей и задач;

4) слияние агентов A1 , A2 , …, Al . Вместо нескольких агентов, прекращающих самостоятельное существование, возникает один агент, обобщающий процедуры и данные составляющих агентов, а также их цели и задачи;

5) уничтожение агента A. Агент A перестает существовать в системе.

 

Рис. 19. Расслоение и слияние агентов

 

Модель агентов важна, например, для обработки транзакций. Как известно, транзакция – это последовательность взаимосвязанных действий, которые должны быть выполнены на нескольких серверах распределенной системы.

Транзакция должна удовлетворять четырем условиям (их называют ACID):

1) атомарности (atomicity). Работа, которую должна выполнить транзакция, не может быть сделана «наполовину». Либо работа выполнена полностью, либо она не выполнена совсем. Это не означает, что транзакция не может состоять из субтранзакций. Если из всех транзакций, которые должны были выполниться, не выполнится хотя бы одна, то считается невыполненной вся транзакция. Должен быть произведен откат (roll back) – последовательность действий, возвращающая сервер (или базу данных) в исходное (до начала выполнения транзакции) состояние;

2) согласованности (consistency). Транзакция должна переводить базу данных (или сервер) из одного согласованного состояния в другое согласованное состояние;

3) изолированности (isolation). Транзакции изолированы друг от друга, кроме случая, когда одна транзакция является субтранзакцией другой. Транзакции либо выполняются последовательно, либо (что вполне возможно в распределенных системах) пересекаются по времени, но не пересекаются по данным. Иными словами, никакие данные, которые читает или изменяет транзакция T1 , не должны быть доступны для изменения или чтения транзакцией T2 до тех пор, пока T1 не завершилась.

4) продолжительности (durability). Результаты зафиксированной (завершенной) транзакции должны сохраняться до тех пор, пока их не заменит новая транзакция. Здесь подразумевается, что попытка пользователя изменить данные приводит не к немедленному их изменению, а к инициированию соответствующей транзакции.

 

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

 

Агенты могут помогать и в решении проблем работы с документами для мобильных пользователей.

Мобильные пользователи обычно находятся в условиях относительно низкой полосы пропускания каналов связи и не слишком плотной (с точки зрения количества связей между узлами) сети. Это затрудняет, в частности, работу с объемными Web-документами, передавать которые целиком на терминал пользователя неэффективно.

Решением может быть (С.Яу, Х.Леонг, А.Си) «нарезка» документа на части и передача непосредственно пользователю только той части, с которой он работает в данный короткий отрезок времени. Таким образом, будет решена проблема недостаточной пропускной способности канала связи.

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

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

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

 

 

Рис. 20. Перемещение мобильного пользователя и мобильного агента

 

Взаимодействующие агенты могут быть частью системы искусственного интеллекта, участвовать в распределенном решении задач и распределенном планировании.

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

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

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

Примером такой задачи является построение сети датчиков интенсивности автомобильного движения на большом пространстве, например, города или района города, и организация на основе этой сети управления движением.

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

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

Поэтому для нахождения оптимального решения задачи требуется мониторинг реальных очередей в различных точках города и соответствующее динамическое регулирование работы светофоров. Т.е. результаты решения задачи также требуются в различных точках распределенной системы.

В мультиагентной системе каждый агент может/должен решать проблему распределения своих задач между другими агентами. Эта проблема возникает, если у агента A есть несколько задач, требующих решения, и он не справляется со всеми (из-за недостатка ресурсов). Тогда он может попытаться передать часть своих задач другим агентам Ai , у которых мало или совсем нет задач. Решение проблемы распределения состоит из четырех фаз:

1) декомпозиция агентом A задачи на подзадачи;

2) назначение подзадач агентам Ai ;

3) решение подзадач агентами;

4) синтез общего результата из частных результатов.

 

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

При назначении подзадач должны быть выбраны подходящие (по тем или иным критериям) агенты.

Решение подзадачи агентом Ai , которому она передана, может состоять в полностью самостоятельном решении. Но этот агент также может решить проблему распределения, т.е. в свою очередь, произвести декомпозицию подзадачи и попросить помощи у других агентов. Этот процесс разбиения задачи на подзадачи может состоять из нескольких уровней.

Синтез результата производится тем агентом A, который инициировал распределение задачи. Он собирает частные результаты своих «помощников» Ai и формирует общий результат. Процесс формирования зависит от того, как исходная задача была разделена на подзадачи. Если декомпозиция, как отмечено выше, была многоуровневой, то и синтез результата будет многоуровневым.

Важно заметить, что декомпозиция задачи и синтез результата – проблемы не тривиальные. Вспомним задачу организации сети управления движением автомобильного транспорта. Агент, ответственный за решение этой задачи в масштабах города, скорее всего, проведет декомпозицию задачи на подзадачи по районам города и назначит подзадачи соответствующим территориальным агентам. Те, в свою очередь, произведут разделение на подзадачи для микрорайонов и т.д.

Решение агентами каждой локальной подзадачи будет производиться на основе некоторых предположений о потоках автомобильного транспорта на «входах» в соответствующую территорию. С учетом предположений могут быть найдены оптимальные локальные решения Ri .

При синтезе общего решения R из локальных решений Ri должна быть произведена «сшивка» решений Ri по границам территорий. И вот здесь может быть выявлена несогласованность сделанных ранее агентами Ai локальных предположений о потоках на границах. Дело в том, что в результате локального решения для территории k будут, в частности, получены и описания «выходных» потоков транспорта с территории k. Если территория k смежна с территорией l и поток из k направляется в l, то «вычисленный» выходной поток k может не совпасть с «предполагаемым» входным потоком l.

Более того, имеется и встречный поток из территории l в территорию k. Кроме того, территориям k и l смежны еще и другие территории. Так что рассогласования могут быть весьма разнообразны.

В результате этого решение R не может быть получено простым объединением решений Ri .

В этом случае возможны следующие стратегии: возврат с пересмотром локальных решений Ri на основе новых предположений о потоках на границах; повторная декомпозиция задачи и повторение всего процесса решения.

Возврат с пересмотром локальных решений порождает итерационный процесс, состоящий из следующих шагов:

1) изменение предположений о «входных» потоках территорий с учетом вычисленных «выходных» потоков;

2) пересчет локальных решений Ri ;

3) сравнение новых выходных потоков предположениями о входных потоках. При совпадении или небольших отклонениях – прекращение процесса. При больших отклонениях – возврат к пункту 1.

Если итерационный процесс завершился в пункте 3 полными совпадениями, то итоговое решение R может быть получено простым объединением решений Ri .

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

Если процесс не сходится, то требуется повторная декомпозиция задачи. Например, исходя из иного территориального разбиения.

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

Если агенты закреплены за районами, то при новой декомпозиции задачи требуется обеспечить сотрудничество агентов и при решении локальных задач.

Описанные проблемы поиска решения имеют в области искусственного интеллекта наименование «удовлетворение распределенных ограничений» (Distributed Constraint Satisfaction).


– Конец работы –

Эта тема принадлежит разделу:

Распределенные системы и алгоритмы

Распределенные системы и алгоритмы... Курс лекций...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Агенты и МАС

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Сосредоточенные и распределенные системы
Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функц

Тандемы распределенных систем
Рассмотрим две системы, S1 и S2 . Первая система функционирует для достижения некоторой цели G1 . При этом в любой момент времени имеется некот

Лекция 2. Распределенные задачи и алгоритмы
С системой S связана цель G, ради которой система функционирует. Эта цель ставится самой системой (если система – активная), или поставлена извне. Для достижения цели в системе должна

Лекция 3. Надежность и безопасность распределенных систем
Сравним сосредоточенную и распределенную системы с точки зрения надежности и безопасности. Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во в

Структура информационного пространства
Хотя термин «информационное пространство» является лишь метафорой, обратимся к проблеме анализа структуры этого пространства. Математики привыкли связывать с любым пространством некоторую структуру

Структура региональной системы образования и предпосылки создания РРИСО
Возникает естественный вопрос: почему выбран именно такой масштаб? Почему – региональная система? Дело в том, что это в определенном смысле минимаксный вариант. Уровень отдельного учебного заведени

Структуры РРИСО
Структуру РРИСО можно рассматривать с нескольких точек зрения. Прежде всего, это наиболее очевидная – географически ориентированная структура. Многие (но не все) элементы информационной системы при

Подсистемы. Взаимоотношения структур
Каждая из структур РРИСО строится по своим законам, поэтому, не стоит ожидать изоморфизма между парами структур. Идеально, если одни структуры являются надстройками над другими, использующими механ

Условная корпоративность
Хотя мы называем РРИСО корпоративной системой в силу того, что имеется определенный административный «каркас» на множестве ее пользователей, и у нее довольно четкая целевая направленность, тем не м

Неоднородность
Неоднородность – одна из важнейших характеристик РРИСО. Если многие корпоративные системы являются однородными, или неоднородность имеет место в одном - двух аспектах построения системы, то неоднор

Интегрируемость
Это одно из ключевых свойств в характеристике РРИСО. Это и «врожденное» и приобретаемое свойство. Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы дан

Лекция 6. Моделирование распределенных систем. Язык Triad
Исследование распределенных систем – трудная задача. Прежде всего, распределенная система должна быть описана, т.е. должна быть построена модель системы. Для этой цели можно использовать различные

Model System2 (k, m, n: integer) def
System2 := star(Server, Serv[a..c]) + star(Serv[a], Node[1..k]) + star(Serv[b], Node[k+1..m]) + star(Serv[c], Node[m+1..n]) enddef.

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 с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют н

Распределенные веб-сервисы
В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует в

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

Различные подходы к балансировке, основанные на технологии клиент-сервер
Рассмотрим различные подходы к балансировке нагрузки. Выделяют следующие категории: - клиентские; - основанные на DNS; - диспетчерские; - серверные.

Мультиагентный подход к балансировке
Мобильные агенты используются для поддержки балансировки загрузки в параллельных и распределенных вычислениях. Рассмотрим кратко несколько проектов. Проект Traveller Проект

Лекция 10. Распределенные интеллектуальные системы на основе агентов
Современные системы искусственного интеллекта часто строятся как системы взаимодействующих и сотрудничающих агентов. Одним из расширений понятия программы стало понятие агента. Оно появило

Лекция 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 обозначает проникающий, распространяющийся повсюду, всеобъемлющий, глубоко влияющий (компьютинг). Тотальный компьютинг ставит во главу угла конечного пользоват

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги