Determinism

Determinism is Law 1 — the foundation on which every other property depends. This chapter explains the technical mechanisms that enforce it.

CrawlSeed

All randomness in Palimpsest flows from a single 64-bit seed:

#![allow(unused)]
fn main() {
pub struct CrawlSeed {
    pub value: u64,
}

impl CrawlSeed {
    pub fn new(value: u64) -> Self { Self { value } }

    pub fn rng(&self) -> ChaCha8Rng {
        ChaCha8Rng::seed_from_u64(self.value)
    }

    pub fn derive(&self, index: u64) -> Self {
        // BLAKE3 mixing: hash(seed_bytes || index_bytes)
        let mut hasher = blake3::Hasher::new();
        hasher.update(&self.value.to_le_bytes());
        hasher.update(&index.to_le_bytes());
        let hash = hasher.finalize();
        let bytes: [u8; 8] = hash.as_bytes()[..8].try_into().unwrap();
        Self { value: u64::from_le_bytes(bytes) }
    }
}
}

ChaCha8Rng is a cryptographically secure PRNG that produces identical sequences for identical seeds on all platforms.

The rand crate is forbidden in all core crates. Palimpsest uses rand_chacha and rand_core directly. The workspace Cargo.toml specifies rand with default-features = false — no OS entropy source is available.

Ordered Collections

HashMap iteration order is randomized per Rust’s specification. Palimpsest uses BTreeMap everywhere that iteration order is observable:

#![allow(unused)]
fn main() {
// The frontier's host queues
struct Frontier {
    host_queues: BTreeMap<String, BTreeSet<FrontierEntry>>,
    seen: BTreeSet<String>,
    // ...
}
}

This ensures the same URLs produce the same host ordering on every run.

Seeded Host Rotation

When the frontier rotates between hosts, it uses a seeded Fisher-Yates shuffle:

#![allow(unused)]
fn main() {
let mut hosts: Vec<&String> = self.host_queues.keys().collect();
let mut rng = self.seed.rng();
// Fisher-Yates shuffle with seeded RNG
for i in (1..hosts.len()).rev() {
    let j = rng.gen_range(0..=i);
    hosts.swap(i, j);
}
}

Same seed, same hosts = same rotation order.

Time is Explicit

No Instant::now() or SystemTime::now() appears in core logic. All time comes from one of two sources:

Caller-provided — frontier.pop(now) takes a DateTime<Utc> parameter
ExecutionEnvelope — envelope.timestamp() returns the sealed CaptureInstant

This means tests can inject fixed timestamps, and replays use the original timestamps exactly.

Browser Determinism

When using headless Chrome, Palimpsest injects JavaScript overrides before any page scripts execute:

// Seeded from CrawlSeed
Date.now = function() { return 1700000000000 + (__date_offset += 1); };
Math.random = function() { /* seeded xorshift */ };
performance.now = function() { return (__perf_offset += 0.1); };

This prevents JavaScript on the page from introducing non-determinism.

Verification

The determinism test pattern runs the same operation twice and asserts byte-identical output:

#![allow(unused)]
fn main() {
#[test]
fn frontier_ordering_is_deterministic() {
    let seed = CrawlSeed::new(42);
    let run_a = run_frontier(seed, &urls);
    let run_b = run_frontier(seed, &urls);
    assert_eq!(run_a, run_b);
}
}

The simulation framework (palimpsest-sim) proves this at scale: 10,000 pages across 5 adversarial universes, two full runs, zero divergence.

Palimpsest Documentation