분산 컴퓨팅

Distributed computing
분산 컴퓨팅과 혼동하지 마십시오.
「분산 애플리케이션」은, 여기서 리다이렉트 됩니다.신뢰할 수 없는 응용프로그램의 경우 분산 응용프로그램을 참조하십시오.
「분산 정보 처리」는, 여기서 리다이렉트 됩니다.컴퓨터 회사에 대해서는 DIP Research를 참조하십시오.

분산 컴퓨팅은 분산 시스템을 연구하는 컴퓨터 과학 분야입니다.분산 시스템은 컴포넌트가 서로 다른 네트워크상의 컴퓨터에 배치되어 있는 시스템으로,[1][2] 임의의 시스템에서 서로 메시지를 전달함으로써 통신하고 동작을 조정합니다.구성요소는 공통의 목표를 달성하기 위해 서로 상호 작용합니다.분산형 시스템의 3가지 중요한 과제는 컴포넌트의 동시성 유지, 글로벌 클럭 부족 극복,[1] 컴포넌트의 독립된 장애 관리입니다.하나의 시스템 컴포넌트에 장애가 발생해도 시스템 전체에 [3]장애가 발생하지 않습니다.분산 시스템의 예는 SOA 기반 시스템에서 대규모 멀티플레이어 온라인 게임, 피어 투 피어 애플리케이션까지 다양합니다.

분산 시스템 내에서 실행되는 컴퓨터 프로그램을 분산 [4]프로그램이라고 하며, 분산 프로그래밍은 이러한 [5]프로그램을 작성하는 과정입니다.메시지 전달 메커니즘에는 순수 HTTP, RPC 유사 커넥터 및 메시지큐 [6]등 다양한 유형의 구현이 있습니다.

분산 컴퓨팅은 또한 계산 문제를 해결하기 위해 분산 시스템을 사용하는 것을 의미합니다.분산 컴퓨팅에서는 문제가 여러 태스크로 나뉘는데, 각 태스크는 메시지 [8]전달을 통해 서로 통신하는 하나 이상의 [7]컴퓨터에 의해 해결됩니다.

서론

"분산 시스템", "분산 프로그래밍", "분산 알고리즘"과 같은 용어로 배포되는 단어는 원래 개별 컴퓨터가 일부 지리적 [9]영역 내에서 물리적으로 배포되는 컴퓨터 네트워크를 가리킵니다.오늘날 이 용어는 훨씬 더 넓은 의미로 사용되고 있으며, 심지어 동일한 물리적 컴퓨터에서 실행되며 메시지 [8]전달에 의해 서로 상호 작용하는 자율 프로세스를 가리킵니다.

분산 [10]시스템에 대한 단일 정의는 없지만 다음과 같은 정의 속성이 일반적으로 사용됩니다.

  • 자율 계산 엔티티(컴퓨터 또는 노드)가 여러 개 있으며, 각 엔티티에는 자체 로컬 [11]메모리가 있습니다.
  • 엔티티는 메시지 [12]전달을 통해 서로 통신합니다.

분산형 시스템은 [13]큰 계산 문제를 해결하는 것과 같은 공통의 목표를 가질 수 있습니다.그러면 사용자는 자율 프로세서의 집합을 하나의 단위로 인식합니다.또는 각 컴퓨터는 개별 요구를 가진 자체 사용자를 가질 수 있으며, 분산 시스템의 목적은 공유 자원의 사용을 조정하거나 사용자에게 [14]통신 서비스를 제공하는 것입니다.

분산 시스템의 기타 일반적인 속성은 다음과 같습니다.

  • 시스템은 개별 컴퓨터의 [15]장애를 허용해야 합니다.
  • 시스템의 구조(네트워크 토폴로지, 네트워크 레이텐시, 컴퓨터 수)는 사전에 알려져 있지 않습니다.시스템은 다른 종류의 컴퓨터와 네트워크 링크로 구성될 수 있으며 분산 [16]프로그램을 실행하는 동안 시스템이 변경될 수 있습니다.
  • 각 컴퓨터에는, 시스템의 표시는 한정되어 있어 불완전합니다.각 컴퓨터는 [17]입력의 일부만 인식할 수 있습니다.

병렬 및 분산 컴퓨팅

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

분산 시스템은 네트워크 연결된 컴퓨터의 그룹으로, 작업에 대한 공통 목표를 공유합니다."동시 컴퓨팅", "병렬 컴퓨팅" 및 "분산 컴퓨팅"이라는 용어는 서로 겹치는 부분이 많고 [18]명확한 차이는 없습니다.동일한 시스템은 "병렬" 및 "분산"으로 특징지을 수 있습니다.일반적인 분산 시스템의 프로세서는 동시에 [19]병렬로 실행됩니다.병렬 컴퓨팅은 분산 컴퓨팅의 특정 [20]긴밀하게 결합된 형태로 간주될 수 있으며 분산 컴퓨팅은 느슨하게 [10]결합된 병렬 컴퓨팅의 형태로 간주될 수 있습니다.그러나 다음 기준을 사용하여 동시 시스템을 "병렬" 또는 "분산"으로 대략 분류할 수 있습니다.

  • 병렬 컴퓨팅에서는 [21]모든 프로세서가 프로세서 간에 정보를 교환하기 위해 공유 메모리에 액세스할 수 있습니다.
  • 분산 컴퓨팅에서는, 각 프로세서에 독자적인 프라이빗 메모리(분산 메모리)가 있습니다.정보는 프로세서 [22]간에 메시지를 전달함으로써 교환됩니다.

오른쪽 그림은 분산 시스템과 병렬 시스템의 차이를 보여줍니다.그림 (a)는 일반적인 분산 시스템의 개략도입니다.시스템은 각 노드가 컴퓨터이고 노드를 연결하는 각 회선이 통신 링크인 네트워크 토폴로지로 표현됩니다.그림 (b)는 동일한 분산 시스템을 보다 자세히 보여줍니다. 각 컴퓨터는 자체 로컬 메모리를 가지고 있으며, 사용 가능한 통신 링크를 사용하여 노드 간에 메시지를 전달해야만 정보를 교환할 수 있습니다.그림 (c)는 각 프로세서가 공유 메모리에 직접 액세스할 수 있는 병렬 시스템을 보여줍니다.

병렬 및 분산 알고리즘이라는 용어를 사용하는 기존 용어가 병렬 및 분산 시스템의 정의와 완전히 일치하지 않기 때문에 상황은 더욱 복잡해집니다(자세한 내용은 아래 참조).단, 경험칙으로서 공유 메모리 멀티프로세서의 고성능 병렬 계산은 병렬 알고리즘을 사용하고,[23] 대규모 분산 시스템의 조정은 분산 알고리즘을 사용한다.

역사

메시지 전달을 통해 통신하는 동시 프로세스의 사용은 1960년대에 [24]연구된 운영 체제 아키텍처에 뿌리를 두고 있습니다.최초로 널리 보급된 분산 시스템은 이더넷과 같은 로컬 에리어 네트워크로, [25]1970년대에 발명되었습니다.

인터넷의 전신 중 하나인 ARPANET은 1960년대 말에 도입되었고 ARPANET 이메일은 1970년대 초에 발명되었다.이메일은 ARPANET의 [26]가장 성공적인 응용 프로그램이 되었으며, 아마도 대규모 분산 응용 프로그램의 가장 이른 예일 것입니다.ARPANET(및 그 후계자인 글로벌 인터넷) 외에도 1980년대의 Usenet과 FidoNet이 포함된 초기 세계 컴퓨터 네트워크는 분산 토론 [27]시스템을 지원하기 위해 사용되었습니다.

분산 컴퓨팅에 대한 연구는 1970년대 후반과 1980년대 초반에 컴퓨터 과학의 독자적인 분야가 되었습니다.이 분야의 첫 번째 컨퍼런스인 PODC(분산 컴퓨팅의 원칙에 관한 심포지엄)는 1982년으로 거슬러 올라가며, 1985년 분산 컴퓨팅에 관한 국제 심포지엄(DISC)이 오타와에서 [28]분산 알고리즘에 관한 국제 워크숍으로 처음 개최되었습니다.

아키텍처

분산 컴퓨팅에는 다양한 하드웨어 및 소프트웨어 아키텍처가 사용됩니다.하위 레벨에서는 네트워크가 회로 기판에 인쇄되어 있는지, 디바이스와 케이블이 느슨하게 결합되어 있는지에 관계없이 여러 CPU를 어떤 종류의 네트워크와 상호 접속해야 합니다.보다 높은 수준에서 이러한 CPU에서 실행되는 프로세스를 일종의 통신 [29]시스템과 상호 연결해야 합니다.

분산 프로그래밍은 일반적으로 클라이언트와 서버, 3계층, n계층 또는 피어투피어(peer-to-peer)의 몇 가지 기본 아키텍처 중 하나 또는 느슨한 커플링 또는 엄격한 [30]커플링 중 하나로 분류됩니다.

  • Client-server: 스마트클라이언트가 서버에 접속하여 데이터를 포맷하여 사용자에게 표시하는 아키텍처.클라이언트의 입력은, 영속적인 변경을 나타내면, 서버에 커밋 됩니다.
  • 3계층: 스테이트리스 클라이언트를 사용할 수 있도록 클라이언트 인텔리전스를 중간 계층으로 이동하는 아키텍처.이것에 의해, 애플리케이션의 도입이 심플화됩니다.대부분의 웹 애플리케이션은 3계층입니다.
  • n-tier: 일반적으로 요청을 다른 엔터프라이즈서비스로 전송하는 웹 애플리케이션을 참조하는 아키텍처.이러한 유형의 애플리케이션은 애플리케이션 서버의 성공에 가장 큰 영향을 미칩니다.
  • 피어투피어: 서비스를 제공하거나 네트워크 [31]: 227 자원을 관리하는 특별한 머신이 없는 아키텍처.대신 모든 책임은 피어(peer)로 알려진 모든 기계 간에 균일하게 분배됩니다.피어(peer)[32]는 클라이언트로서도 서버로서도 사용할 수 있습니다.이 아키텍처의 예로는 BitTorrent와 Bitcoin 네트워크가 있습니다.

분산 컴퓨팅 아키텍처의 또 다른 기본적인 측면은 동시 프로세스 간에 작업을 전달하고 조정하는 방법입니다.다양한 메시지 전달 프로토콜을 통해 프로세스는 일반적으로 마스터/슬레이브 관계에서 서로 직접 통신할 수 있습니다.또, 「데이터베이스 중심」아키텍처는, 공유 [33]데이타베이스를 이용하는 것으로, 프로세스간 직접 통신의 형식 없이 분산 컴퓨팅을 실시할 수 있습니다.특히 데이터베이스 중심 아키텍처는 실시간 환경 릴레이를 허용하는 개략적인 아키텍처에서 관계형 처리 분석을 제공합니다.이것에 의해, 네트워크 [34]데이타베이스의 파라메타내 및 그 외의 분산 컴퓨팅 기능이 가능하게 됩니다.

적용들

분산 시스템과 분산 컴퓨팅을 사용하는 이유는 다음과 같습니다.

  1. 애플리케이션의 성질상, 복수의 컴퓨터를 접속하는 통신 네트워크를 사용할 필요가 있는 경우가 있습니다.예를 들면, 한 물리 로케이션에서 생성되어 다른 로케이션에서 필요한 데이터 등입니다.
  2. 원칙적으로 하나의 컴퓨터를 사용하는 것이 가능한 경우가 많지만, 분산 시스템을 사용하는 것이 실질적인 이유로 유리하다.예를 들어, 하나의 하이엔드 컴퓨터에 비해 여러 대의 로우엔드 컴퓨터를 사용하여 원하는 수준의 성능을 얻는 것이 비용 효율적일 수 있습니다.단일 장애 지점이 없기 때문에 분산 시스템은 비분산 시스템보다 더 높은 신뢰성을 제공할 수 있습니다.또한 분산 시스템은 단일 단일 프로세서 [35]시스템보다 확장 및 관리가 더 용이할 수 있습니다.

예

분산 시스템과 분산 컴퓨팅의 응용 프로그램의 예는 다음과 같습니다.[36]

이론적 기초

주요 기사:분산 알고리즘

모델

컴퓨터를 사용하여 자동화하고 싶은 태스크의 대부분은 질문-답변 유형입니다.질문을 하면 컴퓨터가 답을 생성합니다.이론적인 컴퓨터 과학에서는, 그러한 작업을 계산상의 문제라고 부릅니다.형식적으로 계산 문제는 인스턴스별로 솔루션과 함께 인스턴스로 구성됩니다.인스턴스는 델이 질문할 수 있는 질문이며, 솔루션은 이러한 질문에 대한 바람직한 답변입니다.

이론 컴퓨터 과학은 컴퓨터를 사용하여 어떤 계산 문제를 해결할 수 있는지(계산 가능성 이론)와 얼마나 효율적으로(계산 복잡성 이론)를 이해하려고 합니다.전통적으로, 어떤 경우에 대해 올바른 해결책을 도출하는 알고리즘을 설계할 수 있다면, 어떤 문제를 컴퓨터를 사용하여 해결할 수 있다고 알려져 있다.이러한 알고리즘은 범용 컴퓨터에서 실행되는 컴퓨터 프로그램으로 구현될 수 있습니다. 이 프로그램은 입력에서 문제 인스턴스를 읽어내고 계산을 수행하며 출력으로 솔루션을 생성합니다.랜덤 액세스 머신 또는 범용 튜링 머신과 같은 형식주의는 그러한 [38][39]알고리즘을 실행하는 순차 범용 컴퓨터의 추상 모델로 사용될 수 있다.

동시 및 분산 컴퓨팅 분야에서는 여러 컴퓨터 또는 상호작용하는 프로세스 네트워크를 실행하는 컴퓨터의 경우 유사한 질문을 연구합니다. 이러한 네트워크에서 어떤 계산 문제를 해결할 수 있으며 얼마나 효율적으로 해결할 수 있습니까?그러나 동시 또는 분산 시스템의 경우 "문제 해결"이 무엇을 의미하는지 전혀 알 수 없습니다. 예를 들어 알고리즘 설계자의 태스크는 무엇이며 순차 범용 [citation needed]컴퓨터의 동시 또는 분산은 무엇입니까?

아래에서는 여러 대의 컴퓨터가 있는 경우에 초점을 맞춥니다.단, 여러 대의 문제는 한 대의 컴퓨터에서 동시에 실행되는 프로세스에서도 동일합니다.

일반적으로 다음 3가지 뷰포인트가 사용됩니다.

공유 메모리 모델의 병렬 알고리즘
  • 모든 CPU가 공유 메모리에 액세스 할 수 있습니다.알고리즘 설계자는 각 프로세서에 의해 실행되는 프로그램을 선택합니다.
  • 하나의 이론 모델은 사용되는 [40]Parallel Random-Access Machine(PRAM; 병렬 랜덤 액세스머신)입니다.다만, 기존의 PRAM 모델에서는, 공유 메모리에의 동기 액세스를 전제로 하고 있습니다.
  • 공유 메모리 프로그램은 기본 운영 체제가 노드 간의 통신을 캡슐화하고 모든 개별 시스템에 걸쳐 메모리를 가상으로 통합하면 분산 시스템으로 확장할 수 있습니다.
  • 실제 멀티프로세서머신의 동작에 가깝고 Compare-and-Swap(CAS; 비교 및 스왑) 등의 머신명령어 사용을 고려한 모델은 비동기 공유 메모리의 모델입니다.이 모델에는 폭넓은 작업이 있으며,[41][42] 그 요약은 문헌에서 찾을 수 있다.
메시지 전달 모델의 병렬 알고리즘
  • 알고리즘 설계자는 네트워크의 구조와 각 컴퓨터에서 실행되는 프로그램을 선택합니다.
  • 부울 회로나 정렬 네트워크 등의 모델이 사용됩니다.[43]부울 회로는 컴퓨터 네트워크로 볼 수 있습니다. 각 게이트는 매우 단순한 컴퓨터 프로그램을 실행하는 컴퓨터입니다.마찬가지로 정렬 네트워크는 컴퓨터 네트워크로 볼 수 있습니다. 즉, 각 대조군은 컴퓨터입니다.
메시지 전달 모델의 분산 알고리즘
  • 알고리즘 설계자는 컴퓨터 프로그램만 선택합니다.모든 컴퓨터가 동일한 프로그램을 실행합니다.네트워크 구조에 관계없이 시스템은 올바르게 동작해야 합니다.
  • 일반적으로 사용되는 모델은 노드당 하나의 유한 상태 머신이 있는 그래프입니다.

분산 알고리즘의 경우 일반적으로 그래프와 관련된 계산 문제가 있습니다.컴퓨터 네트워크의 구조를 설명하는 그래프가 문제 인스턴스인 경우가 많습니다.이것은 다음의 [citation needed]예에 나타나 있습니다.

예

주어진 그래프 G의 색상을 찾는 계산 문제를 고려합니다. 다른 필드에서는 다음과 같은 접근방식을 취할 수 있습니다.

집중형 알고리즘[citation needed]
  • 그래프 G는 문자열로 인코딩되고 문자열은 컴퓨터에 입력으로 지정됩니다.컴퓨터 프로그램은 그래프의 색을 찾아 문자열로 인코딩하고 결과를 출력합니다.
병렬 알고리즘
  • 다시 그래프 G는 문자열로 인코딩됩니다.그러나 여러 시스템이 동일한 문자열에 병렬로 액세스할 수 있습니다.각 컴퓨터는 그래프의 한 부분에 초점을 맞추고 해당 부분에 대한 색상을 생성할 수 있습니다.
  • 주요 초점은 여러 컴퓨터의 처리 능력을 병렬로 활용하는 고성능 계산에 있습니다.
알고리즘 분산
  • 컴퓨터 네트워크의 그래프 G는 구조체입니다.에는 G의 각 노드에 대한 하나의 컴퓨터 및 G의 각 가장자리에 한 통신 링크야.각 컴퓨터만 있는 그래프는 G장조가 주변국에 대해;컴퓨터 서로 출력은 색깔을 만들어야 한다 더 G. 서로 컴퓨터의 구조에 대해를 발견하기 위해 메시지를 교환해야 한다 알고 있다.
  • 주된 초점은 임의의 분산 시스템이지만 작전을 지휘에 있다.[표창 필요한]

반면 병렬 알고리즘 분야 분산된 알고리즘의 분야보다는 다른 초점이 두 분야 사이에 많은 상호 작용이 있다.예를 들어, 그래프 coloring[44]의 Cole–Vishkin 알고리즘은 원래 병렬 알고리즘지만 같은 기술도 직접적으로 분산된 알고리즘으로 사용될 수 있었다.

게다가, 병렬 알고리즘은 병렬식(공유 메모리를 사용하여)또는 분산형 시스템( 지나가는 메시지를 사용하여)에 구현할 수 있다.[45](달리기 vs어떤 주어진 네트워크에 적절한 네트워크를 선택하십시오)평행하고 분산 시스템 사이의 경계(공유 메모리 대 메시지 전달)는 같은 곳에 있지 않병렬 및 분산형 알고리즘의 전통적인 경계가 된다.

복잡도 측정

병렬 알고리즘에서 컴퓨터, 아직 시간과 공간 외에 제3의 자원이다.실제로, 종종 달리기는 시간과 컴퓨터 숫자 사이에 균형이 만약 더 많은 컴퓨터 병렬(운전 시간 단축을 참조하십시오)에 달리고 있는 문제 빨리 해결될 수 있다.만약 결정 문제polylogarithmic 시간에 프로세스가 다항 번호를 사용하는 것으로 해결될 수 있다면, 문제는 수업 NC에 있는 것으로 알려졌다.[46]클래스는 NC이 기술을 동일하게 피램.. 형식 주의 또는 부울 circuits—를 사용하여 정의될 수 있다.피램.. 기계 효율적이고 그 반대의 경우도 부울 논리 연산 회로처럼 보일 수 있다.[47]

분산된 알고리즘의 분석에서, 더 많은 관심을 보통 통신 작전에 계산 단계보다 지급된다.모든 노드를 정확히 같은 방식 패션을 아마도 분산 컴퓨팅의 가장 단순한 모델은 동기식.이 모델은 일반적으로 LOCAL 모델로 알려져 있습니다.각 통신 라운드 중에 (1) 병행하는 모든 노드는 네이버로부터 최신 메시지를 수신하고 (2) 임의의 로컬 계산을 실행하며 (3) 새로운 메시지를 네이버에 보냅니다.이러한 시스템에서 중심 복잡도 측정은 작업을 [48]완료하기 위해 필요한 동기 통신 라운드의 수입니다.

이 복잡도 측정은 네트워크의 지름과 밀접하게 관련되어 있습니다.D를 네트워크의 지름으로 합니다.한편, 모든 계산 가능한 문제는 동기식 분산 시스템에서 약 2D 통신 라운드로 3회적으로 해결할 수 있습니다. 즉, 모든 정보를 한 곳에서 수집하고(D 라운드로), 문제를 해결하고(D 라운드로), 각 노드에 솔루션에 대해 알립니다(D 라운드로).

한편, 알고리즘의 실행 시간이 D 통신 라운드보다 훨씬 짧을 경우, 네트워크내의 노드는 네트워크의 먼 부분에 관한 정보를 취득할 수 없는 상태로 출력을 생성해야 합니다.즉, 노드는 로컬 D-네이버에서 이용할 수 있는 정보를 바탕으로 글로벌하게 일관된 결정을 내려야 합니다.많은 분산 알고리즘이 D라운드보다 훨씬 짧은 실행 시간으로 알려져 있으며, 이러한 알고리즘으로 해결할 수 있는 문제를 이해하는 것이 이 [49]분야의 핵심 연구 질문 중 하나이다.일반적으로 이 모델에서는 네트워크크기의 다산술 시간에 문제를 해결하는 알고리즘이 효율적이라고 간주됩니다.

일반적으로 사용되는 또 다른 척도는 네트워크에서 전송되는 총 비트 수입니다(통신 [50]복잡도 참조).이 개념의 기능은 일반적으로 LOCAL 모델과 마찬가지로 정의되지만 단일 메시지에 포함할 수 있는 것은 B비트뿐인 CONGIE(B) 모델을 사용하여 캡처됩니다.

기타 문제

기존의 계산 문제는 사용자가 질문을 하고 컴퓨터(또는 분산형 시스템)가 질문을 처리한 후 답변을 생성하고 중지하는 관점을 취했습니다.하지만, 식사 철학자들 문제나 다른 유사한 상호 배타적 문제 등, 시스템이 중단되지 않아야 하는 문제도 있다.이러한 문제에서 분산 시스템은 충돌이나 교착 상태가 발생하지 않도록 공유 자원의 사용을 지속적으로 조정해야 합니다.

분산 컴퓨팅 특유의 근본적인 과제도 있습니다.예를 들어 폴트 톨러런스와 관련된 과제입니다.관련 문제의 예로는 합의 문제,[51] 비잔틴의 폴트 톨러런스,[52] 자기안정화 [53]등이 있습니다.

또한 많은 연구가 분산 시스템의 비동기적 특성을 이해하는 데 초점을 맞추고 있습니다.

  • 동기기를 사용하여 비동기 [54]시스템에서 동기 알고리즘을 실행할 수 있습니다.
  • 논리시계는 사건의 [55]순서를 정하기 전에 일어난 원인이 된다
  • 클럭 동기 알고리즘은 글로벌하게 일관된 물리 [56]타임스탬프를 제공합니다.

선거

코디네이터 선출(또는 리더 선출)은 여러 컴퓨터(노드)에 분산된 일부 작업의 주관자로 단일 프로세스를 지정하는 프로세스입니다.작업이 시작되기 전에 모든 네트워크 노드는 작업의 "코디네이터"(또는 리더) 역할을 하는 노드를 인식하지 못하거나 현재 코디네이터와 통신할 수 없습니다.단, 코디네이터 선정 알고리즘이 실행되면 네트워크 내의 각 노드는 특정 고유 노드를 작업 [57]코디네이터로 인식합니다.

네트워크 노드는 서로 통신하여 어떤 노드가 "조정자" 상태가 될지를 결정합니다.그러기 위해서는 대칭을 깨기 위한 방법이 필요합니다.예를 들어, 각 노드가 고유하고 동등한 ID를 가지고 있는 경우, 해당 노드는 ID를 비교하여 ID가 가장 높은 노드가 [57]코디네이터라고 판단할 수 있습니다.

이 문제의 정의는 대부분의 경우 LeLann이 토큰이 [58]손실된 토큰 링네트워크에서 새로운 토큰을 작성하는 방법으로 공식화한 것에 기인합니다.

코디네이터 선택 알고리즘은 전송된 총 바이트 및 시간 측면에서 경제적이도록 설계되었습니다.Galager, Humbelt 및 Spira가 일반 무방향 그래프에 대해 제안한 알고리즘은 분산 알고리즘 설계에 큰 영향을 미쳐 분산 컴퓨팅 분야에서 영향력 있는 논문으로 Dijkstra Prize를 수상했습니다.

무방향 링, 단방향 링, 완전한 그래프, 그리드, 유향 오일러 그래프 등과 같은 다양한 종류의 네트워크 그래프에 대해 많은 다른 알고리즘이 제안되었습니다.Korach, Kutten 및 Moran은 [60]그래프 패밀리의 문제를 코디네이터 선정 알고리즘 설계에서 분리하는 일반적인 방법을 제안했다.

코디네이터를 수행하기 위해 분산 시스템은 코디네이터 개념을 사용합니다.코디네이터 선정 문제는 분산 시스템의 서로 다른 프로세서 상의 프로세스 그룹 중에서 중앙 코디네이터 역할을 하는 프로세스를 선택하는 것입니다.몇 가지 중앙 조정자 선출 알고리즘이 있습니다.[61]

분산 시스템 속성

지금까지의 초점은 주어진 문제를 해결하는 분산 시스템 설계에 맞춰져 있었습니다.보완적인 연구 문제는 주어진 분산 시스템의 [62][63]특성을 연구하는 것이다.

정지 문제는 중앙집중식 계산 분야와 유사한 예입니다. 컴퓨터 프로그램이 주어지고 이 프로그램이 영원히 중단되는지 아니면 실행되는지 결정하는 것이 과제입니다.정지 문제는 일반적인 경우에서 판단할 수 없으며, 컴퓨터 네트워크의 동작을 이해하는 것은 적어도 하나의 컴퓨터의 [64]동작을 이해하는 것만큼 어렵습니다.

하지만, 결정될 수 있는 흥미로운 특별한 사건들이 많이 있습니다.특히 유한 상태 기계 네트워크의 동작에 대해 추론할 수 있습니다.예를 들어 상호작용하는(비동기적이고 결정적이지 않은) 유한 상태 머신의 특정 네트워크가 교착 상태에 도달할 수 있는지 여부를 알 수 있습니다.이 문제는 PSPACE 완전,[65] 즉 결정 가능하지만 대규모 네트워크의 경우 문제를 해결하는 효율적인(집중형, 병렬형 또는 분산형) 알고리즘이 존재하지 않을 수 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ a b Tanenbaum, Andrew S.; Steen, Maarten van (2002). Distributed systems: principles and paradigms. Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1.
  2. ^ "Distributed Programs". Texts in Computer Science. London: Springer London. 2010. pp. 373–406. doi:10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN 1868-0941. Systems consist of a number of physically distributed components that work independently using their private storage, but also communicate from time to time by explicit message passing. Such systems are called distributed systems.
  3. ^ Dusseau & Dusseau 2016, 1-2페이지.
  4. ^ "Distributed Programs". Texts in Computer Science. London: Springer London. 2010. pp. 373–406. doi:10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN 1868-0941. Distributed programs are abstract descriptions of distributed systems. A distributed program consists of a collection of processes that work concurrently and communicate by explicit message passing. Each process can access a set of variables which are disjoint from the variables that can be changed by any other process.
  5. ^ Andrews(2000).Dolev(2000).Ghosh (2007), 페이지
  6. ^ Magnoni, L. (2015). "Modern Messaging for Distributed Sytems (sic)". Journal of Physics: Conference Series. 608 (1): 012038. doi:10.1088/1742-6596/608/1/012038. ISSN 1742-6596.
  7. ^ 고드프리(2002년).
  8. ^ a b 앤드루스(2000), 페이지 291~292.돌레프(2000), 페이지 5
  9. ^ 린치(1996), 페이지 1
  10. ^ a b Ghosh (2007), 페이지
  11. ^ Andrews(2000), 페이지 8-9, 291.돌레프(2000), 페이지 5고쉬(2007), 페이지 3. 린치(1996), 페이지 xix, 1. Peleg(2000), 페이지 xv.
  12. ^ 앤드류스(2000), 페이지 291.Ghosh (2007), 페이지 3. Peleg (2000), 페이지 4.
  13. ^ Ghosh (2007년), 페이지 3-4.Peleg (2000), 페이지 1
  14. ^ Ghosh (2007), 페이지 4. Peleg (2000), 페이지 2.
  15. ^ 고쉬(2007), 페이지 4, 8. 린치(1996), 페이지 2-3.Peleg (2000), 페이지 4
  16. ^ 린치(1996), 페이지 2. Peleg(2000), 페이지 1.
  17. ^ 고쉬(2007), 페이지 7. 린치(1996), 페이지 xix, 2. Peleg(2000), 페이지 4.
  18. ^ Ghosh (2007), 페이지Keidar (2008).
  19. ^ 린치(1996), 페이지 xix, 1-2.Peleg (2000), 페이지 1
  20. ^ Peleg (2000), 페이지 1
  21. ^ 파파디미트리우(1994), 15장.Keidar (2008).
  22. ^ 「개요」의 참조를 참조해 주세요.
  23. ^ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). "Parallel and Distributed Algorithms" (PDF). National University of Singapore. Retrieved 20 July 2018.
  24. ^ 앤드류스(2000), 페이지 348.
  25. ^ 앤드류스(2000), 페이지 32.
  26. ^ 피터(2004년),이메일의 이력.
  27. ^ Banks, M. (2012). On the Way to the Web: The Secret History of the Internet and its Founders. Apress. pp. 44–5. ISBN 9781430250746.
  28. ^ Tel, G. (2000). Introduction to Distributed Algorithms. Cambridge University Press. pp. 35–36. ISBN 9780521794831.
  29. ^ Ohlídal, M.; Jaroš, J.; Schwarz, J.; et al. (2006). "Evolutionary Design of OAB and AAB Communication Schedules for Interconnection Networks". In Rothlauf, F.; Branke, J.; Cagnoni, S. (eds.). Applications of Evolutionary Computing. Springer Science & Business Media. pp. 267–78. ISBN 9783540332374.
  30. ^ "Real Time And Distributed Computing Systems" (PDF). ISSN 2278-0661. Archived from the original (PDF) on 2017-01-10. Retrieved 2017-01-09. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  31. ^ Vigna P, Casey MJ. 암호 화폐 시대: Bitcoin과 블록체인이 세계 경제질서에 어떻게 도전하고 있는가.마틴 프레스 2015년 1월 27일 ISBN 9781250065636
  32. ^ Hieu., Vu, Quang (2010). Peer-to-peer computing : principles and applications. Lupu, Mihai., Ooi, Beng Chin, 1961-. Heidelberg: Springer. p. 16. ISBN 9783642035135. OCLC 663093862.
  33. ^ Lind P, Alm M (2006), "A database-centric virtual chemistry system", J Chem Inf Model, 46 (3): 1034–9, doi:10.1021/ci050360b, PMID 16711722.
  34. ^ Chiu, G (1990). "A model for optimal database allocation in distributed computing systems". Proceedings. IEEE INFOCOM'90: Ninth Annual Joint Conference of the IEEE Computer and Communications Societies.
  35. ^ Elmasri & Navathe (2000), 섹션 24.1.2.
  36. ^ Andrews(2000), 페이지 10-11.Ghosh (2007), 페이지 4-6.린치(1996), 페이지 xix, 1. Peleg(2000), 페이지 xv.Elmasri & Navathe (2000), 섹션 24.
  37. ^ Haussmann, J. (2019). "Cost-efficient parallel processing of irregularly structured problems in cloud computing environments". Journal of Cluster Computing. 22 (3): 887–909. doi:10.1007/s10586-018-2879-3. S2CID 54447518.
  38. ^ Toomarian, N.B.; Barhen, J.; Gulati, S. (1992). "Neural Networks for Real-Time Robotic Applications". In Fijany, A.; Bejczy, A. (eds.). Parallel Computation Systems For Robotics: Algorithms And Architectures. World Scientific. p. 214. ISBN 9789814506175.
  39. ^ Savage, J.E. (1998). Models of Computation: Exploring the Power of Computing. Addison Wesley. p. 209. ISBN 9780201895391.
  40. ^ Cormen, Leiserson & Rivest(1990), 섹션 30.
  41. ^ Herlihy & Shavit (2008), 챕터 2-6.
  42. ^ 린치(1996년)
  43. ^ Cormen, Leiserson & Rivest(1990), 섹션 28 및 29.
  44. ^ Cole & Vishkin(1986년).Cormen, Leiserson & Rivest(1990), 섹션 30.5.
  45. ^ Andrews(2000), 페이지 ix.
  46. ^ Arora & Barak (2009), 섹션 6.7.Papadimitriou(1994), 섹션 15.3.
  47. ^ Papadimitriou(1994), 섹션 15.2.
  48. ^ 린치(1996), 페이지 17-23
  49. ^ Peleg(2000), 섹션 2.3 및 7.Linial(1992)Naor & Stockmeyer(1995).
  50. ^ Schneider, J.; Wattenhofer, R. (2011). "Trading Bit, Message, and Time Complexity of Distributed Algorithms". In Peleg, D. (ed.). Distributed Computing. Springer Science & Business Media. pp. 51–65. ISBN 9783642240997.
  51. ^ Lynch(1996), 섹션 5~7.Ghosh (2007), 13장.
  52. ^ 린치(1996), 페이지 99~102.고쉬(2007), 페이지 192~193.
  53. ^ Dolev(2000).Ghosh (2007년), 17장.
  54. ^ 린치(1996), 섹션 16.Peleg(2000), 섹션 6.
  55. ^ 린치(1996), 섹션 18.Ghosh (2007), 섹션 6.2~6.3.
  56. ^ Ghosh (2007), 섹션 6.4.
  57. ^ a b Haloi, S. (2015). Apache ZooKeeper Essentials. Packt Publishing Ltd. pp. 100–101. ISBN 9781784398323.
  58. ^ LeLann, G. (1977). "Distributed systems - toward a formal approach". Information Processing. 77: 155·160 – via Elsevier.
  59. ^ R. G. Gallager, P. A. Humblet, and P. M. Spira (January 1983). "A Distributed Algorithm for Minimum-Weight Spanning Trees" (PDF). ACM Transactions on Programming Languages and Systems. 5 (1): 66–77. doi:10.1145/357195.357200. S2CID 2758285.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  60. ^ Korach, Ephraim; Kutten, Shay; Moran, Shlomo (1990). "A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms" (PDF). ACM Transactions on Programming Languages and Systems. 12 (1): 84–101. CiteSeerX 10.1.1.139.7342. doi:10.1145/77606.77610. S2CID 9175968.
  61. ^ Hamilton, Howard. "Distributed Algorithms". Retrieved 2013-03-03.
  62. ^ "Major unsolved problems in distributed systems?". cstheory.stackexchange.com. Retrieved 16 March 2018.
  63. ^ "How big data and distributed systems solve traditional scalability problems". theserverside.com. Retrieved 16 March 2018.
  64. ^ Svozil, K. (2011). "Indeterminism and Randomness Through Physics". In Hector, Z. (ed.). Randomness Through Computation: Some Answers, More Questions. World Scientific. pp. 112–3. ISBN 9789814462631.
  65. ^ Papadimitriou(1994), 섹션 19.3.

레퍼런스

책들
기사들
웹 사이트

추가 정보

책들
기사들
컨퍼런스 페이퍼
  • Rodriguez, Carlos; Villagra, Marcos; Baran, Benjamin (2007). "Asynchronous team algorithms for Boolean Satisfiability". 2007 2nd Bio-Inspired Models of Network, Information and Computing Systems. pp. 66–69. doi:10.1109/BIMNICS.2007.4610083. S2CID 15185219.

외부 링크

Wiki 인용문에는 분산 컴퓨팅에 관한 인용문이 있습니다.