원자 방송

Atomic broadcast

폴트 톨러런스 분산 컴퓨팅에서 아토믹브로드캐스트 또는 토탈 오더브로드캐스트는 여러 프로세스로 이루어진 시스템 내의 모든 올바른 프로세스가 같은 순서로 같은 메시지세트(즉,[1][2] 같은 시퀀스의 메시지)를 수신하는 브로드캐스트입니다.방송은 결국 모든 참가자에게 올바르게 완료되거나 부작용 없이 모든 참가자가 중단되기 때문에 "원자성"이라고 불립니다.원자방송은 중요한 분산 컴퓨팅 프리미티브입니다.

특성.

일반적으로 다음 속성은 원자 브로드캐스트 프로토콜에서 필요합니다.

  1. 유효성: 올바른 참가자가 메시지를 브로드캐스트하면 올바른 참가자 모두가 최종적으로 메시지를 수신합니다.
  2. Uniform Agreement(일률적인 계약): 1명의 올바른 참가자가 메시지를 수신하면, 최종적으로 모든 올바른 참가자가 그 메시지를 수신합니다.
  3. 균일 무결성: 메시지가 각 참가자에 의해 수신되는 것은 이전에 브로드캐스트된 경우뿐입니다.
  4. Uniform Total Order: 메시지는 수학적인 의미에서 완전히 정렬됩니다.즉, 올바른 참가자가 메시지1을 먼저 수신하고 메시지2를 수신한 경우, 다른 모든 올바른 참가자는 메시지2보다 먼저 메시지1을 수신해야 합니다.

Rodrigues, Raynal[3],[4] Schiper 등은 원자 방송의 무결성과 타당성 특성을 약간 다르게 정의한다.

합계 순서는 FIFO 순서와 동일하지 않습니다.즉, 프로세스가 메시지2 를 송신하기 전에 메시지1 을 송신했을 경우는, 모든 참가자가 메시지2 를 수신하기 전에 메시지1 을 수신할 필요가 있습니다.또한 메시지 2가 메시지 1에 의존하거나 메시지 1 후에 발생하는 경우 메시지 1을 수신한 후 모든 참가자가 메시지 2를 수신해야 하는 '원인 명령'과도 일치하지 않습니다.토탈 오더는 강력하고 유용한 조건이지만 모든 참가자가 같은 순서로 메시지를 수신해야 하며, 그 [5]오더에 다른 제약은 가하지 않습니다.

폴트 톨러런스

컴퓨터가 고장나지 않는다고 가정할 수 있다면 원자 방송의 알고리즘을 설계하는 것은 비교적 쉽습니다.예를 들어, 장애가 없는 경우, 모든 참가자가 메시지의 순서를 결정하는 하나의 "리더"와 통신하고 다른 참가자는 리더를 따르는 것만으로 원자성 브로드캐스트를 실현할 수 있습니다.

그러나 실제 컴퓨터에는 장애가 있습니다.예측할 수 없는 시기, 경우에 따라서는 부적절한 시기에 장애가 발생하고 장애가 복구됩니다.예를 들어, Follow-the-leader 알고리즘에서는 리더가 잘못된 시간에 실패하면 어떻게 됩니까?그러한 환경에서는 원자방송을 실현하는 것이 [1]어렵다.네트워크, 장애 모델, 멀티캐스트를 위한 하드웨어 지원의 가용성 등에 관한 다양한 가정 하에서 원자 브로드캐스트를 수행하기 위해 많은 프로토콜이 제안되어 왔다.[2]

컨센서스와 동등

아토믹 브로드캐스트의 조건을 만족시키기 위해서는, 참가자는 메시지의 수신 순서에 대해서 효과적으로 「동의」할 필요가 있습니다.다른 참가자가 주문을 "동의"하고 메시지 수신을 시작한 후 장애로부터 회복하는 참가자는 합의된 주문을 학습하고 준수할 수 있어야 합니다.이러한 고려사항은 크래시 장애가 있는 시스템에서는 원자 방송과 컨센서스가 동등한 [6]문제임을 나타냅니다.

값을 원자적으로 브로드캐스트함으로써 합의를 위한 프로세스에 의해 제안할 수 있고, 프로세스는 원자적으로 수신한 첫 번째 메시지의 값을 선택함으로써 값을 결정할 수 있다.따라서 컨센서스는 아토믹 브로드캐스트로 축소할 수 있습니다.

반대로 참가자 그룹은 수신하는 첫 번째 메시지에 대한 합의를 얻어 다음 메시지에 대한 합의를 얻어 모든 메시지를 수신할 때까지 메시지를 원자적으로 브로드캐스트할 수 있습니다.따라서 아토믹 브로드캐스트는 컨센서스로 환원됩니다.이것은 자비에르 데파고 [2]등에 의해 더욱 공식적이고 상세하게 증명되었다.

분산 컴퓨팅의 기본적인 결과는 대부분의 경우 하나의 크래시 장애라도 발생할 수 있는 비동기 시스템에서 합의를 도출하는 것은 불가능하다는 것입니다.이것은 1985년에 Michael J.에 의해 증명되었다. Fischer, Nancy Lynch 및 Mike Paterson은 FLP [7]결과라고 불리기도 합니다.컨센서스와 아토믹브로드캐스트는 동등하기 때문에 FLP는 [5]아토믹브로드캐스트에도 적용됩니다.FLP 결과에 따라 실제로 원자성 브로드캐스트의 실장이 금지되지는 않지만 프로세서나 통신 타이밍 등 몇 가지 점에서 FLP보다 덜 엄격한 가정을 할 필요가 있습니다.

알고리즘

Chandra-Toug[6] 알고리즘은 원자 방송에 대한 합의 기반 솔루션입니다.Rodrigues와 Raynal에 [3]의해 또 다른 해결책이 제시되었다.

Zookeeper Atomic Broadcast(ZAB) 프로토콜은 Apache ZooKeeper를 위한 기본 구성 요소이며, Hadoop과 다른 많은 중요한 분산 [8][9]시스템의 기반이 되는 내결함성 분산 조정 서비스입니다.

Ken Birman은 모든 프로세스가 동일한 순서로 동일한 이벤트를 관찰하는 분산 시스템을 위한 가상 동기 실행 모델을 제안했습니다.수신되는 메시지의 총 순서는 아토믹브로드캐스트와 마찬가지로 거의 동기화된 메시지 수신을 실현하기 위한 방법 중 하나입니다(단, 유일한 방법은 아닙니다).

레퍼런스

  1. ^ a b Kshemkalyani, Ajay; Singhal, Mukesh (2008). Distributed Computing: Principles, Algorithms, and Systems (Google eBook). Cambridge University Press. pp. 583–585. ISBN 9781139470315.
  2. ^ a b c Défago, Xavier; Schiper, André; Urbán, Péter (2004). "Total order broadcast and multicast algorithms" (PDF). ACM Computing Surveys. 36 (4): 372–421. doi:10.1145/1041680.1041682.
  3. ^ a b Rodrigues L, Raynal M.: 비동기 크래시 복구 분산 시스템에서의 원자력 방송[1], ICDCS '00: 제20회 분산 컴퓨팅 시스템 국제회의의 진행 상황 (ICDCS 2000)
  4. ^ Ekwall, R.; Schiper, A. (2006). "Solving Atomic Broadcast with Indirect Consensus". International Conference on Dependable Systems and Networks (DSN'06) (PDF). pp. 156–165. doi:10.1109/dsn.2006.65. ISBN 0-7695-2607-1.
  5. ^ a b Dermot Kelly. "Group Communication".
  6. ^ a b Chandra, Tushar Deepak; Toueg, Sam (1996). "Unreliable failure detectors for reliable distributed systems". Journal of the ACM. 43 (2): 225–267. doi:10.1145/226643.226647.
  7. ^ Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson (1985). "Impossibility of Distributed Consensus with One Faulty Process" (PDF). Journal of the ACM. 32 (2): 374–382. doi:10.1145/3149.214121.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  8. ^ Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini, Yahoo! Research (2011). "Zab: High-performance broadcast for primary-backup systems". 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN). pp. 245–256. doi:10.1109/DSN.2011.5958223. ISBN 978-1-4244-9233-6. S2CID 206611670.{{cite book}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  9. ^ André Medeiros (March 20, 2012). "ZooKeeper's atomic broadcast protocol: Theory and practice" (PDF). Helsinki University of Technology - Laboratory of Theoretical Computer Science.