Scheduling Into Conflict-Free Batches

The previous page gave us a single predicate. Two transactions conflict when they share an account and at least one of them writes it — the borrow checker’s shared XOR mutable, lifted from variables to accounts. That rule tells us, for any pair, whether they may run at the same time. It does not yet tell us how to run hundreds of them.

This page closes that gap. We take a list of transactions in submission order and partition it into batches with two properties that pull in opposite directions:

• Inside a batch, nothing conflicts — so the whole batch can run on separate cores at once, at hardware speed.
• Across batches, submission order is preserved — so if a later transaction conflicts with an earlier one, it runs after it and sees its effects.

The surprise of Sealevel scheduling is that one rule delivers both at once. You do not need a parallelism pass and a separate ordering pass. You need a single number per transaction: the batch it lands in.

The layering rule

Number the transactions 0, 1, 2, … in submission order. For each transaction i, define its batch as one greater than the highest batch of any earlier transaction it conflicts with — and 0 if it conflicts with none:

   batch(i) = 1 + max{ batch(j) : j < i and conflicts(i, j) }     (0 if the set is empty)

Read it slowly, because every word is load-bearing:

• j < i — we only ever look backward, at transactions submitted before i. This is what ties the schedule to submission order.
• conflicts(i, j) — we only care about earlier transactions i actually fights with. A transaction that touches disjoint accounts imposes no constraint.
• 1 + max{…} — i must land strictly after the latest conflicting predecessor, so it can never share a batch with something it conflicts with.
• 0 if empty — a transaction that conflicts with nothing before it drops straight into the first batch.

That is the entire scheduler. It is a single backward pass computing one integer per transaction. Everything else — the parallelism, the ordering, the correctness — falls out of this one line.

Why “layering”

The rule is the classic longest-path layering of a dependency graph. Draw an edge from every earlier conflicting transaction j into i. Then batch(i) is the length of the longest chain of conflicts ending at i. Independent transactions have no incoming edges and sit at layer 0; a transaction that must wait behind a chain of k conflicting predecessors sits at layer k.

   submission order →   t0    t1    t2    t3    t4
   conflicts (edges):   t0 ─────────► t2
                              t1 ───────────► t4

   layer 0:  t0   t1   t3        (no conflicting predecessor)
   layer 1:  t2   t4             (each waited on exactly one earlier writer)

The worked example: A B A C B

Take five transactions, each writing a single account. The accounts, in submission order, are A B A C B:

   tx:               t0   t1   t2   t3   t4
   writes account:    A    B    A    C    B

Compute batch(i) left to right. A write–write on the same account is a conflict.

tx	account	earlier conflicts	batch = 1 + max, else 0
t0	A	none	0
t1	B	none	0
t2	A	t0 (both write A)	1 + batch(t0) = 1 + 0 = 1
t3	C	none	0
t4	B	t1 (both write B)	1 + batch(t1) = 1 + 0 = 1

Group by batch number:

   batch 0 (parallel):   t0[A]   t1[B]   t3[C]     ← three disjoint accounts, run together
   batch 1 (parallel):   t2[A]   t4[B]             ← each waited on an earlier writer of its account

Notice what happened without any special-casing. t0 and t2 both write A; the rule put them in different batches, in the right order. t1 and t4 both write B; same. And t3, which conflicts with nobody, slipped into batch 0 alongside t0 and t1 even though t2 (submitted before t3) got bumped to batch 1 — the scheduler does not stall an independent transaction behind an unrelated conflict.

If instead t2 had also touched B (say a transfer from A to B), it would conflict with both t0 (via A) and t1 (via B), giving batch(t2) = 1 + max(batch(t0), batch(t1)) = 1 — and then t4, writing B, would conflict with t2 and be pushed to batch(t4) = 1 + batch(t2) = 2. The chain grows exactly as long as the true dependency chain, and no longer.

The two-line correctness proof

The whole design earns its keep only if the batches are safe to run in parallel and produce the same result as running everything one-at-a-time in submission order. Both fall directly out of the rule.

Within-batch conflict-free. Suppose two transactions i and j with j < i conflicted and yet landed in the same batch, batch(i) == batch(j). But the rule forces batch(i) ≥ 1 + batch(j) > batch(j) whenever conflicts(i, j). That contradicts batch(i) == batch(j). So no two transactions in a batch conflict — a batch is safe to run on parallel cores.

Cross-batch order preserved. Take any two conflicting transactions j < i. The rule gives batch(i) ≥ 1 + batch(j), so i’s batch strictly follows j’s. Since batches execute one after another, j has fully committed its writes before i’s batch begins. Therefore i — the later writer, or the later reader of what j wrote — observes j’s effects, exactly as a strict submission-order replay would. The parallel run is observationally equivalent to the sequential one.

That is the payoff: two properties, one rule, two lines of proof. The scheduler is correct by construction, not by testing.

By the numbers — how deep do the batches get?

The number of batches equals the longest conflict chain, not the transaction count. That is the whole game.

   1000 transfers, all touching DIFFERENT accounts:
      longest conflict chain = 1  →  1 batch  →  ~1000-way parallel

   1000 transfers, all draining ONE hot account:
      longest conflict chain = 1000  →  1000 batches  →  fully serial, no speedup

   1000 transfers, 100 independent groups of 10 in a chain:
      longest conflict chain = 10  →  10 batches  →  ~100-way parallel

Parallel width is n / (batch count). Disjoint work collapses to a single wide batch; a single contended account collapses to a tower of one-transaction batches. Real workloads live in between — which is exactly the tension the hot-account ceiling page picks apart.

The code: schedule() returns batches of indices

Here is the scheduler from the book’s companion crate, solmini. It returns a Vec<Vec<usize>>: the outer vector is the batches in execution order, and each inner vector holds the indices of the transactions in that batch (indices, not clones, so nothing is copied and the caller can look each transaction back up).

/// Do two transactions conflict? They share an account and at least one writes it.
/// (Read–read on the same account is not a conflict.)
pub fn conflicts(a: &Transaction, b: &Transaction) -> bool {
    for ma in &a.accounts {
        for mb in &b.accounts {
            if ma.key == mb.key && (ma.is_writable || mb.is_writable) {
                return true;
            }
        }
    }
    false
}

/// Partition transactions into conflict-free batches by dependency layering:
///     batch(i) = 1 + max{ batch(j) : j < i and conflicts(i, j) }   (0 if none)
pub fn schedule(txs: &[Transaction]) -> Vec<Vec<usize>> {
    let mut batch_of = vec![0usize; txs.len()];
    let mut num_batches = 0usize;

    for i in 0..txs.len() {
        let mut b = 0usize;
        for j in 0..i {
            if conflicts(&txs[i], &txs[j]) {
                b = b.max(batch_of[j] + 1);   // strictly after every conflicting predecessor
            }
        }
        batch_of[i] = b;
        num_batches = num_batches.max(b + 1);
    }

    // Bucket the transaction indices by their computed batch number.
    let mut batches = vec![Vec::new(); num_batches];
    for (i, &b) in batch_of.iter().enumerate() {
        batches[b].push(i);
    }
    batches
}

The inner double loop reads exactly like the rule: for each i, scan every earlier j, and if they conflict, push i at least one batch past j. batch_of[i] is the running max; 0 if no conflict ever fires. A final pass buckets indices by batch number so batch 0 comes first.

On the A B A C B example this returns:

   schedule(&txs) == vec![
       vec![0, 1, 3],   // batch 0: t0, t1, t3
       vec![2, 4],      // batch 1: t2, t4
   ]

Under the hood — this scan is O(n²), and real Solana isn’t

The double loop compares every transaction against every earlier one, so schedule is O(n²) in the number of transactions. For a teaching crate that is fine and keeps the rule visible. A real validator packing thousands of transactions per block cannot afford it.

Solana’s runtime reaches the same layering with per-account locks instead of a pairwise scan. As it walks transactions in order, it tries to acquire a read-lock or write-lock on each declared account (that is why the footprint is declared up front). A transaction whose locks are all free joins the current batch; one that would collide with a lock already held by the batch is deferred to a later batch. That is the layering rule expressed through a lock table — the same answer, computed in roughly O(n · accounts/tx) rather than O(n²). The mental model on this page is exactly right; only the data structure changes for speed.

Batches run sequentially — and that is the point

It is tempting to read “parallel scheduler” and imagine everything running at once. It does not, and it must not. The execution loop is:

   for each batch, in order:
       run every transaction in the batch  ← in parallel, across cores
       commit their writes                 ← now the account DB reflects this batch
   (only then) move on to the next batch

The parallelism is within a batch; the sequence of batches is strictly serial. That serial spine is not a limitation to be optimized away — it is the mechanism that makes cross-batch ordering true. Batch 0’s writes are fully committed before batch 1 starts reading, so t2 in batch 1 genuinely sees t0’s effect on account A. If batches overlapped, that guarantee would evaporate and the parallel run would stop matching the sequential one.

The next page takes a single batch and shows how it actually runs across a thread pool — each transaction on its own private clone of its accounts, with writes committed only on success — and why the type system makes a data race between two transactions in the same batch literally unrepresentable.

The architect’s lens

• Why does it exist? Because the conflict rule only compares pairs of transactions; something has to turn “these two may/may not overlap” into a concrete plan for running a whole block. The scheduler is that translation layer.
• What problem does it solve? It extracts the maximum safe parallelism from a block while preserving the illusion that transactions ran one-by-one in submission order — the property every user and program silently depends on.
• What are the trade-offs? Parallel width is capped by the longest conflict chain, not the core count, so contention on a single hot account can flatten the whole schedule into a serial tower. The naive scan is also O(n²); real implementations trade it for a lock table.
• When should I avoid it? Never on Solana — it is the runtime. But the idea buys nothing when every transaction touches the same account (a single global counter), where a plain serial loop is simpler and just as fast.
• What breaks if I remove it? You are left with either an unsafe “run everything on threads” (data races on shared accounts, non-deterministic state) or a fully serial EVM-style loop that leaves every extra core idle — the exact failure the serial-EVM page diagnoses.

Check your understanding

1. State the layering rule batch(i) from memory, including the case when a transaction conflicts with nothing before it.
2. For the sequence A B A C B, which transactions land in batch 0 and which in batch 1, and why does t3 (writing C) share batch 0 with t0 even though t2, submitted earlier, was pushed to batch 1?
3. Give the two-line argument that within a batch nothing conflicts. Which piece of the rule (1 + max) does the argument lean on?
4. Batches run one after another rather than all at once. What correctness property would break if two adjacent batches were allowed to overlap in time?
5. A block has 1000 transactions. In the best case they fit in one batch; in the worst case they need 1000 batches. What single graph quantity determines which end you land near?

Show answers

1. batch(i) = 1 + max{ batch(j) : j < i and conflicts(i, j) }, and batch(i) = 0 when no earlier transaction conflicts with i. It is a single backward pass over earlier transactions.
2. Batch 0 = {t0, t1, t3}, batch 1 = {t2, t4}. t3 writes C, which no earlier transaction touches, so it conflicts with nothing and drops to batch 0. t2 writes A and conflicts with t0, so 1 + batch(t0) = 1. The scheduler ranks each transaction by its own conflict chain, so an independent t3 is never stalled behind an unrelated conflict.
3. If conflicting j < i shared a batch, then batch(i) == batch(j). But conflicts(i, j) forces batch(i) ≥ 1 + batch(j) > batch(j), a contradiction. The argument leans on the 1 + max term, which guarantees a strictly higher batch for any conflicting successor.
4. Cross-batch order preservation. The guarantee that a later conflicting transaction sees an earlier one’s writes depends on the earlier batch being fully committed before the later batch reads. Overlapping batches would let i read account state before j’s write landed, so the parallel run would no longer match the sequential replay.
5. The longest conflict chain (the longest path in the dependency graph). One batch means the longest chain is 1 (all disjoint); 1000 batches means the longest chain is 1000 (e.g. every transaction draining one hot account). Parallel width is roughly n / (number of batches).