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