-
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까지 설명하기에는 너무 긴 분량이 될 것이므로 초반부는 간략하게 설명하였으니 이 글을 읽고 흥미가 생긴...
-
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration 2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주...
-
Size of struct
서론 이 글은 구조체를 사용할 때 구조체가 차지하는 메모리가 어떻게 계산되는지를 다룬다. Problem Solving을 할 때 조금이나마 도움이 되기를 바란다. 구조체의 메모리 계산 예시 PS가 아닌 개발을 목적으로 한 프로그래밍을 할 때에는 보통 가독성을 중요하게 생각한다. 다음과 같은 c++ 코드를 생각해 보자. const int SIZE = 1000000; struct User{ char sex; short age; long long id; } db[SIZE]; 유저의 성별, 나이, 고유한 id를 설정해야 하는 상황이다. 우선 위와 같이 설정한 이유를 간략히 설명하겠다. 성별은 ‘M’...