Исчисление процессов

Исчисление процессов (алгебра процессов) — семейство теорий, посвящённых формальному моделированию параллельных систем.

Исторически первая проработанная теория — исчисление взаимодействующих систем Милнера (CCS, calculus of communicating systems, 1980), следующей значительной разработкой стала теория взаимодействующих последовательных процессов Хоара (CSP, communicating sequential processes, 1985). Если в исчислении Милнера за основу положен механизм взаимодействия, называемый «рандеву», предполагающий, что взаимодействие между процессами происходит мгновенно, в случае теории Хоара взаимодействие между процессами предусматривает обмен сообщениями.

Среди других исчислений процессов — теория временных параллельных ограничений (timed concurrent constraints, TCC), алгебра взаимодействующих процессов (англ. algebra of communicating processes; ACP), LOTOS; более поздние разработки — пи-исчисление, исчисление окружений (англ. ambient calculus), PEPA, исчисление соединений (англ. join-calculus)^[1][2].

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

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

• Модель акторов

• Milner, R. Communication and Concurrency. — Prentice-Hall, Inc., 1989. — ISBN 0-13-115007-3.
• Хоар Ч. Взаимодействующие последовательные процессы. — М.: Мир, 1989. — 264 с.
• Pierce, Benjamin. The Computer Science and Engineering Handbook. — CRC Press, 1997. — P. 2190–2207. — ISBN 0-8493-2909-4.
• Baeten, J. C. M. A brief history of process algebra (англ.) // Rapport CSR 04-02. — Vakgroep Informatica, Technische Universiteit Eindhoven, 2004. Архивировано 15 июня 2007 года.
• А. М. Миронов. Теория процессов.