벡터 시계

벡터 클럭은 분산 시스템에서 이벤트의 부분 순서를 결정하고 인과관계 위반을 탐지하는 데 사용되는 데이터 구조다.램포트 타임스탬프에서와 마찬가지로, 프로세스 간 메시지에는 송신 프로세스의 논리 클럭 상태가 포함되어 있다.N 프로세스 시스템의 벡터 클럭은 프로세스당 하나의 클럭인 N 논리 클럭의 배열/벡터로서, 글로벌 클럭 어레이의 로컬 "가능한 가장 큰 값" 복사본은 각 프로세스에서 보관된다.

${\displaystyle {}_{}}$ ${\displaystyle i_{}}$에 의해 유지되는 벡터 클럭으로 V C i {\$displaystyle VC_{i}$를 나타냄으로써$$ 클럭 업데이트는 다음과 같이 진행된다.^[1]

• 처음에는 모든 시계가 0이다.
• 프로세스가 내부 이벤트를 경험할 때마다 벡터 내의 자체 논리 클럭을 하나씩 증가시킨다.예를 들어 프로세스 i의 이벤트에서 $V{\displaystyle }$ ${\displaystyle C_{}}$ i${\displaystyle {}_{}}$[ ${\displaystyle i}$ ${\displaystyle ]}$← V ${\displaystyle C_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle i}$ ${\displaystyle ]}$+ ${\displaystyle 1}$ ${\displaystyle VC_{i}[i]\좌측$ 화살표 $VC_{i}[i]+1}$를 업데이트한다$.$
• 프로세스가 메시지를 보낼 때마다 벡터 안의 논리 시계를 (위의 총알에서처럼, 그러나 동일한 사건에 대해 두 번이 아닌) 1씩 증가시킨 다음, 메시지는 자신의 벡터 복사본을 백업한다.
• 프로세스가 메시지를 수신할 때마다 벡터 내의 자체 논리 클럭을 하나씩 증가시키고 수신된 메시지(모든 요소에 대해)의 벡터 클럭과 수신된 메시지의 벡터 값의 최대치를 취함으로써 벡터 내의 각 요소를 업데이트한다.예를 들어 프로세스 Pj가 Pi로부터 메시지 m을 수신하는 경우, V ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}m}$ ${\displaystyle a}$ x${\displaystyle }$(${\displaystyle V}$ ${\displaystyle {}_{}}$ j${\displaystyle {}_{}}$[${\displaystyle k]}$ + 1, ${\displaystyle \mathrm{V}}$ ${\displaystyle C_{}}$ ${\displaystyle i}$ [ k ${\displaystyle ]}$,${\displaystyle \mathrm{\forall }}$ k$${\$displaystyle VC_${j$}\leftarrow max(VC_{j}+1, VC_$$i}[k$]]), $모든$ k$}$를 설정하여 업데이트한다$.$

역사

벡터 시계라는 특정 명칭을 사용하지 않은 채, 벡터 시계의 개념은 리브카 라딘과 바바라 리스크노프가 1986년 논문에서 처음^[2] 언급했는데, 여기서 '멀티파트 타임스탬프'^[3]라는 용어를 사용했다.리스크보프/라딘 용지의 31페이지에서 인용하려면:

우리는 이 문제를 멀티마트 타임스탬프를 사용하여 해결하는데, 여기에는 각 복제본마다 한 부분이 있다.따라서, n개의 복제본이 있는 경우, 타임스탬프 t는

t = <t1, …, tn>

여기서 각 부분은 양의 정수다.일반적으로 적은 수의 복제본(예: 3 - 7)이 존재하므로, 이러한 타임스탬프를 사용하는 것이 실용적이다.

"벡터 시계"라는 용어는 1988년에 콜린 피지와 프리드먼 매턴에 의해 처음으로 독립적으로 사용되었다.^[4][5]

부분발주특성

벡터 클럭은 사건의 부분적인 인과적 순서를 허용한다.다음을 정의하는 중:

• ${\displaystyle V}$ ${\displaystyle C}$( ${\displaystyle x}$) ${\$$displaystyle VC$$(x$$)}$은 이벤트 $x$의 벡터 클럭을 나타내며$$$,$ ${\displaystyle V_{}}$ ${\displaystyle C}$( x${\displaystyle {}_{}}$) z ${\$은 프로세스 $z{\displaystyle }$ ${\displaystystyle z}$에 대한 해당 클럭의 구성 요소를 나타낸다$$$.$
• ${\displaystyle VC(x)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}<VC(y)_{z'}}]}}$
  • In English: ${\displaystyle VC(x)}$ is less than ${\displaystyle VC(y)}$, if and only if ${\displaystyle VC(x)_{z}}$ is less than or equal to ${\displaystyle VC(y)_{z}}$ for all process indices ${\displaystyle z}$, and at least one of those relationships is strictly더 작은 (, C( x) z < V ( ) ${\$
• ${\displaystyle }$${\displaystyle x}$${\displaystyle }$→ ${\displaystyle y}$ ${\$은$($는) 이벤트 y ${\displaystyle \{\backslash }$$displaystyle y}$ $이전$에 $이벤트$ x ${\$ $다음{\displaystyle }$ V ( x$){\displaystyle VC(x){\$displaysty$)$로 정의된다$.$

속성:

• 대칭: ( )< ( ) ${\displaystyle VC(a)},$¬ ( ($)},$ ¬( (b ${\displaystyle (VC)(a)}$
• Transitivity:VC(를)<>VC(b){\displaystyle VC(를)<, VC(b)}과 VC(b)<>VC(c){\displaystyle VC(b)<, VC(c)}, VC(를)<>VC(c){\displaystyle VC(를)<, VC(c)}, 또는 → b{\displaystyle a\to b\.}과 대한 largeenough→ c{\displaystyle b\to c\.},→ c{\displaystyle a\to. c\.}

다른 주문과의 관계:

• $이벤트{\displaystyle }$ $x{\displaystyle }$ ${\displaystyle rT($x$)}$이(가) 발생할 때 R $)$를 실시간 표시하십시오$$. ( )< ( b) ${\displaystyle VC(a$$VC(b)}$인 경우, ( < R ( ${\displaystyle RT(a)}$
• ${\displaystyle C}$( x${\displaystyle }$) ${\displaystyle C(x)}$을(를) $이벤트{\displaystyle }$ x ${\displaystyle x}$의 Lamport 타임스탬프가 되도록$$ 두십시오$.$ C < $VC$b$)> {\displaystystyle VC(a$ $b) {\displaystystytimate C(b$)

기타 메커니즘

• 1999년 토레스-로하스와 아하마드는 벡터 시계보다 공간을 적게 차지하지만 경우에 따라서는 인과적으로 동시적인 이벤트를 완전히 주문하는 메커니즘인 '^[6]타당한 시계'를 개발했다.

• 2005년에 Agargwal과 Garg는 프로세스 수보다 크기가 작은 벡터를 사용하여 종속성을 추적하고 동적 프로세스 수가 있는 시스템에 자동으로 적응하는 시스템인 ^[7]Chain Clocks를 만들었다.
• 2008년 알메이다 외는 인터벌 트리 클럭을 도입했다.^[8][9][10]이 메커니즘은 벡터 클럭을 일반화하며, 연산에서의 ID와 프로세스 수를 미리 알 수 없을 때 동적 환경에서 작동할 수 있다.

• 2019년, Lum Ramabaja는 시스템의 노드 수에 따라 공간 복잡성이 달라지지 않는 확률론적 데이터 구조인 Bloom Clocks를 개발했다.^[11]만약 두 개의 시계가 비교가 되지 않는다면, 블룸 시계는 항상 그것을 추론할 수 있다. 즉, 잘못된 부정은 가능하지 않다.만약 두 개의 시계가 비교 가능하다면, 블룸 시계는 그 문장의 신뢰도를 계산할 수 있다. 즉, 비교 가능한 시계 쌍들 사이의 잘못된 양성률을 계산할 수 있다.

참고 항목

• 램포트 타임스탬프
• 매트릭스 시계
• 버전 벡터

참조

외부 링크

• 논리 클럭이 쉬운 이유(인과 이력, 벡터 클럭 및 버전 벡터)
• 벡터 클럭 설명
• Erlang에서 타임스탬프 기반 벡터 클럭 구현
• 목표-C에서의 벡터 클럭 구현
• Erlang에서의 벡터 클럭 구현
• 벡터 시계가 어려운 이유
• 왜 카산드라는 벡터 시계가 필요 없는가?