방향성 비순환 그래프(Directed Acyclic Graph, DAG)는 방향이 있는 간선(edge)으로 연결된 노드들로 구성된 그래프 데이터 구조의 한 종류로, 간선은 특정 방향을 가지며 어떠한 순환(cycle)도 형성하지 않습니다. 즉, 방향성이 있으면서도 방향성 순환이 존재하지 않는 그래프를 말합니다.

DAG의 각 노드는 하나 이상의 들어오는 간선과 나가는 간선을 가질 수 있습니다. DAG의 간선은 노드 간의 종속 관계를 나타내며, 간선의 방향은 종속성의 방향을 나타냅니다. 예를 들어, 노드 A에서 노드 B로 향하는 나가는 간선이 있다면, 이는 노드 A가 노드 B에 종속되어 있음을 의미합니다.

개요

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

DAG 기반 네트워크에서 새로운 트랜잭션이 승인되려면 블록체인의 블록이 이전 블록을 참조하는 것과 유사하게 이전 트랜잭션들을 참조해야 합니다. 트랜잭션을 참조하는 것은 해당 트랜잭션을 확인(confirm)하는 것이며, 트랜잭션이 완전히 확정되려면 후속 트랜잭션들에 의해 참조되어야 합니다. ^[1]​

DAG는 블록 생성 과정이 없기 때문에 트랜잭션 속도가 빠르고, 채굴자가 없어서 트랜잭션 수수료가 발생하지 않으므로 환경적인 이점도 가질 수 있습니다. ^[2]​

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

역사

DAG가 처음 사용된 시기는 명시되지 않았지만, 그 개념은 매우 유용하여 인류 역사의 시작까지 거슬러 올라갑니다.

1736년 레온하르트 오일러(Leonhard Euler)가 발표한 '쾨니히스베르크의 일곱 다리(Seven Bridges of Königsberg)'는 그래프 이론을 다룬 최초의 논문으로 간주됩니다. 쾨니히스베르크의 일곱 다리는 수학사에서 유명한 문제입니다. 과제는 쾨니히스베르크(현재 러시아 칼리닌그라드)에 있는 7개의 다리를 각각 한 번씩만 건너는 경로를 찾는 것이었습니다. 도시의 지도를 그래프로 단순화한 후, 오일러는 간선, 정점, 면의 수와 관련된 공식을 도입했습니다.

이후 그래프 이론은 수학적 구조로 묘사되는 객체 간의 관계에 대한 연구로 발전했습니다. 특정 정의를 가진 다양한 유형의 그래프가 존재하며, DAG는 그중 하나입니다. ^[3]​

활용 사례

가계도

DAG의 독창적인 활용 사례 중 하나는 가계도를 만드는 것입니다. 흥미롭게도 그래프 이론에서 '트리(tree)'의 정의에는 대부분의 가계도가 포함되지 않습니다. 이는 충분히 먼 과거로 거슬러 올라가는 대부분의 가계도에서 먼 친척끼리 결합하는 경우가 발생하여 부계와 모계 양쪽에 공통 조상이 생기기 때문입니다. 즉, 가계도는 각 노드가 사람이고 각 부모-자식 관계가 자식을 향하는 화살표로 그려지는 DAG로 간주될 수 있습니다. 이는 아래와 같이 방향성(화살표)이 있고 비순환적(어느 누구도 자기 자신의 부모가 될 수 없음)인 그래프를 형성합니다.

가계도를 DAG로 묘사한 기록은 고대 로마의 대 플리니우스(Pliny the Elder)가 로마 귀족 저택의 벽을 장식한 그래프를 설명한 것에서 찾아볼 수 있습니다. 그 이전에는 DAG가 기록되지는 않았을지라도 가족사를 설명할 때 자주 묘사되었을 것입니다. ^[3]​

작업 스케줄링

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

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

컴퓨터 과학

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