si-serializability-certifier

Answer

The SI serializability certifier works in three stages:

1. Conflict Graph Construction — For every pair of transactions, detect three types of edges: - rw (anti-dependency): Ti reads an item x, Tj writes it, and Ti's snapshot (at start_ts) predates Tj's commit. The intervals must overlap — if Ti fully committed before Tj started, the execution is already serializable in that direction. - wr dependency: Ti writes x, Tj reads x, and Ti committed before Tj took its snapshot. Tj reads Ti's version. - ww dependency: Both write the same item. (Under SI's first-committer-wins rule, concurrent ww conflicts abort one; if both appear, we order by commit.)

2. Dangerous Cycle Detection — Find all elementary cycles in the directed graph that contain at least one rw (anti-dependency) edge. Uses Tarjan's circuit-finding algorithm with blocked-node optimization. A cycle with any rw edge indicates a non-serializable history: write skew, phantom reads, or general anti-dependency cycles.

3. Minimal Pivot Structure — From all dangerous cycles, return the smallest set of transaction IDs. If multiple cycles tie, return the lexicographically first one.

Key design decisions: - Default start_ts = 0 if not provided (conservative: all transactions considered concurrent from time 0). - Accepts flexible field names: start_ts/start_timestamp, commit_ts/commit_timestamp/timestamp. - Returns "serializable" for safe histories, or an array of transaction IDs for the minimal pivot.

function certify(input) {
  const transactions = input.transactions || input;
  if (transactions.length <= 1) return "serializable";

  // Build conflict graph
  const graph = Array.from({ length: transactions.length }, () => []);
  for (let i = 0; i < transactions.length; i++)
    for (let j = 0; j < transactions.length; j++)
      if (i !== j) addEdges(transactions, i, j, graph);

  // Find dangerous cycles (containing at least one rw edge)
  const cycles = findDangerousCycles(transactions.length, graph);
  if (cycles.length === 0) return "serializable";

  // Return minimal pivot
  return minimalPivot(cycles, transactions);
}

Edge construction for rw (anti-dependency):

// rw anti-dependency: Ti reads x, Tj writes x
for (const item of Ti.read_set) {
  if (Tj.write_set.includes(item)) {
    if (si < cj && intervalsOverlap(Ti, Tj)) {
      graph[i].push({ to: j, type: 'rw' });
    }
  }
}