프로세스 미적분

컴퓨터 과학에서 프로세스 계산(또는 프로세스 대수)은 공식적으로 동시 시스템을 모델링하기 위한 다양한 관련 접근법 패밀리입니다.프로세스 계산은 독립된 에이전트 또는 프로세스 간의 상호 작용, 통신 및 동기화를 개략적으로 설명하는 도구를 제공합니다.또한 프로세스 기술을 조작 및 분석할 수 있는 대수적 법칙을 제공하고 프로세스 간의 동등성에 대한 공식 추론을 허용합니다(예: 이원 시뮬레이션을 사용).프로세스 계산의 주요 예로는 CSP, CCS, ACP 및 LOTOS가 ^[1]있습니다.더 최근에 추가된 패밀리에는 γ-calculus, 주변 미적분, PEPA, 융접 미적분 및 결합 미적분이 포함됩니다.

필수 기능

기존 공정 계산의 다양성은 매우 크지만(확률적 행동, 타이밍 정보 및 분자 상호작용 연구를 위한 전문화를 포함하는 변종 포함), 모든 공정 계산에는 다음과 같은 ^[2]몇 가지 특징이 있습니다.

독립 프로세스 간의 상호작용을 공유 변수의 수정이 아닌 통신(메시지 전달)으로 나타냅니다.
소수의 원시 요소 집합을 사용하는 프로세스와 시스템을 설명하고 이러한 원시 요소를 결합하는 연산자를 설명합니다.
공정 연산자에 대한 대수 법칙 정의. 공정 식을 등식 추론을 사용하여 조작할 수 있습니다.

프로세스의 수학

프로세스 미적분을 정의하려면 통신 수단을 제공하는 데 목적이 있는 일련의 이름(또는 채널)으로 시작합니다.많은 구현에서 채널은 효율을 개선하기 위해 풍부한 내부 구조를 가지고 있지만, 대부분의 이론적인 모델에서는 이를 추상화하지 않습니다.이름뿐만 아니라 오래된 것에서 새로운 과정을 형성할 수 있는 수단이 필요하다.기본 연산자는 항상 어떤 형태로든 존재하며 다음을 ^[3]수행할 수 있습니다.

프로세스의 병렬 구성
데이터 송수신에 사용할 채널 지정
상호작용의 순차화
교호작용 점 숨기기
재귀 또는 프로세스 복제

병렬 구성

보통 $P\vert Q$ Q $(\displaystyle$ P\ $vert$ Q $P\vert Q$ 로 표기되는 2개의 ${\mathit {P}}$ P $(\$ displaystyle { $P})$ 와 ${\mathit {P}}$ Q $(\$ 의 병렬 구성은 프로세스 계산과 순차 계산 모델을 구별하는 주요 원시 사항입니다.병렬 구성을 통해 P $(\$ 와 ${\mathit {P}}$ Q $(\$ 의 ${\mathit {Q}}$ ${\mathit {P}}$ 을 동시에 독립적으로 진행할 수 있습니다.그러나 P $(또는$ 그 반대)에서 ${\mathit {P}}$ ${\mathit {P}}$ $(또는$ 그 $반대)$ 로 ${\mathit {Q}}$ 를 동기화하고 동기화할 수 있습니다.중요한 것은 에이전트 또는 프로세스를 한 번에 여러 채널에 연결할 수 있다는 것입니다.

채널은 동기 또는 비동기일 수 있습니다.동기 채널의 경우 메시지를 보내는 에이전트는 다른 에이전트가 메시지를 수신할 때까지 기다립니다.비동기 채널에는 이러한 동기화가 필요하지 않습니다.일부 프로세스에서는 계산(특히 "계산") 채널 자체가 (다른) 채널을 통해 메시지로 전송되므로 프로세스 상호 접속의 토폴로지가 변경될 수 있습니다.일부 프로세스 계산에서는 계산 실행 중에 채널을 생성할 수도 있습니다.

의사소통

상호작용은 정보의 직접적인 흐름일 수 있지만 항상 그런 것은 아닙니다.즉, 입력과 출력을 듀얼 인터랙션 프리미티브로 구별할 수 있습니다.이러한 구별을 하는 프로세스 계산은 일반적으로 입력 연산자( $x(v)$ : $x(v)$ x ( $x(v)$ $){displaystyle$ x ( $v$ 와 출력 연산자( $x\langle y\rangle$ : x $x\langle y\rangle$ y ${\$ { $displaystyle$ x $\langle$ y $\rangle$ }) $x\langle y\rangle$ 를 정의합니다.이 두 연산자(여기서 ${\mathit {x}}$ \ $displaystyle x\math$ {x ${\mathit {x}}$ 는 듀얼 psynchronization과 상호 작용하기 위해 사용됩니다.제한적

정보가 교환되면 출력 프로세스에서 입력 프로세스로 흐릅니다.출력 프리미티브는 전송할 데이터를 지정합니다.x $x\langle y\rangle$ y { $display$ x \ $langle$ y \ rangle $x\langle y\rangle$ 에서 이 데이터는y { $display$ y $y$ }입니다. 마찬가지로 입력이 데이터를 수신할 것으로 예상되는 경우 하나 이상의 바인딩 변수가 도착 시 데이터로 대체되는 플레이스 홀더 역할을 합니다.x $x(v)$ ( $x(v)$ ) { $displaystyle$ x ( $v$ ) $x(v)$ 、 v { $displaystyle$ v}가 $v$ 그 역할을 합니다.상호작용에서 교환할 수 있는 데이터의 종류는 서로 다른 공정 계산을 구별하는 주요 특징 중 하나입니다.

순차적 구성

상호작용을 일시적으로 주문해야 하는 경우도 있습니다.예를 들어, 먼저 x $(\$ { $x})$ 에 ${\mathit {x}}$ 대한 데이터를 받은 다음 y $(\$ 에 데이터를 전송하는 등의 알고리즘을 지정하는 것이 바람직할 수 있습니다.순차적 구성은 이러한 목적으로 사용할 수 있습니다.이것은 다른 계산 모델로부터 잘 알려져 있다.프로세스 계산에서 시퀀셜라이제이션 연산자는 보통 입력 또는 출력 또는 둘 다와 통합됩니다.예를 들어 $x(v)\cdot P$ x ( $x(v)\cdot P$ ) $x(v)\cdot P$ p $x(v)\cdot P$ {\ $displaystyle$ ${\mathit {x}}$ x $(v)\cdot$ P $x(v)\cdot P$ $}$ 는 x {\displaystyle { $x$ 에서 입력을 기다립니다. 이 입력이 발생한 ${\mathit {P}}$ 에만 $프로세스$ P {\displaystyle ${p}$ 이(가 $x(v)\cdot P$ ${\mathit {P}}$ ) 활성화되고 ${\mathit {x}}$ x {\ $displaystyle {x}$ 을 ${\mathit {x}}$ 통해 수신된 데이터가 대체됩니다. ${\mathit {v}}$ v \ $displaystyle$ \ $mathit$ { $v$ } ${\mathit {v}}$

환원 의미론

프로세스 계산의 계산적 본질을 포함하는 핵심 운영 감소 규칙은 병렬 구성, 순차화, 입력 및 출력의 관점에서만 제공될 수 있습니다.이 감소에 대한 자세한 내용은 계산마다 다르지만 본질은 거의 동일합니다.축소 규칙은 다음과 같습니다.

\displaystyle x\langle y\cdot P\;\vert \;x(v)\cdot Q\long rightrow P\;\vert \;Q[{y}\!/\!_{v}}

이 축소 규칙의 해석은 다음과 같습니다.

$x\langle y\rangle \cdot P$ x $x\langle y\rangle \cdot P$ 는 $x\langle y\rangle \cdot P$ 는 $x\langle y\rangle \cdot P$ $(\$ x\ $langle$ y $\$ $cdot$ P $)$ 에 따라 메시지를 보냅니다. ${\mathit {y}}$ 서는 x(\displaystyle { $x$ 마지막으로 x $($ $x(v)\cdot Q$ 는 $x(v)\cdot Q$ x(\ $displaystyle$ x $(v$ )\ $cdot$ Q $($ $x$ 에서 메시지를 수신합니다 $.$
$메시지$ 가 전송되면 $x\langle y\rangle \cdot P$ y y $x\langle y\rangle \cdot P$ P \ $displaystyle$ x \ $langle$ y \ $cdot$ P $x\langle y\rangle \cdot P$ becomes $x\langle y\rangle \cdot P$ p the ${\mathit {P}}$ \ $display$ style \ mathit { $P$ $x(v)\cdot Q$ ( $x(v)\cdot Q$ ) $x(v)\cdot Q$ Q \ $display style$ x ( v ) \ $cdot$ Q $x(v)\cdot Q$ qy $x(v)\cdot Q$ the $the$ the the the the the the [ [ [ [ [ [ [ [Q [ $Q[^{y}\!/\!_{v}]$ / $Q[^{y}\!/\!_{v}]$ $]{$ $display sty$ ! $_{v$ ${\mathit {v}}$ 표시자 ${\mathit {v}}$ v\ $display\$ style\ $mathit$ ${v}$ 이 ${\mathit {v}}$ (가) y $\$ $displaystyle$ $\$ displaystyle ${\mathit {x}}$ mathit ${x}$ 로 대체된 ${\mathit {Q}}$ Q $(\$ displaystyle\ $mathit$ ${x$ })입니다 ${\mathit {Q}}$ .

출력 연산의 계속이 미적분의 특성에 큰 영향을 미치기 때문에 P $(style$ { $mathit {P})$ 가 ${\mathit {P}}$ 범위로 지정할 수 있는 ${\mathit {P}}$ 의 클래스가 있습니다.

숨기다

프로세스는 특정 상호작용 포인트에서 확립할 수 있는 연결 수를 제한하지 않습니다.그러나 교호작용 점은 간섭(즉, 교호작용)을 허용합니다.소형, 최소 및 구성 시스템의 합성에 있어 간섭을 제한하는 능력은 매우 중요합니다.숨기기 작업을 통해 에이전트를 병렬로 구성할 때 상호 작용 지점 간의 연결을 제어할 수 있습니다.숨김은 다양한 방법으로 나타낼 수 있습니다.예를 들어 $,$ p(\displaystyle $\mathit {P})$ 에서 ${\mathit {P}}$ x(\displaystyle $\$ $mathit$ ${x$ $P\setminus \{x\}$ 라는 ${\mathit {x}}$ 이름의 숨김은 p $(\displaystyle(\nu$ \; $x)P$ $)$ 로 나타낼 수 있지만 CSP에서는 p $displaystyle$ { $})$ 로 쓸 수 있습니다 $.$

재귀와 리플리케이션

지금까지 제시된 연산은 유한한 상호작용만을 설명하며, 결과적으로 비종단 동작을 포함하는 완전한 계산 가능성에 불충분하다.재귀 및 복제는 무한 동작을 유한하게 기술할 수 있는 작업입니다.재귀는 순차적 세계에서 잘 알려져 있습니다.리플리케이션 $! P$ \ $displaystyle!$ $P는$ 셀 수 없을 정도로 무한히 ${\mathit {P}}$ P $(\displaystyle\mathit {P})$ 프로세스의 ${\mathit {P}}$ 병렬 구성을 줄인 것으로 이해할 수 있습니다.

디스플레이 스타일!P=P\mid!P}

특수한 프로세스

프로세스 계산에는 일반적으로 상호작용 포인트가 없는 ${\mathit {nil}}$ 프로세스 $($ \ $displaystyle$ $\mathit{$ $nil$ $0$ \ $displaystyle0$ ${\mathit {STOP}}$ $(\$ $\delta$ { $STOP$ ${\$ \ $delta$ 또는 $\delta$ 적절한 ${\mathit {nil}}$ )도 포함됩니다.그것은 완전히 비활동적이며, 그것의 유일한 목적은 유도 앵커 역할을 하는 것이며, 그 위에 더 흥미로운 과정이 생성될 수 있다.

이산 및 연속 프로세스 대수

프로세스 대수는 이산 시간과 연속 시간(실시간 또는 조밀한 시간)^[4]에 대해 연구되었습니다.

역사

20세기 전반에는 계산 가능 함수의 비공식적 개념을 포착하기 위해 다양한 형식주의가 제안되었고, μ-재귀 함수, 튜링 기계, 람다 미적분은 오늘날 가장 잘 알려진 예일 수 있다.이들 모두가 서로 암호화할 수 있다는 점에서 본질적으로 동등하다는 놀라운 사실은 처치-튜링 논제를 뒷받침한다.또 다른 공유 기능은 거의 언급되지 않습니다.그것들은 모두 순차 연산 모델로 가장 쉽게 이해됩니다.컴퓨터 과학의 후속 통합은 계산의 개념, 특히 동시성과 통신의 명시적 표현에 대한 보다 미묘한 공식을 필요로 했다.프로세스 계산, 1962년 페트리 네트, 1973년 액터 모델과 같은 동시성 모델이 이 연구 라인에서 나타났다.

프로세스 계산 연구는 1973년부터 1980년까지 로빈 밀너의 커뮤니케이션 시스템 미적분학(CCS)에 대한 중요한 연구로 시작되었으며, C.A.R. Hoare의 커뮤니케이션 시퀀셜 프로세스(CSP)는 1978년에 처음 등장하여 1980년대 초에 본격적인 미적분학으로 발전하였다.CCS와 CSP가 발전함에 따라 아이디어의 교차화가 많이 이루어졌습니다.1982년 Jan Bergstra와 Jan Willem Klop은 커뮤니케이션 프로세스의 대수(ACP)로 알려진 것을 연구하기 시작했고, 그들의 ^[1]작업을 설명하기 위해 프로세스 대수라는 용어를 도입했다.CCS, CSP 및 ACP는 프로세스 계산 패밀리의 3가지 주요 분기를 구성합니다.기타 프로세스 계산의 대부분은 이들 3가지 계산 중 하나에 대한 루트를 추적할 수 있습니다.

현재의 연구

다양한 프로세스 계산이 연구되어 모두 여기서 설명한 패러다임과 일치하는 것은 아닙니다.가장 두드러진 예는 환경미적분일 수 있다.프로세스 계산이 활발한 연구 분야이기 때문에 이는 예상할 수 있습니다.현재 공정 계산에 대한 연구는 다음과 같은 문제에 초점을 맞추고 있습니다.

계산 현상의 보다 나은 모델링을 위한 새로운 프로세스 계산 개발.
주어진 공정 미적분의 정상 동작 하위 계산 찾기.이것은 (1) 대부분의 계산이 다소 일반적이고 임의 프로세스에 대해 많은 것을 말할 수 없다는 점에서 상당히 거칠기 때문에, 그리고 (2) 계산 어플리케이션이 미적분 전체를 거의 소진하지 않기 때문에 가치가 있다.오히려 형식적으로 매우 제약된 프로세스만 사용합니다.공정의 형태를 제한하는 것은 대부분 유형 시스템을 통해 연구됩니다.
Hoare 로직의 아이디어를 따라 프로세스의 임의의 속성을 추론할 수 있는 프로세스의 논리학입니다.
행동 이론: 두 프로세스가 동일하다는 것은 무엇을 의미합니까?두 프로세스가 다른지 아닌지를 어떻게 판단할 수 있을까요?공정의 동등성 클래스에 대한 대표자를 찾을 수 있습니까?일반적으로 병렬로 실행되고 있는 다른 프로세스가 차이를 검출할 수 없는 경우 프로세스는 동일한 것으로 간주됩니다.불행하게도, 이러한 직관을 정확하게 만드는 것은 미묘하며 대부분 다루기 어려운 평등 특성을 산출한다(대부분의 경우 중단 문제의 결과로 결정될 수 없다).이중 시뮬레이션은 공정 동등성에 대한 추론을 지원하는 기술 도구입니다.
계산의 표현력.프로그래밍 경험에 따르면 일부 언어에서 특정 문제가 다른 언어보다 해결하기가 더 쉽습니다.이 현상은 Church-Turing 논문에 의해 제공되는 것보다 계산 모델링 계산의 표현성에 대한 더 정확한 특성화를 요구한다.이를 위한 한 가지 방법은 두 가지 형식 사이의 인코딩을 고려하고 인코딩이 잠재적으로 보존할 수 있는 속성을 확인하는 것입니다.보존할 수 있는 속성이 많을수록 부호화의 대상이 표현력이 높아집니다.프로세스 계산에서는 동기식 δ-calculus가 비동기식 변종보다 표현력이 높고 고차식 δ-calculus와 ^[5]표현력이 동일하지만 주변 ^{[citation needed]}미적분보다 작다는 것이 유명한 결과입니다.
프로세스 미적분을 사용하여 생물학적 시스템(stocastic δ-calculus, BioAmbients, Beta Binders, BioPEPA, Brane 미적분)을 모델링합니다.일부에서는 프로세스 이론 도구에 의해 제공되는 구성성이 생물학자들이 지식을 더 공식적으로 정리하는 데 도움이 될 수 있다고 생각합니다.

소프트웨어 구현

프로세스 대수학의 배후에 있는 아이디어는 다음과 같은 몇 가지 도구를 만들어냈습니다.

다른 동시성 모델과의 관계

이력 모노이드는 일반적으로 개별 통신 프로세스의 이력을 나타낼 수 있는 자유 객체입니다.프로세스 미적분은 일관된 ^[6]방식으로 역사 모노이드에 부과되는 형식 언어이다.즉, 이력 모노이드는 동기화된 일련의 이벤트만 기록할 수 있으며 허용된 상태 천이를 지정할 수 없습니다.그러므로, 프로세스 미적분은 역사 모노이드에 대한 공식 언어와 자유 모노이드에 대한 것과 같다.

통신을 위한 채널 사용은 프로세스 계산과 페트리 네트 및 액터 모델 등 다른 동시성 모델을 구별하는 특징 중 하나이다(액터 모델 및 프로세스 계산 참조).프로세스 계산에 채널을 포함시키는 기본적인 동기 중 하나는 특정 대수 기법을 활성화하여 프로세스를 대수적으로 추론하는 것을 용이하게 하는 것이었습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Baeten, J.C.M. (2004). "A brief history of process algebra" (PDF). Rapport CSR 04-02. Vakgroep Informatica, Technische Universiteit Eindhoven.
^ Pierce, Benjamin (1996-12-21). "Foundational Calculi for Programming Languages". The Computer Science and Engineering Handbook. CRC Press. pp. 2190–2207. ISBN 0-8493-2909-4.
^ Baeten, J.C.M.; Bravetti, M. (August 2005). "A Generic Process Algebra". Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3). Bertinoro, Forlì, Italy: BRICS, Department of Computer Science, University of Aarhus. Retrieved 2007-12-29.
^ Baeten, J. C. M.; Middelburg, C. A. (2000). "Process algebra with timing: Real time and discrete time": 627–684. CiteSeerX 10.1.1.42.729. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Sangiorgi, Davide (1993). Gaudel, M. -C.; Jouannaud, J. -P. (eds.). "From π-calculus to higher-order π-calculus — and back". TAPSOFT'93: Theory and Practice of Software Development. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 668: 151–166. doi:10.1007/3-540-56610-4_62. ISBN 9783540475989.
^ Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PostScript). In Diekert, V.; Rozenberg, G. (eds.). The Book of Traces. Singapore: World Scientific. pp. 3–41. ISBN 981-02-2058-8.

추가 정보

매튜 헤네시:프로세스 대수이론, MIT 프레스, ISBN 0-262-08171-7.
C. A. R. Hoare: 커뮤니케이션 시퀀셜 프로세스, 프렌티스 홀, ISBN0-13-153289-8.
- 이 책은 옥스퍼드 대학 컴퓨팅 연구소의 Jim Davies에 의해 갱신되었습니다.새로운 에디션은 Using CSP 웹사이트에서 PDF 파일로 다운로드 할 수 있습니다.
Robin Milner: 커뮤니케이션 시스템의 미적분, Springer Verlag, ISBN 0-387-10235-3.
Robin Milner: 통신 및 모바일 시스템: Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.
Valk, Rüdiger; Moldt, Daniel; Köhler-Bußmeier, Michael, eds. (2011). "Chapter 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF). Formale Grundlagen der Informatik II: Modellierung und Analyse von Informatiksystemen. Theoretische Grundlagen der Informatik (in German). Vol. Part 2. University of Hamburg. FGI2. Archived (PDF) from the original on 2019-07-09. Retrieved 2019-07-13.

[baeten2004-1] Baeten, J.C.M. (2004). "A brief history of process algebra" (PDF). Rapport CSR 04-02. Vakgroep Informatica, Technische Universiteit Eindhoven.

[2] Pierce, Benjamin (1996-12-21). "Foundational Calculi for Programming Languages". The Computer Science and Engineering Handbook. CRC Press. pp. 2190–2207. ISBN 0-8493-2909-4.

[3] Baeten, J.C.M.; Bravetti, M. (August 2005). "A Generic Process Algebra". Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3). Bertinoro, Forlì, Italy: BRICS, Department of Computer Science, University of Aarhus. Retrieved 2007-12-29.

[4] Baeten, J. C. M.; Middelburg, C. A. (2000). "Process algebra with timing: Real time and discrete time": 627–684. CiteSeerX 10.1.1.42.729. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[5] Sangiorgi, Davide (1993). Gaudel, M. -C.; Jouannaud, J. -P. (eds.). "From π-calculus to higher-order π-calculus — and back". TAPSOFT'93: Theory and Practice of Software Development. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 668: 151–166. doi:10.1007/3-540-56610-4_62. ISBN 9783540475989.

[6] Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PostScript). In Diekert, V.; Rozenberg, G. (eds.). The Book of Traces. Singapore: World Scientific. pp. 3–41. ISBN 981-02-2058-8.

[1]

[2]

[3]

[4]

[5]

[6]

v t 동시 컴퓨팅
일반	동시성 동시성 제어 선형성
공정계산	CSP CCS ACP 로고 - - calculuscalculus 환경미적분 API 계산 PEPA 결합계산
고전적인 문제	ABA 문제 흡연자 문제 교착 상태 식사 철학자의 문제 생산자-소비자 레이스 조건 독자-라이터 문제 잠자는 이발사 문제
카테고리: 동시 컴퓨팅

Search

프로세스 미적분

네임스페이스

더

목차

필수 기능

프로세스의 수학

병렬 구성

의사소통

순차적 구성

환원 의미론

숨기다

재귀와 리플리케이션

특수한 프로세스

이산 및 연속 프로세스 대수

역사

현재의 연구

소프트웨어 구현

다른 동시성 모델과의 관계

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

프로세스 미적분

필수 기능

프로세스의 수학

병렬 구성

의사소통

순차적 구성

환원 의미론

숨기다

재귀와 리플리케이션

특수한 프로세스

이산 및 연속 프로세스 대수

역사

현재의 연구

소프트웨어 구현

다른 동시성 모델과의 관계

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.