자기안정화

Self-stabilization


자기 안정화는 분산형 시스템에서 내결함성의 개념이다. 초기 상태를 감안할 때, 자체 안정화 분산 시스템은 제한된 수의 실행 단계에서 올바른 상태로 끝나게 될 것이다.

얼핏 보면, 시스템이 특정 종류의 상태 전환 하에서 항상 올바른 상태로 유지된다는 것을 보장하는 것을 목적으로 하는, 보다 전통적인 알고리즘의 결함 강화보다 자기 안정화의 보장이 덜 유망해 보일 수 있다. 그러나 그러한 전통적인 내결함성이 항상 달성될 수는 없다. 예를 들어 시스템이 잘못된 상태에서 시작되거나 침입자에 의해 손상되었을 때는 달성할 수 없다. 게다가, 그것의 복잡성 때문에, 분산된 시스템을 디버깅하고 분석하는 것은 매우 어렵다. 따라서 분산형 시스템이 잘못된 상태에 도달하는 것을 막기란 매우 어렵다. 실제로, 알고리즘 설계에서 예측하지 못한 결함에 대처할 수 있는 능력을 주기 때문에, 몇몇 형태의 자기안정화가 많은 현대의 컴퓨터 및 통신 네트워크에 통합된다.

1974년 Edsger Dijkstra의 정논문 이후 여러 해 동안, 이 개념은 컴퓨터 시스템과 내결함성 시스템을 스스로 관리할 수 있는 중요한 토대를 제시하기 때문에 여전히 중요하다. 그 결과, Dijkstra의 논문은 분산 컴퓨팅 커뮤니티에서 가장 높은 인정 중 하나인 2002 ACM PODC 영향력-종이 상을 받았다.[1] 더구나 디즈크스트라의 사후 이 상의 명칭이 바뀌어 현재는 디즈크스트라 상으로 불린다.

역사

1974년 E.W. Dijkstra는 자기 안정화 개념을 제시하여 이 분야에 대한 추가 연구를 촉진하였다.[2] 그의 시연에는 자기 안정화 상호 배제 알고리즘의 제시가 포함되었다.[3] 또한 시스템에 대한 강한 가정에 의존하지 않는 최초의 자기안정 알고리즘을 보여주었다. 실제에 사용된 이전의 일부 프로토콜은 실제로 안정화되었지만, 시스템에 전역적인 시계의 존재를 가정하고 각 시스템 전환 기간에 대해 알려진 상한선을 가정했을 뿐이다. 연구자들이 이 우아한 결함-관용성 개념에 주의를 기울인 것은 레슬리 램포트가 1983년 분산 컴퓨팅의 원리에 관한 심포지엄이라는 회의에서 디즈크스트라의 연구의 중요성을 지적한 것이 불과 10년 후였다. 그의 강연에서 램포트는 다음과 같이 말했다.

나는 이것을 디크스트라의 가장 훌륭한 작품이라고 생각한다 - 적어도 그의 가장 훌륭한 출판 논문이다. 거의 완전히 알 수 없는 일이다. 내결함성에 대한 연구의 이정표라고 생각한다... 나는 자기 안정화가 내결함성에 있어서 매우 중요한 개념이며 연구를 위한 매우 비옥한 분야라고 생각한다.[3]

그 후, Dijkstra의 작품은 ACM-POPDC 영향력 있는 논문상을 수상하였고, 그 후 ACM(Association for Computing Machine) Dijkstra가 매년 열리는 ACM-POPDC 심포지엄에서 수여되는 분산 컴퓨팅 부문 Dijkstra 상이 되었다.[5]

개요

분산 알고리즘은 임의 상태에서 시작하여 합법적인 상태로 수렴하여 그 이후 합법적인 상태로 유지될 수 있는 경우에 자체 안정화된다. 이 상태에서 시작하여 알고리즘이 그 규격을 만족한다면 상태는 합법적이다. 자가 안정화의 속성은 분산 알고리즘이 그 성격에 관계없이 과도적 결함을 복구할 수 있게 한다. 더욱이 자기안정화 알고리즘은 결국 초기 상태에 관계없이 올바르게 동작하기 시작하므로 초기화할 필요가 없다.

자기안정화 개념을 소개하는 디즈크스트라의 논문은 원형으로 주문된 컴퓨터 네트워크인 '토큰 고리'의 맥락에서 예를 제시한다. 여기서 각 컴퓨터 또는 프로세서는 바로 앞에 있는 하나의 프로세서의 전체 상태를 "보기"할 수 있으며, 이 상태는 프로세서가 "토큰"을 가지고 있거나 "토큰"을 가지고 있지 않음을 의미할 수 있다.[5] 요구 사항 중 [6]하나는 정확히 그 중 하나가 주어진 시간에 "증표를 가지고 있어야 한다"는 것이다. 두 번째 요건은 토큰이 결국 링을 순환하도록 각 노드가 이를 이어받는 컴퓨터/프로세서에 " 토큰을 전달"하도록 규정한다.[5][6]

  • 토큰을 보유하지 않는 것은 토큰을 다른 컴퓨터에서 보유할 수 있기 때문에 이 네트워크의 각 컴퓨터에 대한 올바른 상태 입니다. 그러나 모든 컴퓨터가 " 토큰을 보유하지 않는" 상태라면, 네트워크는 완전히 올바른 상태가 아니다.
  • 마찬가지로, 둘 이상의 컴퓨터가 " 토큰을 보유"하는 경우, 이것은 네트워크에 대한 올바른 상태가 아니다. 단, 어떤 컴퓨터를 개별적으로 보더라도 잘못된 것으로 관찰될 수는 없다. 모든 컴퓨터는 두 이웃의 상태만을 "관찰"할 수 있기 때문에, 컴퓨터가 네트워크가 모두 정확한 상태인지 여부를 결정하기가 어렵다.

첫 번째 자체 안정화 알고리즘은 후속적으로 오류를 복구하기 위해 명시적으로 감지하지 않았다. 대신 그들은 끊임없이 이 제도를 합법적인 상태로 밀어붙였다. 전통적인[7] 오류 감지 방법은 종종 매우 어렵고 시간이 많이 걸리기 때문에, 그러한 행동은 바람직한 것으로 여겨졌다. (위에서 인용한 논문에서 기술한 방법은 네트워크 전체에서 한 곳으로 엄청난 양의 정보를 수집하고, 그 이후에는 수집된 글로벌 상태가 정확한지 여부를 판단하려고 시도한다. 그 결정만으로도 어려운 과제가 될 수 있다.)

효율성 향상

보다 최근에, 연구자들은 국소 검사를 이용한 자가 안정화 시스템과 일반 업무를 위한 경량 오류 검출에 대한 새로운 방법을 제시하였다.[8][9][10]

로컬이라는 용어는 컴퓨터 네트워크의 일부를 가리킨다. 로컬 탐지를 사용할 때, 오류를 감지하기 위해 네트워크 내의 컴퓨터는 전체 네트워크와 통신할 필요가 없다. 즉, 각 컴퓨터가 가장 가까운 이웃들과만 통신하도록 함으로써 오류를 탐지할 수 있다. 이러한 국소 탐지 방법은 자기안정 알고리즘 설계 작업을 상당히 단순화하였다. 오류 감지 메커니즘과 복구 메커니즘을 별도로 설계할 수 있기 때문이다. 이러한 검출 방법에 기초한 새로운 알고리즘도 훨씬 더 효율적인 것으로 나타났다. 더욱이, 이 논문들은 비자기 안정화 알고리즘을 자기 안정화 알고리즘으로 변환하기 위해 다소 효율적인 일반 변압기를 제안하였다. 그 아이디어는,

  1. 비자율 안정화 프로토콜을 동시에 실행하십시오.
  2. 위에서 언급한 탐지 방법을 사용하여 (주어진 프로토콜의 실행 중) 결함을 탐지한다.
  3. 그런 다음 (자체 안정화) "자동 안정화" 프로토콜을 적용하여 시스템을 미리 결정된 초기 상태로 되돌리고, 마지막으로,
  4. 지정된 (자율 안정화되지 않은) 프로토콜을 재시작하십시오.

이 4개 부품의 조합은 자체 안정화(예를 들어, 보정 결함 단계 중 결함 트리거가 없는 한)이다.[11] 초기 자기 안정화 프로토콜도 상기 논문에서 제시되었다. 예를 들어, 보다 효율적인 재설정 프로토콜이 나중에 제시된 예는 다음과 같다.[12]

시간적응 프로토콜의 개념으로 추가적인 효율성이 도입되었다.[13] 이러한 이면의 아이디어는 적은 수의 오류만 발생할 때 복구 시간이 단축될 수 있고(그리고) 짧아야 한다는 것이다. Dijkstra의 원래 자기안정 알고리즘은 이 속성을 가지고 있지 않다.

자기안정 알고리즘의 유용한 특성은 계층들이 순환 종속성을 보이지 않는 경우 계층들로 구성될 수 있다는 것이다. 구성의 안정화 시간은 각 층의 개별 안정화 시간의 합으로 제한된다.[6]

전략 게임의 표준 개념, 특히 개선 경로의 개념을 사용하여 어떻게 자기 안정화가 자연스럽게 형성될 수 있는지를 보여준 크라이즈토프 아파트와 에산 쇼자의 제안과 같은 디즈크스트라의 작업에 대한 새로운 접근법이 나중에 등장했다. [14] 이 특별한 작품은 자기 안정화와 게임 이론의 연관성을 증명하기 위해 노력했다.

시간 복잡성

자기안정화 알고리즘의 시간 복잡성은 (비동기) 라운드 또는 사이클로 측정한다.

  • 라운드(round)는 각 프로세서가 적어도 한 단계 이상을 실행하는 최단 실행 트레이스다.
  • 마찬가지로, 사이클은 각 프로세서가 반복적으로 실행된 명령 목록을 적어도 하나의 완전한 반복을 실행하는 최단 실행 추적이다.

출력 안정화 시간을 측정하기 위해 상태 변수의 하위 집합이 외부로 보이도록 정의된다(출력). 출력의 특정 상태는 정확하도록 정의된다(합법적이다). 시스템의 모든 구성 요소의 출력 세트는 추가 고장이 발생하지 않는 한 무기한 정확성을 유지한다면 정확해지기 시작하는 시점에 안정되었다고 한다. 출력 안정화 시간은 출력이 안정화될 때까지의 시간(비동기)이다.[8]

정의

시스템은 다음과 같은 경우에만 자체 안정화된다.

  1. 어떤 상태로부터 시작해도, 시스템은 결국 정확한 상태(융합)에 도달할 것이라고 보장한다.
  2. 시스템이 올바른 상태에 있다는 점을 감안하여 고장이 발생하지 않는 한(폐쇄) 올바른 상태를 유지할 것을 보장한다.

시스템이 자체 안정화되고 올바른 상태에 도달하기 위해 필요한 라운드 수가 일정한 에 의해 제한되는 경우에만 시스템이 임의로 자체 안정화된다고 한다[15]

이상과 같은 의미에서의 자기안정화 설계는 어려운 일로 잘 알려져 있다. 사실, 분산 알고리즘의 종류는 로컬 체크의 속성을 가지고 있지 않다: 네트워크 상태의 합법성은 단일 프로세스로 평가될 수 없다. 가장 명백한 사례는 위에서 정의한 Dijkstra의 토큰링이다. 즉, 비근접 프로세스에 둘 이상의 토큰이 존재하는 경우에는 어떠한 프로세스도 네트워크 상태가 합법적인지 여부를 감지할 수 없다. 이는 분산형 시스템의 자기안정화가 일종의 집단지성이라는 것을 시사하는데, 각 구성요소가 그 지역지식에 근거해 국지적인 행동을 취하지만 결국 이것은 결국 글로벌 융합을 보장한다.

위에서 정의한 자기안정화 설계의 난이도를 극복하기 위해 다른 유형의 안정화를 고안하였다. 예를 들어, 약한 안정화는 분산 시스템이 가능한 모든 상태에서 그것의 합법적인 행동에 도달할 수 있는 가능성을 가진 재산이다.[16] 안정성이 약하면 모든 주행에 대한 수렴보다는 분산 시스템의 일부 주행에 대한 수렴 가능성만 보장하므로 설계가 용이하다.

자기안정화 알고리즘은 알고리즘에 의해 사용되는 통신 레지스터의 값이 고정된 상태로 유지되는 글로벌 상태로 수렴되는 경우에만 침묵한다.[17]

관련업무

자기안정화 개념의 연장은 초안정화 개념이다.[18] 여기서의 목적은 위상적 변화를 겪는 동적 분산 시스템에 대처하는 것이다. 고전적 자기안정론에서 임의변경은 시스템이 다시 안정될 때까지 보증이 주어지지 않는 오류로 본다. 초안정화 시스템에서는 시스템 토폴로지를 재구성하는 동안 항상 충족되는 통로 술어가 있다.

참조

  1. ^ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 2009-09-01
  2. ^ Dijkstra, Edsger W. (1974), "Self-stabilizing systems in spite of distributed control" (PDF), Communications of the ACM, 17 (11): 643–644, doi:10.1145/361179.361202.
  3. ^ a b Dolev, Shlomi (2000). Self-stabilization. Cambridge, MA: The MIT Press. p. 3. ISBN 978-0262041782.
  4. ^ Lamport, Leslie (1985), "Solved problems, unsolved problems, and non-problems in concurrency" (PDF), ACM Special Interest Group Operating Systems Review, 19 (4): 34–44, doi:10.1145/858336.858339.
  5. ^ a b c Chaudhuri, Soma; Das, Samir; Paul, Himadri; Tirthapura, Srikanta (2007). Distributed Computing and Networking: 8th International Conference, ICDCN 2006, Guwahati, India, December 27-30, 2006, Proceedings. Berlin: Springer. p. 108. ISBN 978-3540681397.
  6. ^ a b c Shlomi Dolev, Shlomo Moran, Amos 이스라엘: 읽기/쓰기 원자성만 가정하는 동적 시스템의 자체 안정화. 분산 컴퓨팅, 제7권, 페이지3–16(1993).
  7. ^ Katz, Shmuel; Perry, Kenneth J. (1993), "Self-stabilizing extensions for meassage-passing systems", Distributed Computing, 7 (1): 17–26, doi:10.1007/BF02278852.
  8. ^ a b Awerbuch, Baruch; Patt-Shamir, Boaz; Varghese, George (1991), "Self-stabilization by local checking and correction", Proc. 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268–277, CiteSeerX 10.1.1.211.8704, doi:10.1109/SFCS.1991.185378, ISBN 978-0-8186-2445-2.
  9. ^ Afek, Yehuda; Kutten, Shay; Yung, Moti (1997), "The local detection paradigm and its applications to self-stabilization", Theoretical Computer Science, 186 (1–2): 199–229, doi:10.1016/S0304-3975(96)00286-1, MR 1478668.
  10. ^ Shlomi Dolev, 예후다 Afek: 지역 스태빌라이저. 병렬 및 분산 컴퓨팅 책 62권, 2002년 5월 5일자 745-765페이지.
  11. ^ 바룩 아워부치, 보아스 팻 샤미르, 조지 바르게세, 슐로미 돌레브 로컬 확인 및 글로벌 재설정에 의한 자체 안정화. WDAG 1994: 326-339.
  12. ^ [바룩 아워부치, 샤이 쿠텐, 이세이 만수르, 보아스 팻 샤미르, 조지 바르게세. 시간 최적 자가 안정화 동기화. ACM STOC 1993: 652-661].
  13. ^ 샤이 쿠텐, 보아즈 팻 샤미르: 시간 적응 프로토콜 안정화. 이론. 계산. Sci. 220(1): 93-111(1999년).
  14. ^ de Boer, Frank; Bonsangue, Marcello; Rutten, Jan (2018). Apt. Cham: Springer. p. 22. ISBN 9783319900889.
  15. ^ Dolev, Shlomi (2000), Self-Stabilization, MIT Press, ISBN 978-0-262-04178-2.
  16. ^ Gouda, Mohamed (1995), > The Triumph and Tribulation of System Stabilization, Proceedings of the 9th international workshop on distributed algorithms..
  17. ^ 슐로미 돌레브, 모하메드 G. 고다, 마르코 슈나이더. 무음 안정화를 위한 메모리 요구 사항. PODC '96: 분산 컴퓨팅의 원리에 관한 제15회 연례 ACM 심포지엄의 진행, 27-34페이지 뉴욕, 뉴욕, 미국, 1996페이지. ACM Press. 온라인 확장 추상.
  18. ^ Dolev, Shlomi; Herman, Ted (1997), "Superstabilizing protocols for dynamic distributed systems", Chicago Journal of Theoretical Computer Science, 3: 1–40, doi:10.4086/cjtcs.1997.004, 제4조.

외부 링크

  • libcircle - 해지를 위한 토큰 패싱을 사용한 자기 안정화의 구현.