-
Facebook의 설정 관리 시스템
이 글에서는 SOSP 2015 논문에 소개된 Facebook의 설정 관리 시스템을 살펴봅니다. Introduction 오늘날 대규모 웹서비스는 단순히 한대의 서버에서 돌아가지 않고, 수천대, 수만대 혹은 수십만대 이상의 서버로 이루어진 분산 환경에서 돌아갑니다. 이러한 상황에서 동일한 역할을 하는 서버들 사이에도 각 서버별로 다른 설정 값을 넣어줘야 하는 상황은 존재하며, 이를 “잘” 관리하는 것은 몹시 어려운 일입니다. 또한, 설정 값의 수정 또한 빈번한 경우에는 더더욱 어렵습니다. 예를 들어, 서버가 새로 시작하는 경우에만 설정 값을 읽어온다면, 새로운 설정을 적용하고 싶을...
-
Introduction to Bilateral Trade
Bilateral Trade Bilateral Trade란 기본적으로 구매자 한 명과 판매자 한 명이 item을 거래하는 것입니다. 즉, 다음과 같은 구성 요소로 이루어진다고 볼 수 있습니다: 두 agent: 구매자와 판매자 구매자의 item에 대한 평가(valuation) $B \sim F_B$, 판매자의 평가 $S \sim F_S$ 여기에서 $F_B$와 $F_S$는 각각 $B$와 $S$가 선택되는 확률분포를 뜻합니다. Bilateral Trade Mechanism Bilateral Trade에서의 Mechanism이란 다음 두 가지 함수를 어떻게 설정하는지를 뜻합니다. 할당 함수(allocation function) $A:\mathbb{R} \times \mathbb{R} \rightarrow { 0, 1 }$. 두 reported valuation...
-
연산에 대한 O(n log n) / O(1) 구간 쿼리
프로그래밍을 하면서 많이 맞닥뜨리는 연산중 하나는 “구간 쿼리”입니다. 결합법칙을 만족하는 어떤 종류의 연산이든, $O(N \log N)$ 전처리로 쿼리당 $O(1)$ 시간에 구간에 대한 쿼리를 답할 수 있는 구조를 설명하려고 합니다. 구간 쿼리 구간 쿼리는 다음과 같은 문제입니다. (전처리) 배열 $A = (A_0, A_1, \cdots, A_{N-1})$과 연산 $\circ$가 주어집니다. (쿼리) $1 \le l \le r \le N$이 주어지면, $A_l \circ A_{l+1} \circ \cdots \circ A_r$을 계산해야합니다. 여기서, 우리가 주목해볼 연산의 성질은 다음과 같습니다. 결합법칙: 임의의 세 원소...
-
QGAN in Finance
Keywords: GAN, QGAN, copula, finance data 아이온큐 공식 블로그에 소개되어 있기도 하고, 2022년 11월에 실린 논문인데 아직 한국에 소개하는 글이 없어서 블로그 글로 작성한다. arxiv엔 2021년에 올라왔는데 왜이리 늦게 실렸는지 모르겠다. PRX저널에 실으려고 꽤 오래 존버했나..? 서론 이 논문은 특정한 결합확률 분포를 양자 생성기 (QGAN)으로 모델링하는것이 주제입니다. 꽤 흥미로운 접근법을 많이 보여주고 있어서 소개하고자 하였습니다. 이 논문에서 얻어갈만한 아이디어는 아래와 같습니다. 생성 문제를 probability integral transform을 통해 uniform distribution으로 바꾸고, 이걸 생성한 뒤 역변환 하는...
-
Introduction to Distributed Graph Algorithms
Introduction to Distributed Graph Algorithms 많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를...