Сети внутри сетей

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

Мотивация

Сети внутри сетей хорошо подходят для моделирования распределенных систем с учетом конкретных аспектов

иерархия,
мобильность
инкапсуляция.

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

История

Исходя из необходимости практических приложений, к середине девяностых годов были созданы различные формализмы, соответствующие описанию «сетей внутри сетей». Ломазова и Шнобелен в списке ^[1]некоторые из этих подходов, а именно Сибертен-Блан, ^[2] житель, ^[3] Мольдт и Винберг ^[4] как расширение цветных сетей Петри за пределы объектных сетей Валка. ^[5]Самое раннее использование таких иерархических сетевых моделей появилось Рюдигером Вальком в Валке и Йессене. ^[6] где так называемые сети потока задач ^[7] вводятся для моделирования систем задач в операционных системах. В этих моделях задачи моделируются сетью Петри, которая представляет приоритет задач и состояние их выполнения.

Семантика

Наиболее важные различия в семантике дает исполнение сетевых токенов. С одной стороны, сетевые токены могут быть ссылками на сетевые элементы, ^[8] этот случай называется «эталонной семантикой». Этот вид семантики отличается от семантики значений , где сетевые объекты могут существовать в разных местах и разных внутренних состояниях. В семантике значений можно создавать разные копии для моделирования одновременного выполнения. Соответствующее объединение такого разделения может быть определено по-разному, например, с помощью «семантики распределенных токенов». ^[9] или «семантика исторического процесса». ^[10] В связи с мобильными компьютерами важное значение имеют гибридные версии семантики ссылки и значения. ^[11] В семантике распределенных токенов важное исчисление инвариантов мест для сетей Петри остается в силе. ^[12]

Коммуникация

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

Рисунок 1: Вложенная сеть Петри, содержащая каналы через надписи

На рисунке 1 показана сеть Петри, содержащая токен сети Петри на месте «а». Сеть токенов может перемещаться из места «a» в место «b» и обратно, запуская переходы внешней сети. Надписи каналов на переходах ведут себя как вызов метода , что приводит к синхронному срабатыванию вызывающего перехода во внешней сети (например, помеченного x:forth()) и вызываемого перехода (например, помеченного :forth()). в сети токенов. Переменная «x» у стрелки привязана к сети токенов в месте, связанном с этой стрелкой. В скобках могут содержаться передаваемые параметры. Этот пример настолько прост, что семантика ссылки и значения совпадают.

Алгоритмы и ограниченные формализмы

Стандартные свойства сети Петри, такие как достижимость , ограниченность и живучесть, показывают неоднозначную картину. Бумага ^[13] Кёлер-Бюссмайер дает обзор результатов разрешимости систем элементарных объектов.Чтобы уменьшить сложность формализма, были определены подклассы путем ограничения структуры сетей Петри, например, конечными автоматами. Такие ограничения по-прежнему позволяют проводить сложное моделирование распределенных и мобильных систем, но имеют полиномиальную сложность проверки моделей . ^[14]

Инструменты

CO-OPN https://smv.unige.ch//research-projects/co-opn (на основе алгебраических сетей высокого уровня)
RENEW http://www.renew.de (бесплатная разработка модели проверки эталонных сетей с помощью JAVA-интеграции) ^[15]

Ссылки

^ Ирина А. Ломазова, Филипп Шнобелен: Некоторые результаты разрешимости для вложенных сетей Петри , Springer LNCS 1755, 2000, стр. 208-220
^ Кристоф Сибертен-Блан: Кооперативные сети , Springer LNCS 815, 1994, стр. 471-490.
^ Чарльз Лакос: От цветных сетей Петри к объектным сетям Петри , Springer LNCS 935, 1995, стр. 278-297.
^ Дэниел Молдт и Фрэнк Винберг: Мультиагентные системы на основе цветных сетей Петри , Springer LNCS 1248, 1997, стр. 82-101.
^ Рюдигер Валк : Сети Петри как объекты-символы , Springer LNCS 1420, 1998, стр. 1-24.
^ Эйке Йессен, Рюдигер Валк : Вычислительные системы: основы моделирования , Springer, 1987.
^ Рюдигер Валк : Моделирование параллелизма с помощью систем задач/потоков EN . Материалы 3-го семинара по параллелизму и композиционности, GMD-Studien Nr. 191, Бонн, 1991 г.
^ Олаф Куммер: Справочные сети , диссертация, Гамбургский университет, Logos Verlag Berlin, 2002 г.
^ Михаэль Кёлер, Хайко Рёльке: Свойства объектных сетей Петри . Springer LNCS 3099, 2004, стр. 278–297.
^ Рюдигер Валк : Объектные сети Петри , Springer LNCS 3098, 2004, стр. 819-848.
^ Берндт Фарвер, Михаэль Кёлер: Моделирование глобальных и локальных пространств имен для мобильных агентов с использованием объектных сетей , Fundamenta Informaticae, Vol. 72, № 1, стр. 109-122, 2006 г.
^ Михаэль Келер-Бусмайер, Дэниел Молдт: Анализ мобильных агентов с использованием инвариантов объектных сетей . Электронные коммуникации EASST: специальный выпуск по формальному моделированию адаптивных и мобильных процессов, 12, 2009. http://www.easst.org/eceasst/
^ Михаэль Кёлер-Бусмайер: Обзор результатов разрешимости для систем элементарных объектов : Fundamenta Informaticae, Vol. 130, № 1, стр. 99-123, 2014 г.
^ Франк Хейтманн, Михаэль Кёлер-Бусмайер: P- и t-системы в формализме сетей внутри сетей : Springer LNCS 7347, 2012, стр. 368-387
^ Олаф Куммер, Франк Винберг, Михаэль Дювиньо, Йорн Шумахер, Михаэль Кёлер, Даниэль Молдт, Хайко Рёлке, Рюдигер Вальк ,: Расширяемый редактор и механизм моделирования для сетей Петри: Обновление : Springer LNCS 3099, 2004, стр. 484-493

[1] Ирина А. Ломазова, Филипп Шнобелен: Некоторые результаты разрешимости для вложенных сетей Петри , Springer LNCS 1755, 2000, стр. 208-220

[2] Кристоф Сибертен-Блан: Кооперативные сети , Springer LNCS 815, 1994, стр. 471-490.

[3] Чарльз Лакос: От цветных сетей Петри к объектным сетям Петри , Springer LNCS 935, 1995, стр. 278-297.

[4] Дэниел Молдт и Фрэнк Винберг: Мультиагентные системы на основе цветных сетей Петри , Springer LNCS 1248, 1997, стр. 82-101.

[5] Рюдигер Валк : Сети Петри как объекты-символы , Springer LNCS 1420, 1998, стр. 1-24.

[6] Эйке Йессен, Рюдигер Валк : Вычислительные системы: основы моделирования , Springer, 1987.

[7] Рюдигер Валк : Моделирование параллелизма с помощью систем задач/потоков EN . Материалы 3-го семинара по параллелизму и композиционности, GMD-Studien Nr. 191, Бонн, 1991 г.

[8] Олаф Куммер: Справочные сети , диссертация, Гамбургский университет, Logos Verlag Berlin, 2002 г.

[9] Михаэль Кёлер, Хайко Рёльке: Свойства объектных сетей Петри . Springer LNCS 3099, 2004, стр. 278–297.

[10] Рюдигер Валк : Объектные сети Петри , Springer LNCS 3098, 2004, стр. 819-848.

[11] Берндт Фарвер, Михаэль Кёлер: Моделирование глобальных и локальных пространств имен для мобильных агентов с использованием объектных сетей , Fundamenta Informaticae, Vol. 72, № 1, стр. 109-122, 2006 г.

[12] Михаэль Келер-Бусмайер, Дэниел Молдт: Анализ мобильных агентов с использованием инвариантов объектных сетей . Электронные коммуникации EASST: специальный выпуск по формальному моделированию адаптивных и мобильных процессов, 12, 2009. http://www.easst.org/eceasst/

[13] Михаэль Кёлер-Бусмайер: Обзор результатов разрешимости для систем элементарных объектов : Fundamenta Informaticae, Vol. 130, № 1, стр. 99-123, 2014 г.

[14] Франк Хейтманн, Михаэль Кёлер-Бусмайер: P- и t-системы в формализме сетей внутри сетей : Springer LNCS 7347, 2012, стр. 368-387

[15] Олаф Куммер, Франк Винберг, Михаэль Дювиньо, Йорн Шумахер, Михаэль Кёлер, Даниэль Молдт, Хайко Рёлке, Рюдигер Вальк ,: Расширяемый редактор и механизм моделирования для сетей Петри: Обновление : Springer LNCS 3099, 2004, стр. 484-493

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]