Семантика систем переходов структур событий с отменяемыми событиями при сохранении причинно-следственной зависимости
Язык статьи
Русский
Аннотация
Реверсивные (обратимые) вычисления — это новая парадигма, которая расширяет традиционную организацию вычислений возможностью их выполнения в обратном направлении. Структуры событий, являющиеся одной из центральных моделей параллельных недетерминированных процессов, широко используются для установления взаимосвязей между различными моделями параллелизма. В литературе выделяются два метода разработки семантики систем переходов для моделей структур событий. В первом методе состояния рассматриваются как конфигурации (наборы событий, которые уже произошли в структуре), а переходы между состояниями строятся, начиная с начальной конфигурации и расширяя конфигурации за счёт произошедших событий. Во втором методе состояния понимаются как остаточные структуры (фрагменты модели, которые остались после удаления из неё уже произошедших и конфликтующих событий), а переходы создаются по мере построения остаточных структур. Данная статья посвящена построению и исследованию взаимосвязей двух типов систем переходов, построенных из реверсивных первичных структур событий с отменяемыми событиями и с сохранением причинно-следственной зависимости между событиями. Устанавливается факт существования бисимуляционной эквивалентности между такими системами переходов в контексте истинно-параллельной (шаговой) семантики рассматриваемой модели структур событий.
Ключевые слова
Страницы
59-90
Файл
grib_virb_causal-rpes_si2024.pdf502.14 КБ
Номер