분산 알고리즘

Distributed algorithm

분산 알고리즘은 상호 연결된 프로세서로 구성된 컴퓨터 하드웨어에서 실행되도록 설계된 알고리즘이다. 분산 알고리즘은 통신, 과학 컴퓨팅, 분산 정보 처리, 실시간 프로세스 제어 등 분산 컴퓨팅의 다른 응용 분야에서 사용된다. 분산 알고리즘으로 해결되는 표준 문제로는 지도자 선출, 합의, 분산 검색, 스패닝 트리 생성, 상호 배제, 자원 할당 등이 있다.[1]

분산 알고리즘은 병렬 알고리즘의 하위 유형으로, 일반적으로 동시에 실행되며, 알고리즘의 개별 부분은 독립 프로세서에서 동시에 실행되며, 알고리즘의 다른 부분이 수행하는 작업에 대한 정보가 제한되어 있다. 분산 알고리즘을 개발하고 구현하는 데 있어 중요한 과제 중 하나는 프로세서 장애와 신뢰할 수 없는 통신 링크에 직면하여 알고리즘의 독립된 부분의 동작을 성공적으로 조정하는 것이다. 주어진 문제를 해결하기 위한 적절한 분산 알고리즘의 선택은 문제의 특성과 알고리즘이 실행될 시스템의 특성, 프로세서 또는 링크 장애의 유형과 확률, 수행할 수 있는 프로세스 간 통신의 종류, 동기화의 수준 등에 따라 달라진다.개별 공정 간의 [1]차이

표준 문제

원자 커밋
원자핵 커밋은 일련의 구별되는 변화들이 하나의 연산으로 적용되는 연산이다. 만약 원자력이 성공한다면, 그것은 모든 변화가 적용되었다는 것을 의미한다. 원자력이 커밋을 완료하기 전에 오류가 발생하면 "커밋"이 중단되고 변경 사항이 적용되지 않는다.
원자 커밋 프로토콜을 해결하기 위한 알고리즘은 2상 커밋 프로토콜과 3상 커밋 프로토콜을 포함한다.
컨센서스
합의 알고리즘은 공통의 결정에 동의하는 다수의 프로세스의 문제를 해결하려고 노력한다.
더 정확히 말하면, 컨센서스 프로토콜은 아래의 네 가지 공식 특성을 만족시켜야 한다.
  • 종료: 모든 올바른 과정이 어떤 가치를 결정한다.
  • 유효성: 모든 프로세스가 동일한 값 을(를 제안할 경우, 모든 올바른 프로세스가 을(를) 결정한다
  • 무결성: 모든 올바른 프로세스에서 최대 하나의 값을 결정하며, v displaystyle v}, 어떤 프로세스에서 {\을(를) 제안했을 것이다.
  • 동의: 올바른 프로세스가 을(를 결정하는 경우, 모든 올바른 프로세스가 을(를) 결정한다
합의문 해결을 위한 공통 알고리즘은 팍소스 알고리즘과 래프트 알고리즘이다.
분산 검색
지도자 선거
리더 선거는 단일 프로세스를 여러 대의 컴퓨터(노드)에 분산된 일부 작업의 주관자로 지정하는 과정이다. 작업이 시작되기 전에 모든 네트워크 노드는 작업의 "리더" 또는 조정자 역할을 할 노드를 알지 못한다. 그러나 지도자 선거 알고리즘이 실행된 후, 네트워크 전체의 각 노드는 태스크 리더로서 특정한 고유한 노드를 인식한다.
상호배제
비차단 데이터 구조
신뢰할 수 있는 브로드캐스트
신뢰할 수 있는 방송은 분산형 시스템에서 원시적인 통신이다. 신뢰할 수 있는 브로드캐스트는 다음 속성으로 정의된다.
  • 타당성 - 올바른 프로세스가 메시지를 보낸다면, 어떤 올바른 프로세스는 결국 메시지를 전달할 것이다.
  • 동의 - 올바른 프로세스가 메시지를 전달하면 모든 올바른 프로세스가 결국 메시지를 전달한다.
  • 무결성 - 모든 올바른 프로세스는 한 프로세스에 의해 해당 메시지가 전송된 경우에만 최대 한 번에 동일한 메시지를 전달한다.
신뢰할 수 있는 방송은 순차적, 인과적 또는 전체 순서를 가질 수 있다.
복제
자원할당
스패닝 트리 생성
대칭 파괴(예: 정점 염색)

참조

  1. ^ a b Lynch, Nancy (1996). Distributed Algorithms. San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1-55860-348-6.

추가 읽기

외부 링크