Topological Sort and DAG Scheduling TODO
Concept
Topological sort orders the vertices of a directed acyclic graph (DAG) so that, for every edge u→v, u comes before v. Kahn's algorithm computes this in O(V+E) by queuing up vertices with in-degree 0 and, each time one is dequeued, decrementing the in-degree of its neighbors; if the queue empties while vertices remain, a cycle exists. From a scheduling angle, each step of the topological sort — the set of vertices whose in-degree hits 0 at the same time — can be grouped into one parallel layer, and the number of layers equals the length of the DAG's longest path. So even with infinite processors, the lower bound on execution time is the longest path, i.e. the critical path — this is the fundamental limit on parallel scheduling. In parallel transaction execution, the DAG's edges are defined by state-access conflicts (write-write or read-write on the same slot), and if the access lists are declared up front, this graph can be built statically before execution even starts.
Every design that tries to run transactions within a block in parallel eventually runs into the limit set by the conflict graph's longest path, so this calculation is what lets you estimate the maximum gain parallelization can actually deliver ahead of time.
Code & Formula
# Day 11: 위상정렬·DAG 스케줄링 — Kahn 알고리즘으로 순서·병렬 레이어·최장 경로를 구한다
# 진입차수 0인 정점을 레이어 단위로 소진시키면 위상순서와 병렬 실행 스케줄이 동시에 나온다.
from collections import defaultdict
def topo_layers(nodes, edges):
graph = defaultdict(list)
indeg = {n: 0 for n in nodes}
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
layer = [n for n in nodes if indeg[n] == 0]
layers, order, remaining = [], [], dict(indeg)
while layer:
layers.append(sorted(layer))
order.extend(layer)
next_layer = []
for u in layer:
for v in graph[u]:
remaining[v] -= 1
if remaining[v] == 0:
next_layer.append(v)
layer = next_layer
if len(order) != len(nodes):
raise ValueError("사이클이 존재해 위상정렬 불가")
return order, layers
# 트랜잭션 5개(A~E)가 스토리지 슬롯 접근으로 서로 의존(충돌)하는 상황을 DAG로 모델링
nodes = ["A", "B", "C", "D", "E"]
edges = [("A", "C"), ("B", "C"), ("C", "D"), ("C", "E")] # A,B 끝나야 C 실행, C 끝나야 D,E 실행
order, layers = topo_layers(nodes, edges)
print("위상정렬 순서 =", order)
print("병렬 실행 레이어 =", layers)
print(f"레이어 수(=최장 경로 길이) = {len(layers)} -> {len(nodes)}개 트랜잭션을 {len(layers)}단계에 실행 가능")
docs/code/algorithms/algorithms-11.py
Exercise
Write a program that takes an arbitrary list of transactions along with the storage keys each one reads and writes, builds the conflict DAG, and uses Kahn's algorithm to output the list of parallel layers and the longest-path length.
Practical Connection
When Verex's CLOB matching results get settled as multiple transactions, ones that only touch different markets or different position tokens are independent in the conflict graph — meaning they can be grouped into a parallel layer, with room to lower batch-processing cost.
Where it lands in Jayverse
- Verex: implement the conflict-DAG + Kahn's-algorithm batching from the practical connection as an actual settlement module. Expose the computed critical-path length as a per-batch metric to see how close throughput gets to the theoretical bound.
- OFA: build the same state-access-conflict DAG for solver-auction intents. Batch non-conflicting solver settlements together the same way independent-market Verex trades get batched.
- gitboard: surface "batch critical-path length vs number of parallel layers" as a Verex settlement metric. It's the number that says whether parallelization is actually being captured, not just attempted.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| critical path | 임계 경로(전체 소요시간을 결정짓는 최장 경로) · 병렬 처리의 이론적 한계를 논할 때 · "i.e. the critical path — this is the fundamental limit" |
| lower bound | 하한선 · 아무리 자원이 많아도 넘을 수 없는 한계치 · "the lower bound on execution time is the longest path" |
| runs into | (한계·문제에) 부딪히다 · 병렬 실행 설계가 결국 한계에 도달할 때 · "eventually runs into the limit set by" |
| up front | 사전에·미리 · 접근 목록을 실행 전에 미리 선언할 때 · "if the access lists are declared up front" |
| in-degree | 진입 차수(그래프 정점으로 들어오는 간선 수) · 위상 정렬 알고리즘의 핵심 개념 · "queuing up vertices with in-degree 0" |
| conflict graph | 충돌 그래프(트랜잭션 간 상태 접근 충돌을 표현) · 병렬 실행 가능 여부를 판단하는 자료구조 · "the conflict graph's longest path" |
| ahead of time | 미리·사전에 · 병렬화로 얻을 최대 이득을 미리 추정할 때 · "can actually deliver ahead of time" |
| room to lower | 낮출 여지·개선 여지 · 배치 처리 비용을 줄일 가능성을 말할 때 · "with room to lower batch-processing cost" |
| DAG | 방향성 비순환 그래프(Directed Acyclic Graph) · 사이클이 없는 방향 그래프, 위상 정렬의 대상이 되는 구조 · "orders the vertices of a directed acyclic graph (DAG)" |
| CLOB | 중앙집중형 지정가 주문장(Central Limit Order Book) · 거래소 주문 매칭 결과를 가리킬 때 · "When Verex's CLOB matching results get settled" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.