Алгебра коммуникативных процессов - Algebra of communicating processes

В алгебра коммуникативных процессов (ACP) - это алгебраический подход к рассуждению о параллельные системы. Это член семейства математических теорий параллелизма, известных как алгебры процессов или технологические расчеты. ACP изначально был разработан Ян Бергстра и Ян Виллем Клоп в 1982 г.,^[1] как часть усилий по исследованию решений неохраняемых рекурсивных уравнений. Больше, чем другие исчисления исходных процессов (CCS и CSP ), разработка ACP была сосредоточена на алгебре процессов и была направлена ​​на создание абстрактной обобщенной аксиоматической системы для процессов,^[2] и на самом деле термин алгебра процессов был придуман во время исследования, которое привело к ACP.

Неформальное описание

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

Примитивы

ACP использует мгновенное, атомные действия (${displaystyle {mathit {a, b, c, ...}}}$) как его примитивы. Некоторые действия имеют особое значение, например, действие ${displaystyle delta}$, который представляет тупик или застой, и действие ${displaystyle au}$, который представляет собой тихое действие (абстрактные действия, не имеющие конкретной идентичности).

Алгебраические операторы

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

• Выбор и последовательность - наиболее фундаментальными алгебраическими операторами являются альтернатива оператор (${displaystyle +}$), который предоставляет выбор между действиями, и оператор последовательности (${displaystyle cdot}$), который определяет порядок действий. Так, например, процесс

${displaystyle (a + b) cdot c}$

сначала выбирает выполнить либо ${displaystyle {mathit {a}}}$ или же ${displaystyle {mathit {b}}}$, а затем выполняет действие ${displaystyle {mathit {c}}}$. Как выбор между ${displaystyle {mathit {a}}}$ и ${displaystyle {mathit {b}}}$ сделано не имеет значения и оставлено неопределенным. Обратите внимание, что альтернативная композиция коммутативна, а последовательная композиция - нет (потому что время течет вперед).

• Параллелизм - чтобы позволить описание параллелизма, ACP предоставляет слияние и левое слияние операторы. Оператор слияния, ${displaystyle vert vert}$, представляет собой параллельную композицию двух процессов, отдельные действия которых чередуются. Оператор слияния слева, ${displaystyle vert lfloor}$, является вспомогательным оператором с семантикой, аналогичной слиянию, но обязательством всегда выбирать свой начальный шаг из левого процесса. Например, процесс

${displaystyle (acdot b) vert vert (ccdot d)}$

может выполнять действия ${displaystyle a, b, c, d}$ в любой из последовательностей ${displaystyle abcd, acbd, acdb, cabd, cadb, cdab}$. С другой стороны, процесс

${displaystyle (acdot b) vert lfloor (ccdot d)}$

может выполнять только последовательности ${displaystyle abcd, acbd, acdb}$ поскольку операторы слияния слева гарантируют, что действие ${displaystyle {mathit {a}}}$ происходит первым.

• Коммуникация - взаимодействие (или коммуникация) между процессами представляется с помощью оператора двоичной связи, ${displaystyle vert}$. Например, действия ${displaystyle r (d)}$ и ${displaystyle w (d)}$ может быть интерпретировано как чтение и запись элемента данных ${displaystyle din D = {1,2,3, ldots}}$, соответственно. Тогда процесс

${displaystyle left (sum _ {din D} r (d) cdot yight) vert (w (1) cdot z)}$

сообщит ценность ${displaystyle 1}$ от правого компонентного процесса к левому компонентному процессу (т.е. идентификатор ${displaystyle {mathit {d}}}$ привязан к значению ${displaystyle 1}$, и бесплатные экземпляры ${displaystyle {mathit {d}}}$ в процессе ${displaystyle {mathit {y}}}$ принять это значение), а затем вести себя как слияние ${displaystyle {mathit {y}}}$ и ${displaystyle {mathit {z}}}$.

• Абстракция - оператор абстракции, ${displaystyle au _ {I}}$, это способ «скрыть» определенные действия и рассматривать их как внутренние события моделируемой системы. Абстрагированные действия преобразуются в тихий шаг действие ${displaystyle au}$. В некоторых случаях эти тихие шаги также можно удалить из выражения процесса как часть процесса абстракции. Например,

${displaystyle au _ {{c}} ((a + b) cdot c) = (a + b) cdot au}$

которое в этом случае сводится к

${displaystyle a + b}$

с момента события ${displaystyle {mathit {c}}}$ больше не наблюдается и не имеет наблюдаемых эффектов.

Формальное определение

ACP принципиально использует аксиоматический алгебраический подход к формальному определению своих различных операторов. Представленные ниже аксиомы составляют полную аксиоматическую систему ACP._{${displaystyle au}$} (ACP с абстракцией).

Алгебра основных процессов

Используя альтернативные и последовательные операторы композиции, ACP определяет алгебра основных процессов которое удовлетворяет аксиомам^[3]

${displaystyle {egin {matrix} x + y & = & y + x (x + y) + z & = & x + (y + z) x + x & = & x (x + y) cdot z & = & (xcdot z) + (ycdot z) (xcdot y) cdot z & = & xcdot (ycdot z) end {matrix}}}$

Тупик

Помимо основной алгебры, две дополнительные аксиомы определяют отношения между альтернативными операторами и операторами последовательности, а также тупик действие, ${displaystyle delta}$

${displaystyle {egin {matrix} delta + x & = & x delta cdot x & = & delta end {matrix}}}$

Параллелизм и взаимодействие

Аксиомы, связанные с операторами слияния, слияния слева и связи, следующие:^[3]

${displaystyle {egin {matrix} xvert vert y & = & xvert lfloor y + yvert lfloor x + xvert y acdot xvert lfloor y & = & acdot (xvert vert y) avert lfloor y & = & acdot y (x + y) vert lfloor z & = & (xvert lfloor z) + (yvert lfloor z) acdot xvert b & = & (avert b) cdot x avert bcdot x & = & (avert b) cdot x acdot xvert bcdot y & = & (avert b) cdot (xvert vert y) (x + y) vert z & = & xvert z + yvert z xvert (y + z) & = & xvert y + xvert zend {матрица}}}$

Когда оператор связи применяется только к действиям, а не к процессам, он интерпретируется как бинарная функция от действий к действиям, ${displaystyle vert: A imes Aightarrow A}$. Определение этой функции определяет возможные взаимодействия между процессами - те пары действий, которые не составляют взаимодействия, отображаются на действие тупика, ${displaystyle delta}$, в то время как разрешенные пары взаимодействий отображаются на соответствующие одиночные действия, представляющие возникновение взаимодействия. Например, функция связи может указывать, что

${displaystyle avert aightarrow c}$

что указывает на то, что успешное взаимодействие ${displaystyle avert a}$ будет сведено к действию ${displaystyle c}$. ACP также включает оператор инкапсуляции, ${displaystyle partial _ {H}}$ для некоторых ${displaystyle Hsubseteq A}$, который используется для преобразования неудачных попыток связи (т. е. элементов ${displaystyle H}$ которые не были уменьшены с помощью функции связи) до действия тупика. Аксиомы, связанные с функцией связи и оператором инкапсуляции, следующие:^[3]

${displaystyle {egin {matrix} avert b & = & bvert a (avert b) vert c & = & avert (bvert c) avert delta & = & delta partial _ {H} (a) & = & a {mbox {if}} аотин H partial _ {H} (a) & = & delta {mbox {if}} ain H partial _ {H} (x + y) & = & partial _ {H} (x) + partial _ {H} (y ) partial _ {H} (xcdot y) & = & partial _ {H} (x) cdot partial _ {H} (y) end {matrix}}}$

Абстракция

Аксиомы, связанные с оператором абстракции, следующие:^[3]

${displaystyle {egin {matrix} au _ {I} (au) & = & au au _ {I} (a) & = & a {mbox {if}} аотин I au _ {I} (a) & = & au {mbox {if}} ain I au _ {I} (x + y) & = & au _ {I} (x) + au _ {I} (y) au _ {I} (xcdot y ) & = & au _ {I} (x) cdot au _ {I} (y) partial _ {H} (au) & = & au xcdot au & = & x au cdot x & = & au cdot x + x acdot (au cdot x + y) & = & acdot (au cdot x + y) + acdot x au cdot xvert lfloor y & = & au cdot (xvert vert y) au vert lfloor x & = & au cdot x au vert x & = & delta xvert au & = & delta au cdot xvert y & = & xvert y xvert au cdot y & = & xvert yend {matrix}}}$

Обратите внимание, что действие а в приведенном выше списке может принимать значение δ (но, конечно, δ не может принадлежать множеству абстракций я).

Связанные формализмы

ACP послужил основой или вдохновением для нескольких других формализмов, которые можно использовать для описания и анализа параллельных систем, включая:

• PSF
• μCRL
• mCRL2
• HyPA - алгебра процессов для гибридных систем^[4]

Рекомендации