동시 계산의 불변성

Indeterminacy in concurrent computation

동시 연산에서의 불변성은 동시 연산에서의 불변성의 효과와 관련이 있다.컴퓨팅은 네트워킹으로 인한 동시성의 대폭적인 증가와 다핵심 컴퓨터 아키텍처의 출현으로 인해 불규칙성이 점점 중요해지고 있는 분야다.이 컴퓨터 시스템은 불규칙성을 야기하는 중재자를 이용한다.

논리 프로그래밍의 예상 한계

Patrick Hayes[1973년]는 "계산 과정과 추론 과정 사이에 이루어지는 일상적으로 첨예한 구별은 오해를 불러일으킨다"고 주장했다.로버트 코왈스키 교수는 1988년 프롤로그의 초기 역사에 대한 논문에서 "컴퓨팅은 통제된 추론"을 승인과 함께 인용할 수 있다는 논문을 개발했다.Kowalski와 Hayes와는 대조적으로, Carl Hewitt는 논리적인 추리는 오픈 시스템에서[citation needed] 동시 연산을 수행할 수 없다고 주장했다.

휴이트[1985]와 아그하[1991], 그리고 다른 출판물들은 동시성의 수학 모델이 다음과 같이 특정한 동시 연산을 결정하지 않았다고 주장했다.행위자 모델은 복수의 메시지를 동시에 보내는 행위자의 도착 순서에서 다음에 어떤 메시지가 나올지 결정하기 위해 중재자(흔히 공칭 중재자 형태로)를 사용한다.이것은 도착 순서에 불변성을 도입한다.도착 순서는 미확정이기 때문에 수학 논리만으로는 사전 정보에서 추론할 수 없다.따라서 수학논리는 개방형 시스템에서 동시연산을 구현할 수 없다.

저자들은 비록 수학 논리가 일반적인 동시성을 구현할 수는 없지만, 순차 연산 및 람다 미적분을 포함한 일부 종류의 병렬 컴퓨팅과 같은 특수한 동시 연산 사례를 구현할 수 있다고 주장한다.

도착 순서 불변

휴이트에 따르면, 배우 시스템을 위한 구체적인 용어로, 우리는 일반적으로 배우에 대한 메시지의 도착 순서가 결정되는 세부사항을 관찰할 수 없다.이를 시도하면 결과에 영향을 미치고 전자제품과 중재자의 만족도를 확인할 수 있는 등 불변성을 다른 곳으로 밀어 넣을 수도 있다.행위자 계산의 중재 과정의 내부를 관찰하는 대신에, 우리는 결과를 기다린다.중재자에 대한 불변은 배우들에게 불변함을 낳는다.우리가 결과를 기다리는 이유는 불규칙성 때문에 대안이 없기 때문이다.

수학적 논리의 한계에 대해 발표된 주장의 근거를 명확히 하는 것이 중요하다.액터스가 일반적으로 수학적 논리로 구현될 수 없다는 것만이 아니었다.공개된 주장은 행위자 모델의 물리적 기반에 대한 불변성 때문에 어떤 종류의 연역적 수학적 논리도 한계를 벗어날 수 없다는 것이었다.이는 나중에 연구자들이 메시지 패싱을 사용한 동시 연산까지 Prolog(논리 프로그래밍에 어느 정도 기초가 있었다)를 확장하려고 시도하면서 중요해졌다. (아래 절 참조)

배우들의 수학적 이론은 이것에 대해 무엇을 말하고 있는가?폐쇄형 시스템은 외부와 통신하지 않는 것으로 정의된다.행위자 모델 이론은 다음과 같이 표현 정리[Huitt 2007]를 사용하여 닫힌 행위자 시스템의 모든 가능한 계산을 특성화하는 수단을 제공한다.

폐쇄적인 시스템에 의해 나타난 수학적인 변명은S는 다음과 같이 S에 대한 변절(의미)을 구성하기 위해 함수 진행에S 근접한 동작으로 ⊥S이라고 하는 초기 동작으로부터 점점 더 나은 근사를 구성함으로써 발견된다.

이렇게 해서 S의 행동은 가능한 모든 행동(한계 비결정론 포함)의 관점에서 수학적으로 특징지어질 수 있다.

그래서 수학적 논리는 폐쇄적인 행위자 시스템의 모든 가능한 계산을 특징 지을 수 있다.

정보의 부족으로 인한 논리의 한계

개방형 행위자 시스템 S는 S가 이러한 외부 행위자와 의사소통할 수 있도록 계산 도중에 외부 행위자의 주소를 S로 전달할 수 있는 시스템이다.이 외부 행위자들은 차례로 S에 의해 제공된 주소를 사용하여 S에 내부 행위자와 통신할 수 있다.도착 순서를 추론할 수 없는 한계 때문에 외부에서 어떤 메시지가 전송되는지 아는 것은 S의 응답을 추론할 수 없을 것이다.개방형 시스템을 구현하기 위해 다른 동시 시스템 모델(예: 프로세스 캘컬리)을 사용할 경우, 이러한 시스템도 도착 시간 순서에 따라 동작할 수 있으므로 논리적 추론에 의해 구현될 수 없다.

프롤로그와 같은 동시 시스템은 수학적 논리에 기초한다고 주장되었다.

키스 클라크, 헤르베 갈레르, 스티브 그레고리, 비제이 사라스와트, 우디 샤피로, 우에다 카즈노리 등에서는 메시지용 데이터 구조 스트림과 공유 변수를 통일하여 프롤로그와 같은 동시 메시지 전달 시스템을 개발하였다.이 시스템들이 수학 논리에 기초했다는 주장이 나왔다.[citation needed]이런 제도가 일본 5세대 프로젝트(ICOT)의 근간으로 쓰였다.

Carl Hewitt와 Gul Agha[1991]는 이러한 Prolog와 유사한 동시 시스템은 연역적이거나 논리적이지 않다고 주장하였다: Actor 모델과 마찬가지로 Prolog와 같은 동시 시스템은 메시지 전달에 기초하였고 결과적으로 동일한 불변성의 대상이었다.

논리적 운영 및 시스템 효율성

Hewitt는 Prolog와 Prolog와 유사한 동시 시스템으로부터 기본적인 교훈을 얻을 수 있다고 주장했다: 동시 계산의 범용 모델은 기본 통신 메커니즘에 의무적인 오버헤드를 가짐으로써 제한된다.이는 데이터 구조 스트림에서 데이터 구조 스트림에서 메시지를 추출하고 단일화를 사용한 패턴 지향적 호출을 기본 원점으로 포함시키는 것에 반대하는 주장이다.그러나 샤피로가 프롤로그와 같은 동시 프로그래밍 언어에 대한 조사를 포함에 대한 논쟁에 비교한다.

다른 계산 모델에서의 불변성

중재는 동시 연산(Actor model)의 행위자 모델에서 불변성의 기초가 된다(Actor models and Actor model 이론의 History of the Actor models) 참조).그것은 또한 프로세스 캘커리와 같은 동시 시스템의 다른 모델에서도 역할을 할 수 있다.

참고 항목

참조

  • 칼 휴이트 연산이란 무엇인가? 계산 가능한 우주에서 배우 모델과 튜링의 모델:연산 이해 및 연산으로서의 자연 탐구.앨런 M의 기억을 위해 헌신했다.그의 탄생 100주년 기념일에 튜링.헥터 제닐이 편집했다.세계 과학 출판사. 2012
  • 칼 휴이트플래너: 로봇 IJCAI 1969에서 이론 증명 언어.
  • 칼 휴이트Planner IJCAI 1971에 지식의 절차적 내장.
  • 칼 휴이트, 피터 비숍, 리차드 스타이거.인공지능 IJCAI 1973을 위한 유니버설 모듈러 배우 형식주의.
  • 로버트 코왈스키 에든버러 대학교 인공지능학과 프로그래밍 언어 메모 70으로 논리를 서술한다.1973.
  • 팻 헤이스.컴퓨터 과학의 계산과 추론 수학 기반: 심포지엄과 하계 학교, 슈트렙스케 플레소, 하이 타트라, 체코슬로바키아, 1973년 9월 3일~8일.
  • Carl Hewitt와 Henry Baker Laws for Communication Parallel Process IFIP-77, 1977년 8월.
  • 칼 휴이트제어 구조를 인공지능의 전달 메시지 저널 패턴으로 보는 것.1977년 6월.
  • 헨리 베이커.실시간 계산을 위한 배우 시스템 MIT EECS 박사 논문.1978년 1월.
  • 빌 콘펠트와 칼 휴이트.과학 커뮤니티 시스템, 인간 및 사이버네틱스에 대한 IEEE 거래 은유.1981년 1월.
  • 윌 클린저배우 의미론 MIT 수학 박사 논문의 기초.1981년 6월.
  • 칼 휴이트오픈 시스템 바이트 매거진의 도전.1985년 4월.인공지능의 기반에 재인쇄 - 캠브리지 대학 출판부의 출처.1990.
  • 굴 아그하.배우: 분산 시스템 박사 논문의 동시 연산 모델.MIT 프레스 1986.
  • 로버트 코왈스키1986년 ACM 14차 컴퓨터 과학 연례 회의의 논리의 한계.
  • 에후드 샤피로(에디터).1987년 동시 프롤로그 MIT 출판사
  • 로버트 코왈스키ACM의 로직 프로그래밍 커뮤니케이션의 초기 해.1988년 1월.
  • 에후드 샤피로.동시 로직 프로그래밍 언어 ACM Computing Surveys의 제품군.1989년 9월.
  • 칼 휴이트와 굴 아그하Guarded Horn 조항 언어: 그것들은 연역적이고 논리적인가?5세대 컴퓨터 시스템에 관한 국제 회의, 옴샤 1988.도쿄. 또한 MIT의 인공지능 제2권. MIT 프레스 1991.
  • 칼 휴이트*칼 휴이트.반복된 논리 프로그래밍의 소멸과 그것이 왜 잘못되고 왜 잘못되었는지, 왜: AI 연구와 응용의 교훈으로 환생할 것인가.기술 보고서 SS-06-08.AAAI 프레스.2006년 3월.

외부 링크