728x90

분류 전체보기 59

Elementary Graph Algorithms

그래프 알고리즘을 배우기에 앞서, 그래프란 무엇일까? 그래프는 $G = (V, E)$는 정점 집합 V와 간선 집합 E로 이루어져 있으며, 방향성이 있을 수도 있고 없을 수도 있다.알고리즘에서 사용하는 그래프 표현 방법에는 두가지가 존재한다.인접 리스트(Adjacency list): 각 정점에 연결된 이웃 정점들을 리스트 형태로 저장한다.인접 행렬(Adgacency matrix): 정점 간의 연결을 행렬 형태로 표현하여, 특정 정점 쌍 간의 연결 여부를 나타낸다.알고리즘의 실행 시간은 보통 정점의 수 |V|와 간선의 수 |E|로 표현된다.점근 표기법을 사용할 때는, 집합의 크기를 나타내는 기호는 생략할 수 있다. $O(V + E)$로 간단히 표현할 수 있다는 의미이다.인접 리스트: Adjacency lis..

Distributed System 12

Replication: 복제복제의 목적은 가용성(availability), 신뢰성(dependability), 또는 성능(performance)을 향상시키는 것이다.이때 복제 가시성(replica visibility)에 대한 정보가 없어도 이러한 목적을 달성할 수 있어야한다. 분산 시스템인만큼, 시스템 내에서 상태의 복제를 숨겨서 사용자나 애플리케이션이 복제를 인식하지 못하도록 하는 복제 투명성(replication transparency)이 중요하다.활성 복제(Active replication)는 여러 복제본이 동시에 활성 상태로 작동하여 요청을 처리한다.기본/대기 복제(Primary/Stand-by replication)는 하나의 기본 복제본이 활성 상태로 작동하고, 대기 복제본은 기본 복제본이 장애..

DKU/분산처리 2024.11.05

Distributed System 11

Coordination전 글에 이어서 coordination에 대해 더 알아보겠다. 분산 시스템에서 여러 프로세스가 특정 자원에 대한 독점적 접근을 원할 때, 각 프로세스는 다른 프로세스와 동시에 해당 자원에 접근하지 못하도록 상호 배제(Mutual exclusion)이 필요하다.허가 기반 해결 방법(Permission-based solution): 프로세스가 자신의 임계 영역에 들어가거나 자원에 접근하기를 원할 때, 다른 프로세스들로부터 허가를 받는 방식이다.토큰 기반 해결 방법(Token-based sloution): 공유 자원에 접근할 수 있는 권한을 나타내는 토큰을 소유한 프로세스만 자원에 접근 가능한 방식이다. 토큰을 가진 프로세스만 접근 권한을 가지므로 상호 배제가 보장된다.Permission..

DKU/분산처리 2024.11.05

Sorting in Linear Time

정렬 알고리즘에는 여러가지 타입이 존재한다.정렬에는 요소들이 순차적으로 증가하게끔 만드는 오퍼레이션만 사용되며, 이는 요소의 쌍을 비교하면서 이루어진다. Exchange Sorting - Bubble Sort, Quick SortInsertion Sort Selection Sorting - Selection Sort, Heap SortMerge SortDistribution Sort - Bucket Sort, Radix Sort 정렬의 하한(lower bound)하한은 주어진 입력을 정렬하기 위해 필요한 최소 계산 작업을 의미한다. 비교 기반 정렬 알고리즘의 경우, 이 최소 비교 횟수는 보통 $\Omega(n\lg n)$이다. 여기서 어떤 비교 기반 정렬이 수행하는 비교 과정을 추상화한 것을 결정 트리 ..

Multiple Access 2

Random access (No Schedule)ALOHA알로하는 하와이 대학교에 있는 Norman의 팀이 4개의 섬에 있는 7개의 컴퓨터의 통신을 어떻게 간단하게 수행할 수 있을까에 대해 찾다가 만들었다.7개의 스테이션이 서로 패킷을 교환하는데, 패팃의 구조는 헤더(32비트), 패리티 검사(16비트), 데이터(80바이트), 패리티 검사(16비트)로 이루어져있다. 중앙 스테이션인 Menehune은 다른 모든 스테이션으로 패킷을 보내기 위해 전방 채널(Forward channel)을 사용한다. 이 채널은 413.475 MHz를 중심으로 하고, 100kHz의 대역폭을 가진다. 다른 스테이션들은 407.350MHz를 중심으로 하고, 100kHz 대역폭을 가지는 역방향 채널(Reverse channel)을 공유..

Distributed System 10

Coordination중앙화된 시스템에서 '시간'은 모호하지 않다.프로세스 A가 시간을 요청한 후에 프로세스 B가 시간을 요청하면, 당연히 프로세스의 A의 시간이 과거일 것이다. 하지만 분산 시스템에서의 '시간'은 어떨까?분산 시스템에서의 '시간'은 많은 애플리케이션에 사용된다. 데이터 일관성 유지나, 이벤트 간의 인과관계 파악, 보안 같은 곳에 쓰인다.문제는 각 시스템이 '자신만의 시계'를 가지고 있으며, 글로벌 시계가 존재하지 않는다는 것이다. 또한 자신만의 시계인 로컬 시계는 동기화되지 않을 수 있다.글로벌한 상태를 유지하기 위해서는 이벤트가 발생한 순서를 알아야한다.이는 물리적 시간과 논리적 시간으로 나누어서 볼 수 있다.Physical Clocks순서대로 줄 세우는 게 아닌 정확한 시간을 따르는..

DKU/분산처리 2024.10.17

Quick Sort Algorithm

Quick Sort최악의 경우 실행시간은 $O(n^2)$이다.평균적으로, 실행시간은 $O(n\lg{n})$이다. 이때의 숨겨진 상수 계수는 다른 알고리즘보다 작아서, 실제로는 매우 빠르게 동작하는 편이다. 퀵 정렬은 분할-정복 방식으로 작동한다.분할: 배열 A[q...r]을 피벗을 기준으로 두 개의 부분 배열로 나눈다. 앞 부분의 배열 A[p...q-1]의 모든 요소는 피벗 A[q] 보다 작거나 같고, 뒷 부분의 배열 A[q+1...r]의 모든 요소는 피벗 A[q]보다 크거나 같다.정복: 분할된 두 부분 배열을 재귀 호출을 통해 각각 정렬한다.결합: 퀵 정렬은 제자리 정렬이기 때문에, 두 부분 배열을 따로 결합할 필요는 없다.분할 과정은 PARTITION 이라는 절차를 이용해 이루어지며, 이 절차는 피벗..

Heap Sort Algorithm

힙은 자료구조 중 하나로, 완전 이진 트리 구조이다.힙의 높이는 루트에서 가장 깊은 리프노드까지의 경로를 나타낸다. 힙은 배열 A[1...n]으로 저장될 수 있으며,트리의 루트는 A[1] 이다.A[i]의 부모는 A[i/2] 이다.A[i]의 왼쪽 자식은 A[2i]이고, 오른쪽 자식은 A[2i + 1]이다.이진 표시의 구현은 컴퓨팅이 빠르다. 가장 큰 요소가 루트에 존재하는 max-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i)] $\geq$ A[i]이다.가장 작은 요소가 루트에 존재하는 min-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i) $\leq$ A[i]이다.힙정렬 알고리즘은 max-heaps를 사용하며, 힙은 이진트리가 아니라 k트리도 가능하다. 방금..

Multiple Access

다중 접속은 여러 스테이션이 공유된 통신 매체를 사용하면서, 동시에 자신의 신호(비트 스트림, 패킷 스트림)를 전송할 수 있게 해주는 방식이다. 다중 접속 방식은 스케줄링과 랜덤 액세스로 분류할 수 있다.여기서 스케줄링은 fixed assignment와 demand assignment로 나뉜다.Scheduling - Fixed assignment: 고정된 할당FDMA(Frequency division multiple access)외부 스테이션이 중앙 스테이션으로 자신의 아날로그 신호 또는 비트 스트림을 전송할 때, 중앙 스테이션이 할당한 고유한 주파수 대역을 사용하는 방식이다. 중앙 스테이션이 외부 스테이션에 주파수를 할당하고, 신호 채널을 통해 이를 외부 스테이션에 알려준다. FDMA에는 Guard b..

Distributed System 9

Naming분산 시스템에서 Name이란, 엔티티의 참조로 사용되는 비트나 문자 스트링이다.많은 수의 노드의 ip 관리가 어렵기 때문에, name을 붙이기 시작했다.네트워크 주소, 프로세스 식별자, 파일 이름, 유저 이름, 서비스 이름, 클래스 식별자 등이 있다. 네임은 공유를 가능하게 한다. 네임은 다른 오브젝트와 통신하기 위해서 흔히 쓰이는 것이며, 싱글 네임은 같은 일을하는 다수의 오브젝트를 대표할 수 있다. 또한, 네임은 큰 집합에서 특정 구성원을 고유하게 식별할 수 있다.네임은 명명된 객체가 수행하는 역할을 나타낼 수 있으며, 위치에 대한 힌트를 줄 수 있고, 수행할 수 있는 작업을 나타낼 수 있다. 네임의 유형주소: IP주소나 포트같이 특정 엔티티에 연결된 접근 지점을 나타내는 네임이다. 하나의..

DKU/분산처리 2024.10.14
728x90