벡터 시계

Vector clock

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

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

벡터 클럭 시스템의 예.파란색 영역의 사건이 사건 B4로 이어지는 원인인 반면, 빨간색 영역의 사건은 사건 B4의 영향이다.
  • 처음에는 모든 시계가 0이다.
  • 프로세스가 내부 이벤트를 경험할 때마다 벡터 내의 자체 논리 클럭을 하나씩 증가시킨다.예를 들어 프로세스 i의 이벤트에서 i[ ← V [ + 화살표 를 업데이트한다
  • 프로세스가 메시지를 보낼 때마다 벡터 안의 논리 시계를 (위의 총알에서처럼, 그러나 동일한 사건에 대해 두 번이 아닌) 1씩 증가시킨 다음, 메시지는 자신의 벡터 복사본을 백업한다.
  • 프로세스가 메시지를 수신할 때마다 벡터 내의 자체 논리 클럭을 하나씩 증가시키고 수신된 메시지(모든 요소에 대해)의 벡터 클럭과 수신된 메시지의 벡터 값의 최대치를 취함으로써 벡터 내의 각 요소를 업데이트한다.예를 들어 프로세스 Pj가 Pi로부터 메시지 m을 수신하는 경우, V x( j[ + 1, [ k , k{\{j]]), k를 설정하여 업데이트한다

역사

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

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

t = <t1, …, tn>

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

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

부분발주특성

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

  • ( ) 은 이벤트 의 벡터 클럭을 나타내며 ( x) z 은 프로세스 에 대한 해당 클럭의 구성 요소를 나타낸다
    • In English: is less than , if and only if is less than or equal to for all process indices , and at least one of those relationships is strictly더 작은 (, C( x) z < V ( )
  • 는) 이벤트 y x V ( xdisplaysty로 정의된다

속성:

  • 대칭: ( )< ( ) ¬ ( ( ¬( (b
  • 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\.}

다른 주문과의 관계:

  • x(가) 발생할 때 R 를 실시간 표시하십시오. ( )< ( b) 인 경우, ( < R (
  • ( x) 을(를) x Lamport 타임스탬프가 되도록 두십시오 C < b )

기타 메커니즘

  • 1999년 토레스-로하스와 아하마드는 벡터 시계보다 공간을 적게 차지하지만 경우에 따라서는 인과적으로 동시적인 이벤트를 완전히 주문하는 메커니즘인 '[6]타당한 시계'를 개발했다.
  • 2005년에 Agargwal과 Garg는 프로세스 수보다 크기가 작은 벡터를 사용하여 종속성을 추적하고 동적 프로세스 수가 있는 시스템에 자동으로 적응하는 시스템인 [7]Chain Clocks를 만들었다.
  • 2008년 알메이다 외는 인터벌 트리 클럭을 도입했다.[8][9][10]이 메커니즘은 벡터 클럭을 일반화하며, 연산에서의 ID와 프로세스 수를 미리 알 수 없을 때 동적 환경에서 작동할 수 있다.
  • 2019년, Lum Ramabaja는 시스템의 노드 수에 따라 공간 복잡성이 달라지지 않는 확률론적 데이터 구조인 Bloom Clocks를 개발했다.[11]만약 두 개의 시계가 비교가 되지 않는다면, 블룸 시계는 항상 그것을 추론할 수 있다. 즉, 잘못된 부정은 가능하지 않다.만약 두 개의 시계가 비교 가능하다면, 블룸 시계는 그 문장의 신뢰도를 계산할 수 있다. 즉, 비교 가능한 시계 쌍들 사이의 잘못된 양성률을 계산할 수 있다.

참고 항목

참조

  1. ^ "Distributed Systems 3rd edition (2017)". DISTRIBUTED-SYSTEMS.NET. Retrieved 2021-03-21.
  2. ^ 이 논문에 대한 언급은 린지 쿠퍼 교수에 의해 발견되었고, 그녀의 유튜브 비디오 강연 시리즈 23편의 분산 시스템에 대한 강연에서 설명되었다.
  3. ^ Barbara Liskov, Rivka Ladin (1986). "Highly-Available Distributed Services and Fault-Tolerant Distributed Garbage Collection". 5th Symposium on the Principles of Distributed Computing. ACM. pp. 29–39. CiteSeerX 10.1.1.569.3601. Retrieved 2020-09-22.
  4. ^ Colin J. Fidge (February 1988). "Timestamps in Message-Passing Systems That Preserve the Partial Ordering" (PDF). In K. Raymond (ed.). Proc. of the 11th Australian Computer Science Conference (ACSC'88). pp. 56–66. Retrieved 2009-02-13.
  5. ^ Mattern, F. (October 1988), "Virtual Time and Global States of Distributed Systems", in Cosnard, M. (ed.), Proc. Workshop on Parallel and Distributed Algorithms, Chateau de Bonas, France: Elsevier, pp. 215–226
  6. ^ Francisco Torres-Rojas; Mustaque Ahamad (1999), "Plausible clocks: constant size logical clocks for distributed systems", Distributed Computing, 12 (4): 179–195, doi:10.1007/s004460050065, S2CID 2936350
  7. ^ Agarwal, Anurag; Garg, Vijay K. (17 July 2005). "Efficient dependency tracking for relevant events in shared-memory systems" (PDF). Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery: 19–28. doi:10.1145/1073814.1073818. ISBN 1-58113-994-2. S2CID 11779779. Retrieved 21 April 2021.
  8. ^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Interval Tree Clocks: A Logical Clock for Dynamic Systems", in Baker, Theodore P.; Bui, Alain; Tixeuil, Sébastien (eds.), Principles of Distributed Systems (PDF), Lecture Notes in Computer Science, vol. 5401, Springer-Verlag, Lecture Notes in Computer Science, pp. 259–274, Bibcode:2008LNCS.5401.....B, doi:10.1007/978-3-540-92221-6, ISBN 978-3-540-92220-9
  9. ^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Interval Tree Clocks: A Logical Clock for Dynamic Systems", Interval Tree Clocks: A Logical Clock for Dynamic Systems, Lecture Notes in Computer Science, vol. 5401, p. 259, doi:10.1007/978-3-540-92221-6_18, hdl:1822/37748, ISBN 978-3-540-92220-9
  10. ^ Zhang, Yi (2014), "Background Preliminaries: Interval Tree Clock Results", Background Preliminaries: Interval Tree Clock Results (PDF)
  11. ^ Lum Ramabaja (2019), The Bloom Clock, arXiv:1905.13064, Bibcode:2019arXiv190513064R

외부 링크