The core question
Given a set of N transaction instructions, which ones can run in parallel and which ones must be ordered? This is the fundamental question IVZA's DependencyAnalyzeranswers, and it has to answer it correctly every time. A false negative -- missing a real dependency -- means concurrent writes to the same account. That's data corruption. A false positive -- detecting a dependency that doesn't exist -- means unnecessary sequentiality. That's wasted throughput.
Account access sets
Every Solana instruction declares which accounts it will access and whether each access is a read or a write. This isn't optional -- it's enforced by the runtime. If your instruction tries to write to an account it didn't declare as writable, the transaction fails.
IVZA captures this information in an AccountSet per node:
pub struct AccountSet {
reads: HashSet<Pubkey>,
writes: HashSet<Pubkey>,
}
impl AccountSet {
pub fn has_conflict(&self, other: &AccountSet) -> bool {
// write-write: both write to same account
if !self.writes.is_disjoint(&other.writes) {
return true;
}
// read-write: one reads what the other writes
if !self.writes.is_disjoint(&other.reads) {
return true;
}
if !self.reads.is_disjoint(&other.writes) {
return true;
}
false
}
}Three HashSet::is_disjoint calls. Each is O(min(a, b)) where a and b are the set sizes. For typical Solana instructions that touch 5-15 accounts, this is effectively constant time.
The N^2 scan
The DependencyAnalyzer checks every pair of nodes:
pub fn analyze(&self, nodes: &[GraphNode]) -> Vec<GraphEdge> {
let mut edges = Vec::new();
for i in 0..nodes.len() {
for j in (i + 1)..nodes.len() {
let a = &nodes[i].account_set;
let b = &nodes[j].account_set;
if let Some(conflict) = a.classify_conflict(b) {
edges.push(GraphEdge {
from: nodes[i].id,
to: nodes[j].id,
dependency_type: conflict,
weight: nodes[j].estimated_cu,
});
}
}
}
edges
}That's O(N^2) pair comparisons. For 1,000 nodes, that's 499,500 comparisons. Sounds expensive?
It isn't. Each comparison is a few HashSet intersections on sets of size ~10. On modern hardware, the entire analysis for 1,000 nodes completes in under 2 milliseconds. The bottleneck in any real execution pipeline is never the dependency analysis -- it's the network round-trip to Solana.
Conflict classification
Not all conflicts are equal. The analyzer classifies each conflict:
- WriteWrite -- Both nodes write to the same account. Strictest ordering requirement. The order matters because final state depends on which write happens last.
- ReadWrite -- One node reads what another writes. The reader must either run before the write (seeing old state) or after (seeing new state). Usually the write should happen first.
- AccountConflict -- A general conflict detected through program-level heuristics. Used when the exact read/write pattern is ambiguous (e.g., CPIs that modify accounts internally).
This classification feeds into the scheduling phase. WriteWrite conflicts create hard dependencies -- the nodes must be in different lanes with strict ordering.ReadWrite conflicts create soft dependencies -- the scheduler has some flexibility in ordering.
Why not an inverted index?
A common optimization would be to build an inverted index: account → list of nodes that access it. Then you only check pairs that share at least one account. This would be faster for sparse graphs where most nodes are independent.
We implemented this as AccountAccessTracker and benchmarked it. For typical Solana DeFi operations (5-20 nodes, high account overlap), the inverted index approach was actually slower due to the overhead of building and querying the index. The brute-force N^2 scan with hash set intersections wins when N is small and overlap is high -- which is exactly the case for real-world transaction graphs.
For graphs with 100+ nodes (batch operations, complex arbitrage paths), theAccountAccessTracker path is available via analyze_with_tracker(). The engine selects the optimal strategy based on node count.
Edge deduplication
Two nodes can conflict on multiple accounts. If node A writes to accounts X and Y, and node B also writes to both X and Y, the naive scan would detect two conflicts. But only one edge is needed in the dependency graph.
The analyzer deduplicates by tracking seen (from, to) pairs and keeping only the strictest conflict type. WriteWrite takes precedence over ReadWrite, which takes precedence over AccountConflict. The weight assigned to the edge is the estimated compute cost of the target node, which feeds into the critical path analysis.
From edges to DAG
The output of the dependency analysis is a set of directed edges. Combined with the original nodes, this forms a DAG. The engine verifies acyclicity using Kahn's algorithm during graph construction -- if a cycle is detected, the graph is rejected with an error.
Cycles shouldn't occur in well-formed transaction graphs (you can't have instruction A depend on B and B depend on A). But CPIs and cross-program invocations can create subtle circular dependencies. Detecting them early prevents infinite loops in the scheduler.
The DAG feeds directly into the next pipeline stage: critical path analysis and parallel scheduling. But that's a topic for another post.