Модели времени для сложных распределенных дискретных систем

  • Виталий [Vitaliy] Павлович [P.] Кутепов [Kutepov]
  • Вадим [Vadim] Николаевич [N.] Фальк [Falk]
Ключевые слова: распределенные многокомпонентные дискретные системы, динамические системы, формализация времени в системах, частично-упорядоченные множества, универсумы времени, средства конструктивного задания множеств универсумов времени, Т-сети, контекстно-свободные Т-сетевые языки и грамматики

Аннотация

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

Сведения об авторах

Виталий [Vitaliy] Павлович [P.] Кутепов [Kutepov]

доктор технических наук, профессор кафедры прикладной математики НИУ «МЭИ»

Вадим [Vadim] Николаевич [N.] Фальк [Falk]

доктор технических наук, профессор кафедры прикладной математики НИУ «МЭИ»,
e-mail: falkvn@yandex.ru

Литература

1. Ковалев С.П. Архитектура времени в распределенных информационных системах // Вычислительные технологии. 2002. Т. 7. № 6. С. 38—53.
2. Winkowski J. An Algebraic Framework for Concurrent Systems // Rep. No. 1023. Institute of the Polish academy of science, 2012.
3. Prakash R., Singhal M. Dependency Sequences and Hierarchical Clocks: Efficient Alternativesto Vector Clocks for Mobile Computing Systems // ACM J. Wireless Network. 1997. No. 3. Pp. 349—360.
4. Lamport L. Time, Сlock and the Ordering of Events in Distributed Systems // Communications of ASM. 1978. V. 21 (7). Pp. 358—365.
5. Fidge J. Timestamps in Message-passing Systems that Preserve the Partial Ordering // Proc. XI Australian Computer Sci. Conf. 1988. V. 10. No. 1. Pp. 56—66.
6. Middelburg С.A. Revisiting Timing in Process Algebra // J. Logic and Algebraic Programming. 2003. V. 54. Pp. 109—127.
7. Аль Джабри Х.Ш., Родионов В.И. Граф ациклических орграфов // Вестник Удмуртского ун-та. Серия «Математика. Механика. Компьютерные науки». 2015. Т. 25. № 4. С. 441—452.
8. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Известия РАН. Серия
«Техническая кибернетика». 1994. № 5. С. 114—123.
9. Фальк В.Н. Теория направленных отношений и ее приложения: автореф. дисс. … докт. техн. наук. М.: МЭИ, 2001.
10. Фальк В.Н. Об одном подходе к эффективной нумерации рекурсивных множеств конструктивных объектов // Вестник МЭИ. 2013. № 4. С. 209—215.
---
Для цитирования: Кутепов В.П., Фальк В.Н. Модели времени для сложных распределенных дискретных систем // Вестник МЭИ. 2019. № 2. С. 109—117. DOI: 10.24160/1993-6982-2019-2-109-117.
---
Работа выполнена при поддержке: РФФИ (грант № 18-01-00548)
#
1. Kovalev S.P. Arkhitektura Vremeni v Raspredelennykh Informatsionnykh Sistemakh. Vychislitel'nye Tekhnologii. 2002;7;6:38—53. (in Russian).
2. Winkowski J. An Algebraic Framework for Concurrent Systems. Rep. No. 1023. Institute of the Polish academy of science, 2012.
3. Prakash R., Singhal M. Dependency Sequences and Hierarchical Clocks: Efficient Alternativesto Vector Clocks for Mobile Computing Systems. ACM J. Wireless Network. 1997;3:349—360.
4. Lamport L. Time, Slock and the Ordering of Events in Distributed Systems. Communications of ASM. 1978; 21 (7):358—365.
5. Fidge J. Timestamps in Message-passing Systems that Preserve the Partial Ordering. Proc. XI Australian Computer Sci. Conf. 1988;10;1:56—66.
6. Middelburg S.A. Revisiting Timing in Process Algebra. J. Logic and Algebraic Programming. 2003;54: 109—127.
7. Al' Dzhabri Kh.Sh., Rodionov V.I. Graf Atsik- licheskikh Orgrafov. Vestnik Udmurtskogo Un-ta. Seriya «Matematika. Mekhanika. Komp'yuternye Nauki». 2015; 25;4:441—452. (in Russian).
8. Kutepov V.P., Fal'k V.N. Napravlennye Otnosheniya: Teoriya i Prilozheniya. Izvestiya RAN. Seriya «Tekhnicheskaya Kibernetika». 1994;5:114—123. (in Russian).
9. Fal'k V.N. Teoriya Napravlennykh Otnosheniy i Ee Prilozheniya: Avtoref. Diss. … Dokt. Tekhn. Nauk. M.: MEI, 2001. (in Russian).
10. Fal'k V.N. Ob Odnom Podkhode k Effektivnoy Numeratsii Rekursivnykh Mnozhestv Konstruktivnykh Ob′ektov. Vestnik MEI. 2013;4:209—215. (in Russian).
---
For citation: Kutepov V.P., Falk V.N. Time Models for Complex Distributed Discrete Systems. Bulletin of MPEI. 2019;2:109—117. (in Russian). DOI: 10.24160/1993-6982-2019-2-109-117.
---
The work is executed at support: RFBR (grant No. 18-01-00548)
Опубликован
2018-01-19
Раздел
Теоретические основы информатики (05.13.17)