-
Poly-logarithmic Randomized Bellman-Ford (2/2)
Introduction 지난 글에 이어 Bringmann 2023의 near-linear time shortest single source path (SSSP) 문제를 해결하는 부분을 더 다루어보도록 하겠습니다. 간선의 가중치가 $-W^{-}$ 이상인 weighted digraph에 대해 $\mathcal{O}(\log^{2} n \log(nW))$ 번의 dijkstra algorithm으로 shortest path tree, negative cycle 중 하나를 반환하는 문제입니다. 지난 글에서는 다음의 특수한 조건을 만족하는 Restricted SSSP (RSSSP)를 $\mathcal{O}(\log^{2} n)$ 번의 dijkstra algorithm으로 해결하는 Las-Vegas algorithm을 소개하였습니다. Definition. Directed graph $G$에 어떤 정점 $s \in V(G)$가 존재하여 다음을 만족하면 $G$를 restricted graph라고 한다....
-
완전 매칭을 찾는 병렬 알고리즘
PRAM Model PRAM (Parallel Random Access Machine) 모델은 병렬 처리를 이론적으로 표현한 모델이다. $P$개의 프로세서와 크기 $M$의 공통 메모리로 이루어져 있다. PRAM 모델에서 한 번의 (병렬) 연산은 다음과 같은 과정을 통해 이루어진다: 공통 메모리의 어떤 위치에 있는 값을 읽는다. 간단한 (unit-step) 연산을 실행한다. 공통 메모리의 어떤 위치에 값을 쓴다. 여러 개의 프로세서가 동시에 연산을 수행할 때 총돌할 가능성을 배제하기 위해, 다음과 같은 가정을 한다. 먼저, 모든 프로세서가 값 읽기 (1.)를 끝낸 다음에 연산 실행과 값...
-
A Near-Optimal Deterministic Distributed Synchronizer
Synchronized message-passing model 분산 컴퓨팅 네트워크를 undirected graph $G=(V,E)$ 로 표현하자. 각 Node는 하나의 컴퓨터 또는 프로세서의 역할을 한다. Synchronized setting에서 계산 및 커뮤니케이션은 synchronous round에 이루어진다. 각 라운드마다 각 노드는 가지고 있는 데이터로 계산을 한 후 neighbor에 하나의 메시지를 보낼 수 있고, 이 때 보낼 수 있는 메시지의 크기에 따라 두 가지 모델로 나뉜다. CONGEST 모델: 보낼 수 있는 메시지의 크기를 $O(\log N) = B$ bit로 가정 LOCAL 모델: 메시지의 크기에 제한을 두지 않음...
-
Rust Crossbeam의 Epoch 기반 메모리 관리
서론 프로그래밍 언어는 다양한 방법을 통해 메모리를 관리합니다. 이러한 메모리 관리 방법은 크게 두 가지 방법으로 나눌 수 있습니다: GC(Garbage Collection)와 직접 메모리를 관리하는 방법입니다. GC는 메모리를 관리하는 방법 중 가장 편리한 방법이지만, GC가 동작하는 동안에는 프로그램이 멈추는 단점이 있습니다. 반면 직접 메모리를 관리하는 방법은 GC가 동작하지 않기 때문에 프로그램이 멈추지 않습니다. 하지만 직접 메모리를 관리하는 방법은 GC보다 훨씬 어렵습니다. Rust는 직접 메모리를 관리하는 방법을 사용합니다. Rust에서의 메모리 관리 방법은 예전 글인 Rust의 Borrow Checker을...
-
bound entanglement
서론 양자 얽힘 (quantum entanglement)는 크게 두 가지로 분류할 수 있다. 대부분의 entanglement는 free enntanglement이며, 일부가 bound entanglement이다. 특히, bound entanglement는 아직 한국에 잘 소개되지 않았으며, 한국어 명칭도 정착되지 않은 개념이다. 그리고 bound entanglement와 깊게 관련된 LOCC(Local Operations and Classical Communication)도 일반 사람들을 대상으로 많이 소개되지 않아 이에 대해 이번 글에서 간단히 소개해 보고자 한다. 양자 상태부터 설명을 시작해서 bound entanglement까지 설명하기에는 너무 긴 분량이 될 것이므로 초반부는 간략하게 설명하였으니 이 글을 읽고 흥미가 생긴...