맨위로가기 타임라인 바로가기

분산 컴퓨팅

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
타임라인 바로가기
목차

1. 개요

분산 컴퓨팅은 여러 대의 컴퓨터를 네트워크로 연결하여 하나의 작업을 분담 처리하는 기술을 의미한다. 1960년대 운영 체제 연구에서 시작되어 인터넷의 발달과 함께 발전해왔으며, 병렬 컴퓨팅과 밀접한 관련을 가진다. 분산 시스템은 공유 메모리 대신 각 프로세서가 전용 메모리를 사용하며 메시지 전달을 통해 정보를 교환하는 특징을 갖는다.

분산 컴퓨팅은 클라이언트-서버, P2P 등 다양한 아키텍처를 사용하며, 고신뢰성, 저렴함 등의 이점을 제공하지만, 보안 취약성, 네트워크 부하 증가, 기술적 문제 등의 단점도 존재한다. 분산 알고리즘 연구는 계산 문제 해결과 효율성을 다루며, 병렬 알고리즘, 분산 알고리즘 모델을 사용한다.

분산 컴퓨팅은 통신, 네트워크 응용 프로그램, 실시간 프로세스 제어, 병렬 컴퓨팅 등 다양한 분야에 활용되며, 4차 산업혁명 시대의 핵심 기술로 부상하고 있다. BOINC, distributed.net, Folding@home 등과 같이 일반 사용자의 참여를 통해 과학 연구를 수행하는 분산 컴퓨팅 프로젝트도 활발히 진행되고 있다.

2. 역사

메시지 전달을 통해 통신하는 병행 프로세스 이용은 1960년대 운영 체제 구조 연구에서 그 뿌리를 찾을 수 있다.[77] 1970년대에는 이더넷과 같은 근거리 통신망이 발명되면서 분산 시스템이 널리 사용되기 시작했다.[78]

1960년대 말 인터넷의 전신인 ARPANET이 도입되었고, 1970년대 초에는 ARPANET 이메일이 발명되었다. 이메일은 ARPANET의 가장 성공적인 애플리케이션이자,[79] 대규모 분산 애플리케이션의 초기 사례로 꼽힌다. ARPANET 외에도 1980년대 Usenet과 FidoNet 등 분산 토론 시스템을 지원하는 전 세계 컴퓨터 네트워크가 등장했다.[30]

1970년대 후반과 1980년대 초, 분산 컴퓨팅 연구는 컴퓨터 과학의 별도 분야로 자리 잡았다. 1982년 분산 컴퓨팅 원리 심포지엄(PODC)이 처음 개최되었고, 1985년에는 오타와에서 그래프의 분산 알고리즘에 관한 국제 워크숍을 시작으로 국제 분산 컴퓨팅 심포지엄(DISC)이 개최되었다.[31]

3. 병렬 컴퓨팅과의 관계

병행 컴퓨팅, 병렬 컴퓨팅, 분산 컴퓨팅은 서로 겹치는 부분이 많아 명확하게 구분하기 어렵다.[76] 같은 시스템이라도 "병렬" 또는 "분산"으로 특징지을 수 있으며, 일반적인 분산 시스템의 프로세서는 동시에 병렬적으로 실행된다.[22]

그럼에도 불구하고, 다음 기준을 사용하여 동시 시스템을 대략 "병렬" 또는 "분산"으로 분류할 수 있다.



(a), (b): 분산 시스템.
(c): 병렬 시스템


오른쪽 그림은 분산 시스템과 병렬 시스템의 차이점을 나타낸다. 그림 (a)와 (b)는 분산 시스템으로, 각 노드는 컴퓨터이고 노드를 연결하는 선은 통신 링크이다. 각 컴퓨터는 자체 로컬 메모리를 가지며, 통신 링크를 통해 메시지를 전달하여 정보를 교환한다. 그림 (c)는 병렬 시스템으로, 각 프로세서가 공유 메모리에 직접 접근할 수 있다.

병렬 컴퓨팅은 밀접하게 결합된 형태의 분산 컴퓨팅으로 볼 수 있으며,[23] 분산 컴퓨팅은 느슨하게 결합된 형태의 병렬 컴퓨팅으로 볼 수 있다.[12] 공유 메모리 멀티프로세서에서는 고성능 병렬 계산을 위해 병렬 알고리즘을 사용하고, 대규모 분산 시스템의 조정에는 분산 알고리즘을 사용한다.[26]

4. 아키텍처

분산 컴퓨팅에는 다양한 하드웨어 및 소프트웨어 아키텍처가 사용된다. CPU 공유 여부에 따라 공유 메모리, 공유 디스크, 공유 없음 아키텍처로 구분할 수 있다.[32]

분산 프로그래밍은 일반적으로 다음 기본 아키텍처 중 하나를 따른다.[33]


  • 클라이언트-서버: 클라이언트가 서버에 데이터를 요청하고, 서버는 데이터를 처리하여 사용자에게 제공한다.
  • 3계층: 클라이언트, 애플리케이션 서버, 데이터베이스 서버로 구성되며, 무상태 클라이언트를 사용할 수 있어 애플리케이션 배포가 용이하다. 대부분의 웹 애플리케이션은 3계층이다.
  • n-계층: 웹 애플리케이션에서 주로 사용되며, 요청을 다른 엔터프라이즈 서비스로 전달한다.
  • 피어 투 피어: 중앙 서버 없이 모든 참여자(피어)가 동등하게 서비스를 제공하고 관리한다.[34] 피어는 클라이언트와 서버 역할을 모두 할 수 있다.[35] 비트토렌트와 비트코인 네트워크가 이 아키텍처의 예시이다.
  • 밀결합(클러스터): 고속 네트워크로 연결된 여러 컴퓨터가 밀접하게 협력하여 작업을 처리한다.


프로세스 간 통신 및 조정을 위해 다양한 메시지 전달 프로토콜, "데이터베이스 중심" 아키텍처 등이 사용된다.[36][37]

분산 시스템은 작업을 위해 공통의 목표를 공유하는 네트워크로 연결된 컴퓨터 그룹이다.

"동시 컴퓨팅", "병렬 컴퓨팅", "분산 컴퓨팅" 용어는 상당 부분 겹치며, 이들 간에 명확한 구분이 존재하지 않는다.[21] 동일한 시스템이 "병렬" 및 "분산"으로 모두 특징지어질 수 있으며, 전형적인 분산 시스템의 프로세서는 병렬적으로 동시에 실행된다.[22] 병렬 컴퓨팅은 특히 밀접하게 결합된 형태의 분산 컴퓨팅으로 볼 수 있으며,[23] 분산 컴퓨팅은 느슨하게 결합된 형태의 병렬 컴퓨팅으로 볼 수 있다.[12] 그럼에도 불구하고, 다음 기준을 사용하여 동시 시스템을 "병렬" 또는 "분산"으로 대략적으로 분류할 수 있다.

  • 병렬 컴퓨팅에서 모든 프로세서는 프로세서 간 정보를 교환하기 위해 공유 메모리에 접근할 수 있다.[24]
  • 분산 컴퓨팅에서 각 프로세서는 자체 전용 메모리(분산 메모리)를 가지고 있다. 정보는 프로세서 간에 메시지를 전달하여 교환된다.[25]

5. 구성

컴퓨터 간의 상호 작용을 조직하고 체계화하는 것이 중요하다. 다양한 컴퓨터를 이용 가능하게 하려면, 통신 프로토콜이나 통신 경로에 특정 머신이 인식할 수 없는 정보가 포함되어서는 안 된다. 메시지가 올바르게 배포되도록 특히 주의를 기울여야 하며, 부정확한 메시지가 있으면 시스템이나 네트워크가 동작 불능이 될 위험성이 있으므로 이를 거부해야 한다.

또 다른 중요한 요인은 소프트웨어를 컴퓨터에서 컴퓨터로 전송하는 기능이며, 이를 통해 전송된 컴퓨터가 기존 네트워크와 상호 작용할 수 있게 된다. 아키텍처가 다르면 이것이 불가능한 경우가 있으며, 크로스 컴파일러 등을 사용한 이식이 필요하게 된다.

6. 목표 및 이점

분산 컴퓨팅 시스템은 다양한 형태를 띤다. 분산 컴퓨팅의 주된 목표는 투명하고 개방적이며 확장성 있는 방식으로 사용자 그룹과 리소스 그룹을 연결하는 것이다.[38] 이상적으로는 독립형 시스템들의 단순한 조합보다 더 결함 감내성 있고 강력한 시스템이 될 것으로 기대된다.[38]

분산 컴퓨팅은 다음과 같은 이점을 가진다.


  • '''고신뢰성''': 일부 구성 요소에 장애가 발생해도 전체 시스템은 계속 작동할 수 있다.
  • '''저렴함''': 여러 대의 저비용 컴퓨터를 활용하여 고비용의 단일 고성능 컴퓨터를 대체할 수 있다. (\[\[그로시의 법칙]](''컴퓨터 성능 ∝ 비용2'')이 깨짐)
  • '''확장성''': 시스템의 규모를 쉽게 확장하거나 축소할 수 있다.


한국에서는 분산 컴퓨팅의 이점을 활용하여 대규모 데이터 처리, 과학 기술 연구, 금융 서비스 등 다양한 분야에서 혁신을 이루고 있다.

6. 1. 오픈성

분산 시스템의 오픈성은 각 서브 시스템이 다른 시스템과의 상호 작용에 대해 지속적으로 열려 있음을 의미한다. 웹 서비스와 통신 프로토콜은 분산 시스템을 확장하고 확대할 수 있게 해주는 표준이다. 일반적으로, 확장성이 있는 오픈 시스템은 자체 완결형의 완전한 폐쇄 시스템보다 우수하다.

오픈 분산 시스템은 다음과 같은 특성을 가진다.

  • '''단조성:''' 오픈 시스템 상에서 어떤 것이 공개되면, 이를 취소할 수 없다.
  • '''다중성:''' 오픈 분산 시스템의 개별 서브 시스템은 이질적이고 중복되며, 경우에 따라서는 경쟁하는 정보를 포함한다. 중심이 되는 조정 기능은 오픈 분산 시스템에는 존재하지 않는다.
  • '''무제한적인 비결정성:''' 오픈 분산 시스템에서는 개별 서브 시스템이 비동기적으로 시작되거나 종료되며, 서브 시스템 간의 통신 링크도 비동기적으로 연결되거나 끊어진다. 따라서, 어떤 처리가 완료되는 시간을 예측할 수 없다.


한국에서는 개방형 API(Application Programming Interface)를 통해 다양한 서비스 간의 연동을 지원하고, 분산 시스템의 유연성과 확장성을 높이고 있다.

7. 문제점


  • 불특정 다수 또는 특정 다수의 컴퓨터에 처리를 맡기기 때문에 보안 측면에서 취약해지기 쉽다.
  • 데이터를 분배, 수집, 집계하기 위한 네트워크 부하가 증가한다.
  • 일반 참여자를 모집하는 경우, 지원자가 적으면 처리 속도가 늦어진다.
  • 계획에 결함이 있으면 분산 시스템 전체의 계산 신뢰성이 저하되고 노드 다운으로 인해 다른 노드도 작동 불능 상태에 빠질 수 있다. 레슬리 램포트는 "분산 시스템은 그런 장애가 있을 것이라고는 생각지도 못한 장애로 인해 이용 불가능해지는 시스템이다"라고 말했다.[72]
  • 분산 시스템에서의 문제 해결 및 진단은 점점 더 어려워지고 있다. 문제의 원인을 파악하려면 원격 노드에 연결해야 하고, 노드 간의 통신 내용을 조사해야 한다.
  • 분산 환경에 적합하지 않은 계산 종류도 많다. 특히 통신량이 많아지거나 동기가 필요한 것은 적합하지 않다. 필요한 대역폭이 너무 크고 지연 시간이 적을수록 좋은 경우에는 분산 컴퓨팅은 부적절하며, 분산되지 않은 환경이 성능이 더 좋을 것으로 예상된다.

8. 설계 사상 (아키텍처)

분산 컴퓨팅에서는 다양한 하드웨어 및 소프트웨어 설계 사상(아키텍처)이 사용된다. 크게 저수준과 고수준으로 나눌 수 있다.[32]


  • '''저수준 설계 사상(아키텍처)''': 복수의 CPU를 네트워크로 상호 접속해야 한다. 이 네트워크는 기판에 프린트된 회로일 수도 있고, 느슨하게 결합된 기기와 케이블의 집합체일 수도 있다.[32]

  • '''고수준 설계 사상(아키텍처)''': 통신 시스템으로 개별 컴퓨터에서 동작하는 프로세스를 상호 접속해야 한다.[32]

8. 1. 분산 컴퓨팅에서의 설계 사상 (아키텍처)

분산 컴퓨팅에서는 다양한 하드웨어 및 소프트웨어 설계 사상(아키텍처)이 사용된다. 크게 저수준과 고수준으로 나눌 수 있다.[32]

; 저수준 설계 사상(아키텍처)

: 복수의 CPU를 네트워크로 상호 접속해야 한다. 이 네트워크는 기판에 프린트된 회로일 수도 있고, 느슨하게 결합된 기기와 케이블의 집합체일 수도 있다.[32]

; 고수준 설계 사상(아키텍처)

: 통신 시스템으로 개별 컴퓨터에서 동작하는 프로세스를 상호 접속해야 한다.[32]

8. 2. 분산 프로그래밍에서의 설계 사상 (아키텍처)

분산 프로그래밍은 클라이언트-서버 모델, 3계층, n계층, 피어 투 피어, 느슨한 결합, 밀결합(클러스터) 등 다양한 아키텍처를 기반으로 한다.[33]

  • 클라이언트-서버 모델: 클라이언트가 서버에 데이터를 요청하고, 서버는 이를 처리하여 결과를 제공한다. 클라이언트의 입력이 서버의 데이터를 변경하는 경우, 서버로 전송된다.
  • 3계층: 클라이언트, 애플리케이션 서버, 데이터베이스 서버로 구성되어 애플리케이션 배포를 단순화한다. 대부분의 웹 애플리케이션이 3계층이다.
  • N계층: 주로 웹 애플리케이션에서 요청을 백엔드 서비스로 전달하는 방식(애플리케이션 서버 사용)
  • 밀결합(클러스터): 고도로 집적된 머신 군에서 동일한 프로세스를 병렬로 실행하고, 작업을 분할하여 개별 프로세서에 실행시킨다. 계산 결과는 나중에 집약된다.
  • 피어 투 피어: 네트워크 서비스를 제공하거나 리소스를 관리하는 특별한 머신 없이, 모든 참여 머신이 동등하게 책임을 분담한다.[34] 각 머신은 클라이언트와 서버 역할을 모두 할 수 있다.[35] 비트토렌트와 비트코인 네트워크가 그 예시이다.
  • 튜플 공간 기반: 단일 주소 공간을 공유하는 것처럼 가상화하여 데이터를 필요에 따라 투명하게 복제한다. 시간적/공간적 결합도가 약화된다.


분산 컴퓨팅 아키텍처는 병행 프로세스 간의 통신과 작업 배포 방법에 따라 달라진다. 프로세스는 다양한 메시지 전달 프로토콜을 사용하여, 일반적으로 주/부 관계에서 서로 직접 통신할 수 있다. 또는, "데이터베이스 중심" 아키텍처는 공유 데이터베이스를 활용하여 직접적인 형태의 프로세스 간 통신 없이 분산 컴퓨팅을 수행할 수 있도록 한다.[36]

9. 이론적 기반

분산 컴퓨팅의 이론적 기반은 여러 컴퓨터 또는 상호 작용하는 프로세스 네트워크에서 어떤 계산 문제를 해결할 수 있는지, 그리고 얼마나 효율적으로 해결할 수 있는지를 연구하는 분야이다.

분산 알고리즘에서 계산 문제는 일반적으로 그래프와 관련이 있으며, 종종 컴퓨터 네트워크의 구조를 설명하는 그래프가 문제 인스턴스 ''이다''.[48]

분산 알고리즘 분석에서는 계산 단계보다 통신 작업에 더 많은 주의를 기울인다. 분산 컴퓨팅의 가장 간단한 모델은 LOCAL 모델인데, 이 모델에서는 모든 노드가 락스텝(lockstep) 방식으로 작동하는 동기식 시스템이다. 각 ''통신 라운드'' 동안 모든 노드는 병렬로 (1) 이웃으로부터 최신 메시지를 수신, (2) 임의의 로컬 계산 수행, (3) 이웃에게 새 메시지 전송을 한다.[53] 이러한 시스템에서 중요한 복잡성 측정은 작업을 완료하는 데 필요한 동기식 통신 라운드 수이다.

이 복잡성 측정은 네트워크의 지름(''D'')과 밀접한 관련이 있다. 실행 시간이 ''D'' 통신 라운드보다 훨씬 작으면 네트워크의 노드는 네트워크의 먼 부분에 대한 정보를 얻을 가능성이 없이 출력을 생성해야 한다. 다시 말해, 노드는 ''로컬 D-근방''에서 사용할 수 있는 정보를 기반으로 전역적으로 일관된 결정을 내려야 한다. 실행 시간이 ''D'' 라운드보다 훨씬 작은 많은 분산 알고리즘이 알려져 있으며, 이러한 알고리즘으로 해결할 수 있는 문제가 무엇인지 이해하는 것이 이 분야의 핵심 연구 질문 중 하나이다.[54] 일반적으로 네트워크 크기에서 폴리로그 시간으로 문제를 해결하는 알고리즘은 이 모델에서 효율적인 것으로 간주된다.

또 다른 일반적으로 사용되는 척도는 네트워크에서 전송되는 총 비트 수이다(cf. 통신 복잡도).[55] 이 개념은 일반적으로 LOCAL 모델과 유사하게 정의되지만 단일 메시지가 B 비트만 포함할 수 있는 CONGEST(B) 모델로 캡처된다.

분산 시스템은 식사하는 철학자 문제 및 기타 상호 배제 문제와 같이 시스템이 중단되지 않아야 하는 문제들을 다룬다. 이러한 문제에서 분산 시스템은 공유 자원 사용을 지속적으로 조정하여 충돌이나 교착 상태를 방지해야 한다.[16]

분산 컴퓨팅에는 ''내결함성''과 관련된 근본적인 과제들이 존재한다. 예를 들어 합의 문제,[56] 비잔틴 장애 허용,[57] 자가 안정화[58] 등이 있다.

또한, 분산 시스템의 ''비동기적'' 특성을 이해하기 위한 연구도 많이 이루어지고 있다.


  • 동기화기는 비동기 시스템에서 동기 알고리즘을 실행하는 데 사용될 수 있다.[59]
  • 논리 시계는 사건의 인과적 이전 발생 순서를 제공한다.[60]
  • 시계 동기화 알고리즘은 전역적으로 일관된 물리적 타임스탬프를 제공한다.[61]


분산 시스템에서 지연 시간은 "중앙값"과 "평균"이 오해의 소지가 있을 수 있으므로 "99번째 백분위수"를 통해 측정해야 한다.[62]
코디네이터 선출(또는 리더 선출)은 여러 컴퓨터(노드)에 분산된 작업의 주최자를 단일 프로세스로 지정하는 과정이다.[63] 코디네이터 선출 알고리즘이 실행된 후에는 네트워크 전체의 각 노드가 특정하고 고유한 노드를 작업 코디네이터로 인식한다.[63]

네트워크 노드들은 서로 통신하여 어떤 노드가 "코디네이터" 상태가 될지 결정한다. 이를 위해 노드 간의 대칭성을 깨는 방법이 필요하다. 예를 들어, 각 노드가 고유하고 비교 가능한 ID를 가지고 있다면, 노드들은 ID를 비교하여 가장 높은 ID를 가진 노드를 코디네이터로 결정할 수 있다.[63]

이 문제의 정의는 토큰이 손실된 토큰 링 네트워크에서 새 토큰을 생성하는 방법으로 공식화한 르란(LeLann)에게 자주 귀속된다.[64]

코디네이터 선출 알고리즘은 전송되는 총 바이트와 시간 측면에서 경제적으로 설계된다. 일반적인 무방향 그래프에 대한 갈라거(Gallager), 험블렛(Humblet) 및 스피라(Spira)가 제안한 알고리즘[65]은 분산 알고리즘 설계에 큰 영향을 미쳤으며, 분산 컴퓨팅 분야의 영향력 있는 논문으로 Dijkstra Prize를 수상했다.

무방향 링, 단방향 링, 완전 그래프, 그리드, 방향 오일러 그래프 등과 같은 다양한 종류의 네트워크 그래프에 대한 다른 많은 알고리즘이 제안되었다. 그래프 패밀리 문제를 코디네이터 선출 알고리즘 설계와 분리하는 일반적인 방법은 코라흐(Korach), 쿠텐(Kutten) 및 모란(Moran)이 제안했다.[66]

조정을 수행하기 위해 분산 시스템은 코디네이터 개념을 사용한다. 코디네이터 선출 문제는 분산 시스템의 여러 프로세서에서 프로세스 그룹 중 중앙 코디네이터 역할을 할 프로세스를 선택하는 것이다. 여러 중앙 코디네이터 선출 알고리즘이 존재한다.[67]

9. 1. 모델

분산 컴퓨팅 모델은 여러 컴퓨터 또는 상호 작용하는 프로세스 네트워크에서 어떤 계산 문제를 해결할 수 있는지, 그리고 얼마나 효율적으로 해결할 수 있는지를 연구하는 분야이다. 분산 컴퓨팅 모델은 크게 다음과 같이 나눌 수 있다.

  • 병렬 알고리즘 (공유 메모리 모델): 모든 프로세서가 공유 메모리에 접근할 수 있다. 알고리즘 설계자는 각 프로세서에서 실행되는 프로그램을 선택한다. 병렬 랜덤 액세스 머신(PRAM)이 대표적인 이론적 모델이지만, 고전적인 PRAM 모델은 공유 메모리에 대한 동기식 접근을 가정한다. 공유 메모리 프로그램은 운영 체제가 노드 간 통신을 캡슐화하고 메모리를 가상으로 통합하는 경우 분산 시스템으로 확장될 수 있다.

  • 병렬 알고리즘 (메시지 전달 모델): 알고리즘 설계자는 네트워크 구조와 각 컴퓨터에서 실행되는 프로그램을 선택한다. 부울 회로 및 정렬 네트워크와 같은 모델이 사용된다. 부울 회로는 각 게이트가 간단한 컴퓨터 프로그램을 실행하는 컴퓨터 네트워크로 볼 수 있다.

  • 분산 알고리즘 (메시지 전달 모델): 알고리즘 설계자는 컴퓨터 프로그램만 선택하며, 모든 컴퓨터는 동일한 프로그램을 실행한다. 시스템은 네트워크 구조에 관계없이 올바르게 작동해야 한다. 일반적으로 사용되는 모델은 노드당 하나의 유한 상태 기계가 있는 그래프이다.


분산 알고리즘에서 계산 문제는 일반적으로 그래프와 관련이 있으며, 종종 컴퓨터 네트워크의 구조를 설명하는 그래프가 문제 인스턴스 ''이다''.[48]

병렬 알고리즘 분야와 분산 알고리즘 분야는 초점이 다르지만, 두 분야 간에는 많은 상호 작용이 있다. 예를 들어, 그래프 채색을 위한 콜-비슈킨 알고리즘[49]은 원래 병렬 알고리즘으로 제시되었지만, 동일한 기술을 분산 알고리즘으로 직접 사용할 수도 있다.

9. 2. 복잡도 측정

분산 알고리즘 분석에서는 계산 단계보다 통신 작업에 더 많은 주의를 기울인다. 분산 컴퓨팅의 가장 간단한 모델은 모든 노드가 락스텝(lockstep) 방식으로 작동하는 동기식 시스템인 LOCAL 모델이다. 각 ''통신 라운드'' 동안 모든 노드는 병렬로 다음을 수행한다. (1) 이웃으로부터 최신 메시지를 수신, (2) 임의의 로컬 계산 수행, (3) 이웃에게 새 메시지 전송.[53] 이러한 시스템에서 중요한 복잡성 측정은 작업을 완료하는 데 필요한 동기식 통신 라운드 수이다.

이 복잡성 측정은 네트워크의 지름(''D'')과 밀접한 관련이 있다. 모든 계산 가능한 문제는 동기식 분산 시스템에서 약 2''D'' 통신 라운드로 쉽게 해결할 수 있다. 즉, 모든 정보를 한 위치에 수집하고(''D'' 라운드), 문제를 해결하고, 각 노드에 솔루션에 대한 정보를 제공한다(''D'' 라운드).[54]

반면, 알고리즘의 실행 시간이 ''D'' 통신 라운드보다 훨씬 작으면 네트워크의 노드는 네트워크의 먼 부분에 대한 정보를 얻을 가능성이 없이 출력을 생성해야 한다. 다시 말해, 노드는 ''로컬 D-근방''에서 사용할 수 있는 정보를 기반으로 전역적으로 일관된 결정을 내려야 한다. 실행 시간이 ''D'' 라운드보다 훨씬 작은 많은 분산 알고리즘이 알려져 있으며, 이러한 알고리즘으로 해결할 수 있는 문제가 무엇인지 이해하는 것이 이 분야의 핵심 연구 질문 중 하나이다.[54] 일반적으로 네트워크 크기에서 폴리로그 시간으로 문제를 해결하는 알고리즘은 이 모델에서 효율적인 것으로 간주된다.

또 다른 일반적으로 사용되는 척도는 네트워크에서 전송되는 총 비트 수이다(cf. 통신 복잡도).[55] 이 개념은 일반적으로 LOCAL 모델과 유사하게 정의되지만 단일 메시지가 B 비트만 포함할 수 있는 CONGEST(B) 모델로 캡처된다.

9. 3. 기타 문제

분산 시스템은 식사하는 철학자 문제 및 기타 상호 배제 문제와 같이 시스템이 중단되지 않아야 하는 문제들을 다룬다. 이러한 문제에서 분산 시스템은 공유 자원 사용을 지속적으로 조정하여 충돌이나 교착 상태를 방지해야 한다.[16]

분산 컴퓨팅에는 ''내결함성''과 관련된 근본적인 과제들이 존재한다. 예를 들어 합의 문제,[56] 비잔틴 장애 허용,[57] 자가 안정화[58] 등이 있다.

또한, 분산 시스템의 ''비동기적'' 특성을 이해하기 위한 연구도 많이 이루어지고 있다.

  • 동기화기는 비동기 시스템에서 동기 알고리즘을 실행하는 데 사용될 수 있다.[59]
  • 논리 시계는 사건의 인과적 이전 발생 순서를 제공한다.[60]
  • 시계 동기화 알고리즘은 전역적으로 일관된 물리적 타임스탬프를 제공한다.[61]


분산 시스템에서 지연 시간은 "중앙값"과 "평균"이 오해의 소지가 있을 수 있으므로 "99번째 백분위수"를 통해 측정해야 한다.[62]

9. 4. 리더 선출

코디네이터 선출(또는 리더 선출)은 여러 컴퓨터(노드)에 분산된 작업의 주최자를 단일 프로세스로 지정하는 과정이다.[63] 작업이 시작되기 전에는 모든 네트워크 노드가 어떤 노드가 작업의 "코디네이터"(또는 리더) 역할을 할지 모르거나 현재 코디네이터와 통신할 수 없다. 그러나 코디네이터 선출 알고리즘이 실행된 후에는 네트워크 전체의 각 노드가 특정하고 고유한 노드를 작업 코디네이터로 인식한다.[63]

네트워크 노드들은 서로 통신하여 어떤 노드가 "코디네이터" 상태가 될지 결정한다. 이를 위해 노드 간의 대칭성을 깨는 방법이 필요하다. 예를 들어, 각 노드가 고유하고 비교 가능한 ID를 가지고 있다면, 노드들은 ID를 비교하여 가장 높은 ID를 가진 노드를 코디네이터로 결정할 수 있다.[63]

이 문제의 정의는 토큰이 손실된 토큰 링 네트워크에서 새 토큰을 생성하는 방법으로 공식화한 르란(LeLann)에게 자주 귀속된다.[64]

코디네이터 선출 알고리즘은 전송되는 총 바이트와 시간 측면에서 경제적으로 설계된다. 일반적인 무방향 그래프에 대한 갈라거(Gallager), 험블렛(Humblet) 및 스피라(Spira)가 제안한 알고리즘[65]은 분산 알고리즘 설계에 큰 영향을 미쳤으며, 분산 컴퓨팅 분야의 영향력 있는 논문으로 Dijkstra Prize를 수상했다.

무방향 링, 단방향 링, 완전 그래프, 그리드, 방향 오일러 그래프 등과 같은 다양한 종류의 네트워크 그래프에 대한 다른 많은 알고리즘이 제안되었다. 그래프 패밀리 문제를 코디네이터 선출 알고리즘 설계와 분리하는 일반적인 방법은 코라흐(Korach), 쿠텐(Kutten) 및 모란(Moran)이 제안했다.[66]

조정을 수행하기 위해 분산 시스템은 코디네이터 개념을 사용한다. 코디네이터 선출 문제는 분산 시스템의 여러 프로세서에서 프로세스 그룹 중 중앙 코디네이터 역할을 할 프로세스를 선택하는 것이다. 여러 중앙 코디네이터 선출 알고리즘이 존재한다.[67]

10. 응용 분야

분산 컴퓨팅은 다양한 분야에서 활용된다.


  • 통신 네트워크:

종류내용
전화 통신망 및 이동 통신망
컴퓨터 네트워크예: 인터넷
무선 센서 네트워크
라우팅 알고리즘


  • 네트워크 응용 프로그램:

종류내용
월드 와이드 웹 및 P2P 네트워크
대규모 다중 사용자 온라인 게임 및 가상 현실 커뮤니티
분산 데이터베이스 및 분산 데이터베이스 관리 시스템
네트워크 파일 시스템
버스트 버퍼와 같은 분산 캐시
은행 시스템 및 항공 예약 시스템과 같은 분산 정보 처리 시스템


  • 실시간 프로세스 제어:

종류내용
항공기 제어 시스템
산업 제어 시스템


  • 병렬 컴퓨팅:

종류내용
과학 컴퓨팅클러스터 컴퓨팅, 그리드 컴퓨팅, 클라우드 컴퓨팅[40] 및 다양한 자원 봉사 컴퓨팅 프로젝트 포함
컴퓨터 그래픽스분산 렌더링



그리드 컴퓨팅은 다수의 컴퓨터가 네트워크(통상 인터넷)를 통해 느슨하게 연결되어 큰 계산 문제를 해결하는 데 사용된다. 퍼블릭 그리드에서는 전 세계 수천 대의 컴퓨터의 남는 시간을 활용한다. 그리드 컴퓨팅은 고가의 슈퍼컴퓨터가 필요한 계산이나, 종래에는 불가능하다고 여겨졌던 계산을 가능하게 했다.

한국에서는 분산 컴퓨팅 기술이 스마트 팩토리, 스마트 시티, 자율 주행, 인공지능, 빅데이터 분석 등 다양한 분야에서 활용되고 있으며, 4차 산업혁명을 이끄는 핵심 기술로 자리매김하고 있다.

11. 분산 컴퓨팅 프로젝트

일반적으로 참가자를 모집하는 분산 컴퓨팅 프로젝트가 많으며, 이미 목표로 한 문제 해결 등의 성과를 낸 프로젝트도 있다. 이러한 프로젝트에서는 서버-클라이언트 모델을 사용하여, 계산을 위한 원본 데이터의 분배 및 수집을 수행하고, 실제로 계산을 수행하는 여러 컴퓨터용 클라이언트 소프트웨어를 배포하며, 집계 결과를 웹 등으로 공개하는 방식을 사용한다. 이를 통해 분산 컴퓨팅을 실현하고 참가자를 모집하며, 일반 사용자의 참여를 통해 비용 절감을 목표로 한다.

하지만 이러한 프로젝트는 클라이언트 등을 개조하여 의도적으로 잘못된 계산 결과를 서버로 보내는 위험성이 존재한다. 이러한 문제에 대한 대책으로 통신 방식을 비공개로 하거나, 동일한 계산을 여러 클라이언트에 반복 수행하도록 하는 방법 등이 사용된다.

프로젝트 진행은 개인 소유의 PC에 의한 계산 결과를 집계하는 방식으로 이루어지므로, 참가자 수가 프로젝트의 진행 속도에 큰 영향을 미친다. 대부분의 프로젝트에서는 진행 상황과 함께 참가자 개인 또는 팀의 집계 결과를 표시하여 참가자 간의 교류를 유도하고 경쟁 의식을 높여 참가자 증가를 유도한다.

11. 1. 주요 프로젝트


  • 현재 가동 중 (알파벳순)
  • * BOINC - 분산 컴퓨팅 관리 소프트웨어. 다양한 프로젝트가 이 소프트웨어를 이용하여 분산 컴퓨팅을 수행하고 있다.
  • * distributed.net - 전수 조사에 의한 암호 해독을 통한 프라이버시 보호 주장, 전수 조사에 의한 수학적 난제 증명 등.
  • * DreamLab - 스마트폰용 애플리케이션. 신종 코로나바이러스에 유효한 물질 탐색 등을 수행한다.
  • * Einstein@Home - 일반 상대성 이론에서 예측되는 중력파를 관측 데이터로부터 검출하는 것을 목표로 한다.
  • * Electric Sheep - 프랙탈 영상을 생성하는 프랙탈 아트 관련 프로젝트.
  • * Folding@home - 분자 역학에 의한 단백질의 접힘 예측 (단백질 구조 예측).
  • * GIMPS - 메르센 소수 발견.
  • * M4 Project - 제2차 세계 대전 중 도청된 나치 독일의 미해독 암호 해독을 목표로 한다.
  • * World Community Grid - 주로 의료 관련 (에이즈나 암, 근이영양증) 신약 개발을 위한 분자 분석, 단백질 분석 관련 프로젝트. 위 BOINC를 사용하여 분석도 가능하다.
  • * 구글 팔분 발견 시스템 "∞Eyes" - 검색 엔진의 검색 결과를 분석하여 구글 팔분을 발견하려는 프로젝트.

  • 가동 종료 (알파벳순)
  • * cell computing - 유전자의 주기성 검색을 통한 유전 질환 감지를 목표로 한다. NTT 데이터가 제공. (2008년 3월 종료)
  • * SETI@home - 우주 생물학. 지구 밖에서 오는 신호에서 비자연 신호를 추출하여 외계 생명체를 탐색. (2020년 3월 종료)
  • * United Devices Cancer Research Project - 암 치료제 개발을 위한 분자 분석. (2007년 4월 종료)

참조

[1] 서적 Distributed systems: principles and paradigms https://www.distribu[...] Pearson Prentice Hall 2020-08-28
[2] 서적 Texts in Computer Science Springer London
[3] 서적 Fundamentals of Software Architecture: An Engineering Approach O'Reilly Media 2020-03-03
[4] 서적 Monolith to Microservices Evolutionary Patterns to Transform Your Monolith O'Reilly Media
[5] 서적 Building Serverless Applications on Knative O'Reilly Media
[6] 서적 Texts in Computer Science Springer London
[7] 문서 Andrews
[8] 간행물 Modern Messaging for Distributed Sytems (sic) 2015
[9] 문서 Godfrey
[10] 문서 Andrews, Dolev
[11] 문서 Lynch
[12] 문서 Ghosh
[13] 문서 Andrews, Dolev, Ghosh, Lynch, Peleg
[14] 문서 Andrews, Ghosh, Peleg
[15] 문서 Ghosh, Peleg
[16] 문서 Ghosh, Peleg
[17] 문서 Ghosh, Lynch, Peleg
[18] 문서 Lynch, Peleg
[19] 문서 Ghosh, Lynch, Peleg
[20] 서적 Fundamentals of Software Architecture: An Engineering Approach O'Reilly Media
[21] 문서 Ghosh, Keidar
[22] 문서 Lynch, Peleg
[23] 문서 Peleg
[24] 문서 Papadimitriou, Keidar
[25] 문서 See references in [[#Introduction|Introduction]]
[26] 웹사이트 Parallel and Distributed Algorithms http://www.comp.nus.[...] National University of Singapore 2018-07-20
[27] 문서 Andrews
[28] 문서 Andrews
[29] 웹사이트 The history of email http://www.nethistor[...] 2009-04-15
[30] 서적 On the Way to the Web: The Secret History of the Internet and its Founders https://books.google[...] Apress 2018-07-20
[31] 서적 Introduction to Distributed Algorithms https://books.google[...] Cambridge University Press 2018-07-20
[32] 서적 Applications of Evolutionary Computing Springer Science & Business Media
[33] 간행물 Real Time And Distributed Computing Systems https://pdfs.semanti[...] 2017-01-09
[34] 문서 The Age of Cryptocurrency: How Bitcoin and the Blockchain Are Challenging the Global Economic Order St. Martin's Press 2015-01-27
[35] 서적 Peer-to-peer computing : principles and applications Springer 2010
[36] 논문 A database-centric virtual chemistry system
[37] 간행물 A model for optimal database allocation in distributed computing systems 1990
[38] 문서
[39] 문서
[40] 논문 Cost-efficient parallel processing of irregularly structured problems in cloud computing environments 2019
[41] 서적 Reactive Application Development Manning
[42] 서적 Parallel Computation Systems For Robotics: Algorithms And Architectures World Scientific 2018-07-20
[43] 서적 Models of Computation: Exploring the Power of Computing Addison Wesley
[44] 문서
[45] 문서
[46] 문서
[47] 문서
[48] 문서 Introduction to Distributed Systems http://www.tgpcet.co[...]
[49] 문서
[50] 문서
[51] 문서
[52] 문서
[53] 문서
[54] 문서
[55] 서적 Distributed Computing Springer Science & Business Media 2018-07-20
[56] 문서
[57] 문서
[58] 문서
[59] 문서
[60] 문서
[61] 문서
[62] 서적 Foundations of Data Intensive Applications Large Scale Data Analytics Under the Hood
[63] 서적 Apache ZooKeeper Essentials https://books.google[...] Packt Publishing Ltd 2018-07-20
[64] 논문 Distributed systems - toward a formal approach
[65] 논문 A Distributed Algorithm for Minimum-Weight Spanning Trees http://www.apposite-[...] 1983-01
[66] 논문 A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms https://www.cs.techn[...]
[67] 웹사이트 Distributed Algorithms http://www2.cs.uregi[...] 2013-03-03
[68] 웹사이트 Major unsolved problems in distributed systems? https://cstheory.sta[...] 2018-03-16
[69] 웹사이트 How big data and distributed systems solve traditional scalability problems http://www.theserver[...] 2018-03-16
[70] 서적 Randomness Through Computation: Some Answers, More Questions World Scientific 2018-07-20
[71] 서적 Section 19.3
[72] 웹사이트 Subject: distribution (Email message sent to a DEC SRC bulletin board at 12:23:29 PDT on 28 May 87) http://research.micr[...] 2007-04-28
[73] 논문 A database-centric virtual chemistry system, J Chem Inf Model. 2006 May-Jun;46(3):1034-9 http://www.ncbi.nlm.[...]
[74] 웹사이트 CS236370 Concurrent and Distributed Programming 2002 http://www.cs.techni[...]
[75] 간행물 Ada Reference Manual, ISO/IEC 8652:2005(E) Ed. 3, Annex E Distributed Systems http://www.adaic.org[...]
[76] 서적
[77] 서적
[78] 서적
[79] 웹사이트 The history of email http://www.nethistor[...]

관련 사건 타임라인

( 최근 20개의 뉴스만 표기 됩니다. )


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com