-
Maximum matching in CONGEST model
Introduction 이전에 작성한 글 A Near-Optimal Deterministic Distributed Synchronizer에서 잠깐 언급하였듯이, Distributed Graph Algorithm에서는 어떠한 모델을 가정하고 있는지에 따라 문제를 접근하는 방법이 달라지게 된다. 해당 포스트에서는 Asynchronized model을 가정하고 synchronized model처럼 문제를 해결할 수 있도록 도움을 주는 synchronizer에 대한 내용을 작성하였다. 이번 포스트에서는 synchronized model 중 하나인 CONGEST model을 가정하고, graph theory의 중요한 문제 중 하나인 maximum matching problem이 어떤 식으로 해결 가능한지에 대해 알아보도록 할 것이다. Synchronized message-passing model 분산 컴퓨팅 네트워크를 undirected graph...
-
Introduction to Distributed Graph Algorithms
Introduction to Distributed Graph Algorithms 많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를...