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

17 февраля 2017

Павел Бойко, заместитель директора по направлению разработки системного ПО, подготовил новый материал, посвященный проработке мультиагентного взаимодействия, и поделился новыми исследовательскими задачами, которые в настоящее время решают эксперты АстроСофт.

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

Становление мультиагентных систем (МАС) как отдельного научного направления пришлось на 1980-е, а уже в середине 1990-х это направление получило широкое признание [1, с. 13]. В течение последующих пятнадцати лет возрастающий объем исследований в данной области привел к необходимости систематизации накопленных знаний и появлению первых тематических монографий как в России [2], так и за рубежом [1, 3–4].

Уже в начале 2000-х агентно-ориентированный подход широко применялся для распределённого решения сложных задач в имитационном моделировании, организации работы коллективов роботов и других областях [2, с. 15]. Сегодня мультиагентные технологии проникают даже в традиционно консервативные области, которые задают высокий уровень безопасности, например — энергетика [5], а вопросы организации коллективов роботов становятся все более актуальными как в гражданском, так и военном секторах [6], выделяя следующие задачи: контроль периметра, обеспечение связи, ликвидация последствий стихийных бедствий и др.

Выделившись из классического искусственного интеллекта, централизованному подходу решения задач МАС противопоставили децентрализованный, предполагая, что отдельный агент может обладать лишь частичными знаниями, а для решения задачи потребуется взаимодействие группы агентов, что обусловило концептуальную новизну решений на основе МАС [2, с. 15]. Стимулом к дальнейшему развитию направления стали предполагаемые повышенные надежность, гибкость и масштабируемость таких систем [3, с. 8] — качества, которые существенно проще обеспечить в децентрализованных многопроцессорных системах, чем в классических [7, с. 12].

1. Мультиагентная (распределённая) система

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

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

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

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

2. Свойства и следствия мультиагентной системы

В теории МАС известна концепция «доски объявлений»[8], описывающая систему взаимодействия нескольких «источников знаний» с некоторой общей структурой данных. Концепция является хорошим приближением к нашей задаче и может быть задействована, однако, так как мы говорим о децентрализованной системе, расширим исходную концепцию, заменив центральное хранилище распределенным. В обновленном виде концепцию можно назвать "виртуальная доска объявлений". Данная концепция также известна в теории многопроцессорных вычислительных систем под названием distributed shared memory (DSM) [9].

Вопросы, которые необходимо рассмотреть при создании подобных систем описаны, например, в [10]. Ключевой вопрос при этом — модель целостности (consistency), обеспечивающая свойство ее когерентности. Система называется когерентной, если значение, возвращаемое операцией чтения, всегда совпадает со значением, ранее записанным ближайшей по времени операцией по тому же адресу [11]. Хотя проблема когерентности возникла еще во времена появления процессорного кэша, она представила собой основную сложность в создании DSM-систем, так как ее DSM-вариант имеет множество особенностей [11].

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

В решении задачи обеспечения когерентности памяти выделяют две стратегии или модели: invalidation и write-broadcast [11]. Первая допускает лишь одного владельца для каждого распределенного объекта, за счет чего сокращает накладные расходы на пересылку изменившихся данных; вторая требует обновления данных во всех узлах-копиях после каждой операции записи. Write-broadcast-подход рассматривается реже, так как необходимые для организации когерентности накладные расходы при нем особенно велики. Однако он хорошо применим в нашей ситуации, так как требует максимально быстрого распространения изменившейся информации по всем узлам в системе, не допуская их уникальности. В соответствии с классификацией, принятой в [9], можно обозначить необходимую нам систему как replication (допускающий множество копий одних и тех же данных), multiple reader/single writer (MRSW, допускающий параллельное чтение одних и тех же данных множеством узлов, но разрешающий запись лишь одному узлу в один момент времени) software (не зависящий от аппаратных особенностей и реализованный программно) алгоритм.

В общем виде, работа алгоритма, реализованного на уровне операционной системы (ОС), может выглядеть согласно описанию в Таблице 1.

Таблица 1. Алгоритм обеспечения когерентности памяти

Операция над распределенным объектом d	Список инструкций операции
Чтение	Пока (d заблокирован) – ожидать Вернуть результат чтения
Запись	Запросить разрешение на захват d у всех агентов системы Если (получен отказ) Отменить захват; Ожидать случайный промежуток времени; Перейти к п.1 Произвести запись d Разослать информацию об освобождении d и новое значение d
Выдача разрешения на захват	Пока (выполняются локальные операции с d) – ожидать Заблокировать d Выдать разрешение
Обработчик сообщения об освобождении	Записать новое значение d Снять блокировку d

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

1. Потенциально высокий трафик на обеспечение когерентности, особенно в случае частых обращений к памяти и большого числа агентов. Возможное решение — фиксация частоты дискретизации операций, либо ее автоматическая подстройка.
2. Возникновение вечной блокировки в случае отсоединения агента сразу после захвата им объекта. Возможное решение — ввод таймаутов на соответствующие операции.
3. Потеря когерентности в случае отсоединения агента в момент рассылки оповещений об освобождении объекта — часть агентов при этом получит информацию о его новом значении, другая же часть разблокирует объект по таймауту, новое значение не получив. Данную проблему можно свести к известной из криптографии "Задаче о византийских генералах", постановка и решения которой рассматриваются, например, в [12].

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

Список литературы

1. Wooldridge M. An Introduction to MultiAgent Systems Second Edition. — Wiley, 2009. — 484 p. — ISBN: 0470519460.
2. Тарасов В. Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. — М.: Эдиториал УРСС, 2002. — 352 с. — ISBN: 5836003300.
3. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence / Ed. by G. Weiss. — The MIT Press, 1999. — 643 p. — ISBN: 0262232030.
4. Shoham Y., LeytonBrown K. Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations. — Cambridge University Press, 2008. — 504 p. — ISBN: 0521899435.
5. Liang H., Abdrabou A., Choi B. J. et al. Multiagent coordination in microgrids via wireless networks // IEEE Wireless Communications. — 2012. — Vol. 19, no. 3. — P. 14–22.
6. Breitenmoser A., Schwager M., Metzger J.-C. et al. Voronoi coverage of non-convex environments with a group of networked robots // In processing of the IEEE International Conference on Robotics and Automation (ICRA). — Anchorage, Alaska, USA: 2010. — P. 4982–4989.
7. Андреев А. М. Многопроцессорные вычислительные системы: теоретический анализ, математические модели и применение: Учебное пособие / А.М. Андреев, Г.П. Можаров, В.В. Сюзев. — М.: МГТУ им. Баумана, 2011. — 332 c.
8. Engelmore R., Morgan T. Blackboard systems: edited by Robert Engelmore, Tony Morgan. — Addison Wesley Publishing Company, 1988.
9. Protic J., Tomasevic M., Milutinovic V. Distributed shared memory: concepts and systems // IEEE Parallel Distributed Technology: Systems Applications. — 1996. — Summer. — Vol. 4, no. 2. — P. 63–71.
10. Vasava H. D., Rathod J. M. A Survey of Software based Distributed Shared Memory (DSM) Implementation Methodologies for Multiprocessor Environ ments // International Journal of Innovative Research in Science, Engineering and Technology. — 2013. — Vol. 2, no. 7.
11. Li K., Hudak P. Memory Coherence in Shared Virtual Memory Systems // ACM Trans. Comput. Syst. — 1989. —November. — Vol. 7, no. 4. — P. 321–359.
12. Генинсон Б. A., Панкова Л. А., Трахтенгерц Э. А. Отказоустойчивые методы обеспечения взаимной информационной согласованности в распределенных вычислительных системах. — Автомат. и телемех. — 1989. — № 5. — С. 3–18.

Теги: МАС, мультиагентные технологии, когерентность памяти, replication, multiple reader/single writer, software алгоритм