체육공대생

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)을 공유..

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

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 이라는 절차를 이용해 이루어지며, 이 절차는 피벗..

힙은 자료구조 중 하나로, 완전 이진 트리 구조이다.힙의 높이는 루트에서 가장 깊은 리프노드까지의 경로를 나타낸다. 힙은 배열 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트리도 가능하다. 방금..

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

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

재귀함수는 하나 이상의 기본 사례에 의해 정의되고, 더 작은 인수를 사용하여 자기 자신으로 정의되는 함수이다. Methods for sloving recurrences: 재귀함수를 푸는 메서드Repeated Substitution Method(반복 치환) 위 재귀함수식을 어디서 많이 봤을 텐데, merge sort에서 등장했었다.반복 치환 메서드는 말 그대로 치환을 반복하면서 식을 유도해나가는 방식이다. merge sort 알고리즘은 먼저 원소가 한개 남을 때까지 배열을 쪼갠다.$T(n) = 2T(n/2) + n$의 식을 쪼개보면,$T(n) = 2(2T(n/2^{2}) + n/2) + n = 2^{2} T(n/2^{2}) + 2n$이다.한번 더 쪼개보자.$T(n) = 2^{2}(2T(n/2^{3}) + ..

오늘은 교수님의 늦잠 이슈로 수업을 30분 늦게 시작했다는 럭키비키한 날교수님의 랩에도 불구하고 진도는 얼마 나가지 못했지만 생각보다 엄청난 과제를 받아버렸다.. 이건 또 언제 공부해서 구현하나 ...전 수업에 RPC에 대해 배웠다.rpcgen이라는 코드 자동 생성 기능으로 simple하게 RPC를 구현할 수 있다. 하지만 RPC에도 단점이 존재하는데,서로 다른 언어를 사용하는 이질적 시스템을 지원하는 것은 어렵고,중간에 네트워크를 껴서 작동하기 때문에 네트워크에 문제가 생겨버리면 프로시저 콜에 대한 리턴을 보장하기 어렵다. RPC 구현을 위해 소켓을 쌍으로 연결하여 사용하는 ZeroMQ가 기억나는가?세 가지 통신 패턴을 제공함으로써 소켓 프로그래밍보다 쉽게 접할 수 있었다.각각의 패턴들이 어떤 상황에 ..

거품 정렬(bubble sort)는 정렬 알고리즘의 하나로, Selection Sort 알고리즘과 유사하다.서로 인접한 두 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 거품 정렬은 첫번째 원소와 두번째 원소 → 두번째 원소와 세번째 원소 → 세번째 원소와 네번째 원소 ・・・ 처럼 인접한 두 원소를 비교하며 정렬한다. 마지막 두개의 원소의 크기를 비교하여 정렬을 마치면 1회전이 끝난 것이고, 제일 큰 원소가 맨 마지막에 위치하게 된다. 2회전을 시작할 때는 이미 정렬된 맨 마지막 원소를 제외하고 비교를 시작한다. 이렇게 회전 수가 늘어날 마다 정렬해야하는 배열에서 제외되는 원소 수가 늘어난다. i가 1부터 배열 A의 길이까지 반복하고,j가 배열A의 길이에서 i+1이 될때까지..

CDM(Code Division Multiplexing): 코드 분할 다중화CDM은 각 채널이 고유한 직교함수 또는 코드워드를 사용하여 데이터를 전송하는 방식이다.직교함수(orthogonal function): 서로 다른 채널들이 서로 간섭하지 않도록 하기 위해 사용하는 고유한 코드나 신호 패턴이다. 직교 함수는 서로 독립적이기 때문에, 하나의 채널에서 전송된 신호는 다른 채널에서 전송된 신호와 겹치지 않는다. Hadamard matrix하다마드 행렬은 모든 요소가 +1 또는 -1로 이루어진 정사각 행렬이며, 행과 열이 서로 직교하는 특별한 성질을 가지고 있다.이 직교성은 다음과 같은 조건을 만족한다.$$H_{n}H_{n}^T = nI_{n}$$즉, 하다마드의 행렬의 행과 열은 서로 직교하며, 그 결과 ..