Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 3 번째 수업입니다. Is a graph bipartite? 그래프가 bipartite 인가 하는 문제는, 그래프의 노드를 이렇게 두 그룹으로 나눌 수 있느냐 하는 문제다. (http://en.wikipedia.org) 알고리즘이 얼마나 어려운가는 이렇게 나눠볼 수 있겠는데 Any programmer could do it Typical diligen algorithms student could do it Hire an … Continue reading Algorithm 3 – Spanning Tree, Shortest Paths
Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 2 번째 수업입니다. 알고리즘을 분석해야 하는 이유는 (1) Predict performance (2) Compare algorithms (3) Provide guarantees (4) Understand theoretical basis 그 중에서도 performance bug 를 피하는 것이 무엇보다 중요하다. 이를 통해 내 알고리즘이 practical large input 에 적용할 수 있을까? 고민하는 것이, 알고리즘 분석의 … Continue reading Algorithm 2: Big O Analysis
Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 1 번째 수업입니다. Union Find Dynamic Connectivity N 개의 오브젝트가 있을때, Union command: connect two objects Find/connected query: is there a path connecting the two objects? 이렇게 두 경로가 연결되어있는지 아닌지를 판별하는 알고리즘은 다양하게 활용될 수 있다. Pixels in adigital photo Computers in a … Continue reading Algorithm 1 – Union Find
대부분의 분산 서버 벤더들은 99.99999% 의 reliability 를 보장하지만, 100%는 아닙니다. 왜그럴까요? 그들이 못해서가 아니라 consensus 문제 때문입니다. The fault lies in the impossibility of consensus Consensus 문제가 중요한 이유는, 많은 분산 시스템이 consensus 문제이기 때문입니다. Perfect Failure Detection Leader Election Agreement (harder than consensus) 일반적으로 서버가 많으면 다음의 일들을 해야합니다. Reliable Multicast: Make … Continue reading Cloud Computing 7 – Paxos
multicast 는 클라우드 시스템에서 많이 사용됩니다. Cassandra 같은 분산 스토리지에서는 write/read 메세지를 replica gorup 으로 보내기도 하고, membership 을 관리하기 위해서 사용하기도 합니다 그런데, 이 multicast 는 ordering 에 따라서 correctness 에 영향을 줄 수 있기 때문에 매우 중요합니다. 자주 쓰이는 기법으로 FIFO, Casual, Total 이 있는데 하나씩 살펴보겠습니다. Ordering FIFO 를 이용한다면, 보낸 … Continue reading Cloud Computing 6 – Multicast
1ambda 