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.
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/.