방향성 비순환 그래프(DAG)는 방향성 간선으로 연결된 노드들로 구성된 그래프 데이터 구조의 한 유형으로, 간선은 특정 방향을 가지며 어떤 순환도 형성하지 않습니다. 이는 방향성 순환이 없는 방향성 그래프입니다.

각 DAG의 노드는 하나 이상의 들어오는 간선과 하나 이상의 나가는 간선을 가질 수 있습니다. DAG의 간선은 노드 간의 의존성을 나타내며, 간선의 방향은 의존성의 방향을 나타냅니다. 예를 들어, 노드 A가 노드 B로 나가는 간선을 가지고 있다면, 노드 A는 노드 B에 의존한다는 것을 의미합니다.

개요

방향성 비순환 그래프(DAG)는 블록 기반 구조를 사용하지 않는다는 점에서 블록체인과 다릅니다. 대신 트랜잭션은 그래프의 정점으로 표현되며 이전 트랜잭션과 연결됩니다. 노드는 트랜잭션을 검증하고 DAG에 추가하며, 트랜잭션을 제출하려면 작업 증명 작업을 완료해야 합니다. ^[1]

DAG 기반 네트워크에서 새로운 트랜잭션은 블록체인에서 블록이 이전 블록을 참조하는 방식과 유사하게 이전 트랜잭션을 참조해야 수락됩니다. 트랜잭션을 참조하면 확인되며, 트랜잭션이 완전히 확인되려면 후속 트랜잭션에서 참조되어야 합니다. ^[1]

DAG는 블록 생성이 없고 채굴자가 없기 때문에 트랜잭션 수수료가 없어 높은 트랜잭션 속도를 가지며, 환경적 이점을 가질 수 있습니다. ^[2]

DAG는 블록체인, 작업 증명 및 지분 증명, 그리고 최장 체인 규칙을 방향성 비순환 그래프와 결합함으로써 더 높은 처리량을 허용한다는 점에서 블록체인보다 우수합니다.

역사

DAG의 최초 사용 시기는 알 수 없지만, 이 개념은 매우 유용하여 인류 역사의 시작으로 거슬러 올라갑니다.

1736년 레온하르트 오일러(Leonhard Euler)가 발표한 “쾨니히스베르크의 7개 다리” 논문은 그래프 이론을 다룬 최초의 논문으로 여겨집니다. 쾨니히스베르크의 7개 다리는 수학 역사에서 주목할 만한 문제입니다. 이 문제는 쾨니히스베르크(현재 러시아 칼리닌그라드)의 7개 다리를 각각 한 번씩만 건너는 경로를 찾는 것입니다. 오일러는 도시 지도를 그래프로 단순화한 후, 간선, 정점, 면의 수와 관련된 공식을 제시했습니다.

여기에서 그래프 이론은 수학적 구조로 묘사된 객체 간의 관계에 대한 연구로 발전했습니다. 정의가 각각 다른 다양한 유형의 그래프가 있으며, DAG는 그중 하나입니다. ^[3]

사용 사례

가계도

DAG의 원래 사용 사례 중 하나는 가계도를 만드는 것입니다. 흥미롭게도 그래프 이론에서 나무의 정의에는 대부분의 가계도가 포함되지 않았습니다. 이는 충분히 거슬러 올라가면 대부분의 가계도에서 먼 친척들이 어느 시점에서 짝을 이루어 부계와 모계 양쪽에 공통 조상이 있기 때문입니다. 즉, 가계도는 각 노드가 사람이고 각 부모-자녀 관계가 자녀를 가리키는 화살표로 그려지는 DAG로 간주될 수 있습니다. 이는 아래에 표시된 그래프를 형성하며, 이는 방향성(화살표)이고 비순환적(어떤 사람도 자신의 부모가 될 수 없음)입니다.

DAG로서의 가계도 묘사는 플리니우스(Pliny the Elder)가 로마 귀족 집 벽을 장식하는 그래프를 묘사한 고대 로마에서 기록되었습니다. 이전에는 DAG가 기록되지 않았을 수도 있지만, 가족 역사를 설명할 때 종종 설명되었습니다. ^[3]

작업 스케줄링

DAG의 또 다른 역사적인 사용 사례는 동물과 인간이 본능적으로 작업 순서를 정하는 작업 스케줄링입니다. 어떤 작업은 다른 작업이 완료될 때까지 시작할 수 없고 다른 작업은 언제든지 시작할 수 있습니다. 이것 자체가 DAG입니다.

위 DAG에서 T1은 저녁 식사를 위해 어떤 동물을 사냥할지 결정하는 것이고, 작업 2는 동물을 사냥하는 것이며, 동시에 수행할 수 있는 작업 3은 땔나무를 모으는 것입니다. 작업 4는 불을 피우는 것입니다. 작업 5는 동물을 요리하는 것으로, 불이 타오르고 동물이 사냥되어야 하며, 작업 6은 저녁 식사를 먹는 것으로, 동물이 먼저 요리되어야 합니다. 피라미드 건설, 로마 설계, 전쟁 중 공격 계획 등과 같은 대규모 작업에는 유사하지만 더 복잡한 DAG가 사용되었을 것입니다. ^[3]

컴퓨터 과학

DAG의 다른 사용 사례는 더 현대적이며, 컴퓨터 과학과 관련된 여러 가지 용도가 있습니다. 데이터 처리 네트워크, 버전 기록 및 일부 데이터 압축 알고리즘은 모두 DAG를 활용합니다. 그러나 중요한 점은 DAG가 새로운 혁신이 아니라 오래된 문제 해결 메커니즘이라는 것입니다. DAG와 블록체인의 결합은 분산 원장 확장성에 있어 큰 발전입니다. ^[3]