Endpoint Sufficiency Behavioral Quotients

기술 요약: 프로비넌스(Provenance) 망각은 언제 정당한가?

문제 정의
생성 시스템은 종종 여러 추상화 수준으로 표현될 수 있는 객체를 생성한다. 하나의 표현은 오직 "가시적 종단점(visible endpoint)"(최종 객체)만을 포착하는 반면, 다른 표현은 전체 "프로비넌스"(계보, 병합 이벤트, 의존 구조)를 유지한다. 종단점 표현은 더 작지만, 시스템의 허용 법칙(admissibility laws)이 계보에 의존할 경우 잘못된 상태 기술(false state description)이 될 위험이 있다. 본 논문이 다루는 핵심 문제는 프로와넌스 정보가 시스템의 향후 법적 동작을 변경하지 않고 안전하게 망각될 수 있는 정확한 시점을 결정하는 것이다. 구체적으로, 본 논문은 다음과 같은 질문을 던진다: 종단점 투영(endpoint projection)이 법적 전이(lawful transitions)를 결정하기에 충분한 정보를 보유하는 시점은 언제이며, 버려질 수 있는 프로비넌스의 최대량은 얼마인가?

본 논문은 "종단점 충분성(endpoint sufficiency)"이 단일하고 균일한 개념이라는 통속적인 가정에 이의를 제기한다. 저자는 이 개념이 관찰 수준(즉, 즉시 활성화된 규칙만을 고려하는지, 유한한 규칙 라벨 시퀀스(trace)를 고려하는지, 또는 미래 가능성의 전체 분기 구조를 고려하는지)에 따라 달라짐을 입증한다.

방법론
저자는 **법적 생성 전이 시스템(Lawful Generative Transition Systems, LGTS)**을 사용하여 문제를 정형화한다. LGTS는 튜플 $T = (S, \Sigma, \to, U, X, \cong_X)$로 정의된다:

• $S$는 프로비넌스가 장식된 발생(occurrence)들의 집합이다.
• $\Sigma$는 규칙 라벨의 집합이다.
• $\to$는 법적 레이블된 전이 관계이다.
• $U: S \to X$는 발생을 가시적 객체로 매핑하는 종단점 투영이다.
• $\cong_X$는 가시적 객체 상의 동치 관계이다.

본 연구는 종단점 동치 관계($\equiv_U$, 여기서 $s \equiv_U t \iff U(s) \cong_X U(t)$)와 다양한 행동적 동치 관계 사이의 관계를 분석한다. 분석은 세 가지 뚜렷한 관찰 수준을 통해 진행된다:

1. 활성화 충분성(Enabled Sufficiency): 즉시 사용 가능한 규칙 라벨의 집합을 보존함.
2. 트레이스 충분성(Trace Sufficiency): 모든 유한한 규칙 라벨 시퀀스를 보존함.
3. 쿼티언트(분기) 충분성(Quotient (Branching) Sufficiency): 종단점 동치 관계를 기준으로 분기 전이 구조를 보존함.

본 논문은 트레이스 동치, 강한 비시뮬레이션(strong bisimulation), 공귀납(coinduction), 그리고 파티션 정제(partition refinement)를 포함한 표준 프로세스 의미론 도구들을 종단점과 프로비넌스의 경계에 적용하여 사용한다.

주요 기여 및 결과

1. 엄격한 3단계 계층 구조
본 논문은 세 가지 수준의 충분성이 서로 구별되며 엄격한 계층을 형성함을 입립한다:
$$\text{Quotient Sufficiency} \implies \text{Trace Sufficiency} \implies \text{Enabled Sufficiency}$$

• 활성화 충분성은 가장 약한 조건으로, 동치인 종단점이 동일한 집합의 다음 이동(next moves)을 가져야 함을 요구한다.
• 트레이스 충분성은 동치인 종단점이 동일한 유한 규칙 라벨 시퀀스 집합을 생성해야 함을 요구한다.
• 쿼티언트 충분성은 가장 강한 조건으로, 임의의 라벨에 대한 도달 가능한 종단점 클래스의 집합이 현재의 종단점 클래스에만 의존해야 하며, 특정 프로비넌스 이력에는 의존하지 않아야 함을 요구한다.

2. 정확한 충분성 기준
본 논문은 각 수준에서 종단점 투영이 충분하기 위한 정밀한 수학적 기준을 제공한다:

• 트레이스 수준: 투영이 트레이스 충분하려면, 종단점 동치가 트레이스 동치의 부분집합이어야 한다 ($\equiv_U \subseteq \equiv_{tr}$).
• 분기 수준: 투영이 쿼티언트 충분하려면, 종단점 동치가 강한 비시뮬레이션 동치여야 한다. 이는 두 종단점 동치 상태에 대해, 한 쪽에서의 모든 전이는 다른 쪽으로부터 동일한 종단점 동치 상태로 가는 전이에 의해 매칭될 수 있음을 의미한다.

3. 정형 복구(Canonical Repairs) 및 최대 망각
가공되지 않은 종단점 동치가 충분하지 않을 때, 본 논문은 가시적 종단점을 존중하면서 원하는 동작을 보존하는 가장 거친(coarsest) 상태 정제를 식별하는 두 가지 "정형 복구"를 제안한다:

• 선형 시간(트레이스)을 위한 경우: 관계 $E^U_{tr} = \equiv_U \cap \equiv_{tr}$는 종단점을 존중하고 유한 트레이스를 보존하는 가장 큰 동치 관계이다. 이는 종단점이 동일하면서도 그 미래가 규칙 라벨 트레이스로서 구별 불가능한 발생들을 식별한다.
• 분기 시간(정확한 쿼티언트)을 위한 경우: 모든 종단점 존중 강한 비시뮬레이션의 합집합으로 정의되는 관계 $\approx_U$는 가장 큰 종단점 존중 강한 비시뮬레이션이다. 쿼티언트 시스템 $T / \approx_U$는 **최대 거친 정확한 분기 쿼티언트(maximally coarse exact branching quotient)**이다.
  • 보편 성질(Universal Property): 다른 모든 정확한 종단점 존중 쿼티언트는 이 정형 쿼티언트를 정제한다. 따라서 $\approx_U$는 정확한 분기 의미론을 유지하면서 망각할 수 있는 프로비넌스의 최대량을 나타낸다.

4. 알고리즘 계산
유한 시스템의 경우, 본 논문은 $\approx_U$를 계산하기 위한 종료 가능한 파티션 정제 절차를 설명한다. 이 알고리즘은 종단점 동치 클래스의 파티션으로 시작하여, "시그니처"(도달 가능한 블록들의 집합)를 기반으로 이를 반복적으로 정제한다. 이 절차는 $\approx_U$에 해당하는 파티션에서 안정화된다.

5. 중첩 재귀적-재조합 생성(NRRG)에의 적용
본 논문은 프로비넌스가 장식된 NRRG의 특정 프레임워크에 이 결과를 적용한다. 저자는 두 발생($e_G$와 $e_H$)이 동일한 가시적 그래프 종단점($I \to A \to B$)을 공유하지만, 서로 다른 재조합 계보를 갖는 사례를 제시한다.

• $e_G$의 경우, 계보는 경계 접촉 재작성 규칙($R_B$)을 허용한다.
• $e_H$의 경우, 계보는 $R_B$를 금지한다.
• 결과: 파티션 정제 알고리즘은 이들의 인접 성공자(successor) 집합이 다르기 때문에 첫 번째 라운드에서 $e_G$와 $e_H$를 분리한다. 이는 종단점 동형성이 활성화 수준에서도 행동적 동치를 보장하지 않음을 보여주며, 제안된 정제 절차가 필요한 구분을 정확히 식별함을 입증한다.

의의 및 주장
본 논문은 프로와넌스를 전부 유지하거나 완전히 버려야 한다는 "전부 아니면 전무(all-or-nothing)" 식의 요구를 법적 망각을 위한 정확한 기준으로 대체한다고 주장한다.

• 운영적 잔여물(Operational Residue): 가공되지 않은 종단점 클래스와 정제된 클래스($\approx_U$ 또는 $E^U_{tr}$) 사이의 차이는 프로와넌스의 "운영적 잔여물"—즉, 미래 전이 공간에서 여전히 활성화되어 있는 역사적 정보—을 구성한다.
• 추상화의 정확성: 본 연구는 추상화를 단순히 타당성(과잉 근사)의 문제가 아니라, 선택된 의미론에 대한 **정확성(exactness)**의 문제로 재구성한다. 비시뮬레이션을 확인하지 않고 상태를 병합하는 가공된 쿼티언트는 특정 발생에 대해 법적이지 않은 동작(팽창)을 생성할 수 있다.
• 도메인 불가지론(Domain Agnosticism): 결과는 시스템이 종단점 투영을 가진 레이블된 전이 시스템으로 모델링될 수 있다면, 계보에 따라 허용 여부가 결정되는 모든 시스템(예: 소프트웨어 상태, 법적 문서, 과학적 주장)에 적용 가능한 정형적 기준으로 제시된다.

본 논문은 프로와넌스가 선택된 법적 미래 의미론을 변경하지 않는 발생 구별들에 대해 정확하게 삭제될 수 있다고 결론짓는다. 최대 안전한 삭제 후에 남는 것은 역사적 장식이 아니라, 진정한 **생성 상태(generative state)**이다.