PART 1 · 01–05
기록의 순서와 인과의 순서
왜 사건의 한 줄 실행기록만으로 부족한가요?
사회자 두 직원의 기록에 “표지 부착, 알림”과 “알림, 표지 부착”이 찍혔습니다. 한 기록이 틀렸나요?
답변 사서 지우는 표지를 붙이고, 사서 해진은 회원에게 준비 알림을 보냅니다. 이 도서관에서는 알림을 보내기 위해 표지가 붙을 때까지 기다릴 필요가 없습니다. 순서가 바뀐 두 기록 모두 가능합니다. 어느 쪽이 먼저 찍혔는지와 반드시 먼저 해야 하는 일이 무엇인지는 서로 다른 질문입니다. 사건 구조에서는 이 차이를 남길 수 있습니다.
원문·범위 · §1.1 사례 1.1.5–6
마지막 집합 {a,b} 하나만 보면 실제 기록이 ab였는지 알 수 있을까요?
알 수 없습니다. ba도 같은 집합에 도착합니다. 실제 기록을 구별하려면 시간순 목록을 따로 보관해야 합니다.
사건은 무엇인가요?
사회자 ‘회원에게 알림 보내기’라는 같은 버튼을 두 번 누르면 사건 하나인가요?
답변 버튼 이름은 동작의 종류입니다. 지우에게 보낸 알림과 다른 날 해진에게 보낸 알림은 발생이 다릅니다. b₁, b₂로 이름을 붙이면 {b₁,b₂}가 두 번의 알림을 담습니다. 둘 다 그냥 b라 쓰고 집합 {b,b}를 만들면 집합에는 b 하나만 남아 횟수를 잃습니다. 이번 실험의 b는 회원 알림 한 건을 가리킵니다.
원문·범위 · 서론, §1.1 정의 1.1.1
같은 제목의 알림 2개를 {b,b}에 넣으면 원소는 몇 개인가요?
1개입니다. 이 모형에서 두 번의 발생을 보존하려면 b₁와 b₂처럼 나눠야 합니다.
인과 순서 e≤e′는 무엇을 뜻하나요?
사회자 서가에 꽂은 책을 보았다면 장부에 어떤 일을 추가해도 안전할까요?
답변 이 사례에서 서가 배치 c의 필수 원인은 표지 부착 a입니다. c가 있으면 a도 포함되어야 합니다. a≤c에서 ≤는 자기 자신까지 포함합니다. 서로 다른 두 발생에서 실제 선후를 말할 때는 a<c처럼 씁니다. a가 관찰됐다고 해서 그 책이 반드시 서가에 놓였다고 거꾸로 읽을 수는 없습니다. a만 하고 작업을 멈춘 상태도 가능합니다.
원문·범위 · §1.3 정의 1.3.4
책을 폐기한 상태라도 표지가 먼저 붙었을 수 있나요?
네. 기본 모형에서 {a,d}는 유효합니다. a와 d를 서로 배제하는 조건은 없습니다.
인과 순서가 없으면 두 사건이 독립일까요?
사회자 “a와 b 사이에 화살표가 없다”만으로 어떤 결론까지 내릴 수 있나요?
답변 바로 그어진 선이 없어도 다른 사건을 거쳐 이어질 수 있습니다. 모든 경로를 확인해도 선후가 없다면 한 조건만 채운 것입니다. 함께 일어날 수 있는지도 확인해야 합니다. 표지 부착 a와 알림 b는 순서 제약이 없고 {a,b}도 가능합니다. 서가 배치 c와 폐기 d는 순서가 없지만 같은 책에 대한 모순된 결과라 함께 담을 수 없습니다.
원문·범위 · §1.1 사례 1.1.5–6, §3.4 정의 3.4.4
같은 구성에 들어가면 모두 독립인가요?
a와 c는 같은 구성 {a,c}에 있지만 a<c입니다. 함께 가능하다는 조건 하나만으로는 독립이 성립하지 않습니다.
충돌은 무엇인가요?
사회자 어제 서가 배치, 오늘 폐기라면 c와 d가 왜 충돌하나요?
답변 이 사례의 c와 d는 한 건의 최종 처리 요청에서 고르는 두 결과입니다. 그래서 같은 접수 건에 c와 d를 모두 넣을 수 없다고 정했습니다. 다른 날 별도의 폐기 요청을 새로 접수했다면 그때 사건은 이 d와 다른 발생입니다. 충돌은 “현실에서 한 책을 영원히 폐기할 수 없다”는 말이 아니라 지금 모델링하는 한 선택의 제약입니다.
원문·범위 · §1.1 사례 1.1.5, §3.4 정의 3.4.4
{a,c,d}에서 빠진 원인은 없는데 왜 구성이 아닌가요?
a가 있어서 c의 원인은 채웠지만 c와 d가 함께 들어 있습니다. 원인 조건과 충돌 조건을 모두 만족해야 합니다.
PART 2 · 06–10
충돌의 유전과 가능한 장부
충돌은 뒤의 사건에도 이어지나요?
사회자 이미 폐기한 책의 ‘서가 배치 영수증’만 발급할 수 있을까요?
답변 기본 네 사건에 e를 하나 더 붙입니다. 이 영수증 e는 실제 서가 배치 c 뒤에만 생기므로 c<e이고, c는 a를 요구합니다. d가 c와 충돌하는데 e와 d를 같이 허용하면, e 때문에 c도 같이 있어야 해 모순입니다. d#e는 임의로 더한 새 금지선이 아니라 기존 충돌과 원인 제약에서 따라옵니다. a와 d까지 금지된다는 뜻은 아닙니다.
원문·범위 · §1.3 정의 1.3.4, §3.4 명제 3.4.5
종이에는 a에서 e로 가는 직접 화살표가 없습니다. 그래도 a가 필요할까요?
필요합니다. a<c이고 c<e이므로 a<e입니다. 즉시 원인만 그렸어도 전체 선후는 경로를 따라갑니다.
구성(configuration)은 무엇인가요?
사회자 가능한 조합을 사건 개수로만 골라 보면 어떻게 될까요?
답변 후보 {a,c}와 {c,d}는 둘 다 두 사건짜리입니다. 전자는 c에 필요한 a가 있고 충돌도 없습니다. 후자는 a가 없고 c#d까지 들어 있습니다. 이 글의 유한 모형은 원인을 모두 포함하는지, 충돌쌍이 없는지를 별개로 검사합니다. 4개의 사건으로 만든 부분집합은 16개이고 두 검사를 함께 통과하는 구성은 10개입니다. 빈집합도 아직 아무것도 하지 않은 정상 구성입니다.
원문·범위 · §1.3 정의 1.3.4와 정리 1.3.5, §3.4 정의 3.4.6
빈집합은 사건이 없으니 검사에서 빼야 할까요?
아니요. 빠진 필수 원인도 충돌쌍도 없는 출발 구성입니다. 10개에 포함됩니다.
왜 원인을 모두 포함해야 하나요?
사회자 서가에 꽂았다는 c 기록만 들어 있는 장부를 어떻게 고치나요?
답변 표지를 붙인 증거 a까지 포함하면 {a,c}가 됩니다. c를 유지하는 가장 작은 가능한 구성입니다. 사실관계를 모르는 상황에서 억지로 a를 꾸며 내라는 뜻은 아닙니다. 주어진 규칙과 장부 기록이 함께 맞을 수 있는지를 검사한 결과입니다. 반대로 c가 애초에 오기였다면 c를 지운 빈집합도 가능한 수정 결과입니다.
원문·범위 · §1.3 정의 1.3.4의 아래로 닫힘 조건
{b,c}에서 두 사건을 유지하려면 무엇을 더해야 하나요?
a입니다. {a,b,c}가 되면 c의 원인이 있고 충돌 사건 d가 없습니다.
기록 몇 개가 같은 구성에 도달할까요?
사회자 a·b·c를 모두 기록할 때, 세 장의 카드로 정확히 몇 줄을 만들 수 있나요?
답변 기본 모형에는 a<c만 있고 b에는 순서 제약이 없습니다. a 다음 c를 고정해 놓고 b를 앞·사이·뒤 빈자리에 넣으면 bac, abc, acb의 세 줄입니다. 다른 세 줄은 c가 a보다 앞서므로 탈락합니다. 만약 직원 규정을 바꿔 알림 b도 서가 배치보다 먼저 요구하면 b<c가 추가되어 acb가 탈락합니다. 실험 2는 두 규정을 바꾸어 그 한 줄을 비교합니다.
원문·범위 · §1.1 사례 1.1.6, §1.3 정의 1.3.4에 기댄 편집부 열거
추가 규정 b<c가 생기면 abc, acb, bac 중 무엇이 사라질까요?
acb가 사라집니다. c가 b보다 먼저이기 때문입니다. 남는 순서는 abc와 bac입니다.
선택과 동시성은 어떻게 구별하나요?
사회자 가능한 기록이 두 갈래로 갈라지기만 하면 그것은 선택일까요?
답변 빈집합에서 a를 먼저 하거나 b를 먼저 할 수 있습니다. {a}에서 b를, {b}에서 a를 더하면 두 길은 {a,b}에서 만납니다. 반면 {a}에서 서가 배치 c나 폐기 d를 고른 뒤에는 c와 d를 함께 포함하는 도착점이 없습니다. 앞부분의 두 갈래만 그린 그림에서는 둘이 같은 모양이므로, 두 갈래가 다시 합쳐지는 구성이 있는지를 보세요.
원문·범위 · §1.1 사례 1.1.5와 1.1.6
기본 모형에서 c와 d의 두 길이 합쳐지는 구성을 하나 만들 수 있나요?
없습니다. c#d이므로 두 사건이 다 들어간 집합은 어떤 추가 사건을 넣어도 유효해지지 않습니다.
PART 3 · 11–15
넷과 영역으로 다시 읽기
페트리 넷에서는 같은 선택을 어떻게 그릴까요?
사회자 처리표 한 장으로 서가 배치와 폐기 중 하나만 고르는 것을 그려 볼까요?
답변 교육용 넷에서 처리표가 있는 자리에 토큰 한 개를 놓고, 배치 전이와 폐기 전이가 그 토큰을 각각 쓰게 합니다. 둘 중 하나가 토큰을 사용하면 다른 쪽에 쓸 토큰은 남지 않습니다. 반환 규칙과 추가 토큰은 없다고 정했습니다. 윈스켈은 안전 넷의 전개와 사건 구조 사이를 엄밀하게 연결합니다. 여기의 작은 토큰 예는 그 구성 전체의 증명은 아닙니다.
원문·범위 · §3.3–3.4, 특히 따름정리 3.4.3
배치 후 처리표를 다시 발급하는 전이를 추가해도 같은 설명이 성립하나요?
그대로 성립하지 않습니다. 새 전이가 토큰을 반환하면 뒤에 다른 전이가 가능할 수 있으므로 새로운 제약을 따져야 합니다.
Scott 영역과는 왜 연결되나요?
사회자 아직 덜 진행한 기록과 더 진행한 기록을 무엇으로 비교하나요?
답변 {a}가 {a,c}에 포함되므로 둘째 기록은 첫째의 발생 정보를 보존하면서 c를 추가합니다. {a,c}와 {a,d}는 어느 쪽도 다른 쪽의 부분집합이 아닙니다. 심지어 두 집합의 합집합은 충돌 때문에 구성이 아닙니다. 그래서 모든 두 구성이 합쳐지는 격자라고 단정하면 이 예에서 바로 어긋납니다. 원문의 영역 결과에는 어떤 종류의 사건 구조와 순서를 쓰는지 조건이 있습니다.
원문·범위 · §1.1 정의 1.1.8, §1.3 정리 1.3.5
{a}와 {b}에도 같은 문제가 생기나요?
기본 모형에서는 {a,b}가 구성이므로 이 두 기록은 함께 확장할 수 있습니다. 비교 불가와 함께 확장 불가를 구별하세요.
두 과정이 같다는 것은 같은 사건 수를 뜻하나요?
사회자 작업 이름이 같고 마지막 사건 수도 같으면 운영 규칙도 같을까요?
답변 두 도서관 모두 a,b,c를 갖고 최종적으로 세 사건을 모두 기록합니다. 기본 도서관은 acb를 허용하지만, b<c를 추가한 둘째 도서관은 허용하지 않습니다. 완성된 집합 {a,b,c}만 보면 이 차이를 놓칩니다. 중간 구성 {a,c}를 살펴보면 바로 갈립니다. 첫 모형에서는 가능하고 둘째에서는 b가 빠져 불가능합니다.
원문·범위 · §1.1–1.3의 구성 개념에 기댄 편집부 비교
두 모형의 네 사건 부분집합 16개 중 원래 가능하다가 불가능해진 것은 무엇일까요?
{a,c} 하나입니다. 유효한 구성은 10개에서 9개로 줄어듭니다. 실험 1에서 두 전체 목록을 대조할 수 있습니다.
유한 그림으로 무한 과정을 설명할 수 있나요?
사회자 책이 계속 도착한다면 네 사건 그림을 한 번 그린 것으로 충분할까요?
답변 원문은 끝없이 0,1,2,… 순으로 진행하는 시계도 예로 듭니다. 지금 10개를 모두 세었다는 사실은 네 사건의 이 모형에서만 완전합니다. 매일 한 번 새 알림이 생기는 모형에서 첫 세 번만 보면 {b₁,b₂,b₃}까지는 알 수 있지만 네 번째가 가능하지 않다고 결론 내릴 수 없습니다. 무한히 늘어나는 과정에는 모든 유한 관찰을 어떻게 잇는지 정해야 합니다.
원문·범위 · §1.1 사례 1.1.4, §1.4의 유한 원인
지금 프로그램이 부분집합 32개를 검사했다면 어떤 모형일까요?
영수증 e를 더한 다섯 사건 모형입니다. 2⁵=32라는 수는 후보 개수이고, 실제 가능한 구성은 12개입니다.
이번 글의 결론은 어디까지인가요?
사회자 실험을 닫은 뒤 새 업무 순서를 받으면 어떤 세 가지를 먼저 묻겠어요?
답변 첫째, 사건 이름이 작업 종류인지 개별 발생인지 정합니다. 둘째, 뒤 사건에 꼭 필요한 원인이 무엇인지 씁니다. 셋째, 함께 들어갈 수 없는 선택이 무엇인지 확인합니다. 도서관 기본 모형에서는 a<c와 c#d가 그 두 관계의 전부입니다. 그래서 b는 a와도 c와도 독립이고, c와 d는 인과가 없어도 독립이 아닙니다. 시간과 자원까지 분석하려면 그 항목을 별도로 명시해야 합니다.
원문·범위 · 서론, §1.3 정의 1.3.4, §3.4 정의 3.4.6
다른 직원의 시계에서 d가 a보다 먼저 찍혔다면 이 모형에 바로 모순인가요?
아닙니다. a와 d 사이에는 순서도 충돌도 없습니다. 같은 책이 실제로 언제 처리됐는지는 별도 자료가 필요합니다.
INTERACTIVE NOTEBOOK
도서관 장부에서 세 가지를 직접 검산하기
기본 규정은 a<c와 c#d입니다. 먼저 결과를 종이에 예상한 뒤 선택을 바꾸세요. 세 번째 실험에서는 영수증 e도 살펴봅니다.
1. 내 장부는 가능한 구성인가요?
체크한 사건의 원인과 충돌을 각각 검사합니다. ‘영수증’ 규정을 고르면 다섯 번째 사건을 사용할 수 있습니다.
2. 같은 구성의 모든 실행 순서
세 사건을 모두 담는 기록의 순서를 빠짐없이 만듭니다. 알림이 서가 배치보다 먼저여야 한다는 규정을 추가하고 사라지는 한 줄을 찾아보세요.
3. 인과인가, 독립인가, 충돌인가?
영수증 e를 추가해 a<c<e와 c#d가 적용되는 장부입니다. 직접 화살표가 없어도 간접 원인과 유전된 충돌을 셉니다.
원문으로 돌아가는 길
- 케임브리지대 저자 공개 원문. §1.1은 선택과 동시성, §1.3.4–5는 프라임 사건 구조와 구성, §3.4.4–6은 이항 충돌과 유전을 다룹니다. 편집부의 도서관 예에서는 이 마지막 특수 조건을 적용했습니다.
- 출판사 장 서지. Glynn Winskel, “Event Structures,” Petri Nets: Applications and Relationships to Other Models of Concurrency, LNCS 255, 1987, 325–392쪽. DOI 10.1007/3-540-17906-2_31.
두 사건을 함께 담을 수 있는지, 그리고 순서를 바꿀 수 있는지는 따로 물어야 합니다. 두 답이 모두 맞을 때 두 다른 사건을 독립이라고 부를 수 있습니다.
