Why must a program submitted to an in-memory store decide only from its arguments and what it read, never from the clock or a random draw?
answer
- same inputs, same effect, every run
- arguments plus what it read
- the clock is ambient state
- it may run twice somewhere else
- pass the timestamp in as an argument
basics
~20 sBecause the same program may run again elsewhere — on a replica, or replayed from a write log after a restart — and a decision taken from ambient inputs writes something different each run, so the copies stop agreeing.
solid answer
~50 sA submitted program's inputs should be exactly two things: what the caller passed in, and what it read from the store during that run. Anything else — wall-clock time, a random draw, the node's own identity — is ambient, and stores differ in how badly that hurts. Where a store hands the program and its arguments to a replica, or replays it from a write log on restart, a program that reads the clock writes something different on each run and the copies diverge with nothing reporting it; where a store replicates only the writes the program produced, divergence does not arise but the effect still cannot be reproduced or tested. The repair is to move the non-determinism outside: the **caller** reads its clock, draws its random value, generates its identifier, and passes them in as arguments. The program then only decides.
go deeper
Recall the rule in one line: a program sent to the store should work only from the values it was given and the entries it read, so that running it again does the same thing.
Explain why the rule exists — the same program can run again on a replica or be replayed from a write log — and give the repair: the caller reads the clock and passes the value in as an argument.
Show that you know stores differ on whether the program or its writes travel, and name the cost that survives either way: an effect you cannot reproduce, test, audit, or safely re-run after a partial failure.
Treat determinism as the contract that makes store-side decisions reviewable at all. Decide whose clock is authoritative once, write it down, and accept that callers' clocks disagree visibly rather than invisibly.
## What determinism means here A submitted program is **deterministic** when the same inputs always produce the same effect: the same writes, in the same order, with the same values. Its legitimate inputs are exactly two: - the arguments the caller passed in with the program; - the entries it read from the store during this run. Everything else is **ambient state**, and reading it is what makes a program non-deterministic: - the machine's wall-clock time; - a random draw or any unseeded generator; - the identity, address or configuration of the node it happens to be running on; - anything that counts how many times the program itself has run. ## Why the store cares, and where stores differ The reason this is a rule rather than a style preference is that in this class of store the same program can be **executed more than once**, in a place you were not thinking about when you wrote it. Two mechanisms do that: 1. **Replication.** The tier keeps a second copy of the keyspace on another node. 2. **Replay.** Where the store keeps a write log, restarting the node reconstructs the keyspace by applying that log again. This is precisely the place to say what varies, because stores in this class genuinely split: | How the effect travels | What non-determinism costs | |---|---| | The program and its arguments are shipped, and run again at the other end | Each run decides differently, so the two copies of the keyspace stop agreeing — silently, until somebody reads both | | Only the writes the program produced are shipped | The copies agree, because nobody re-decides; the divergence problem does not arise at all | Some stores also refuse or flag particular non-deterministic reads inside a program; others allow them and leave the consequence to you. The honest position for a candidate is: *I do not assume which behaviour I am on, so I write the program deterministically and the rule costs me nothing either way.* ## The second cost, which applies on every store Even where only the writes travel, a program that decides from ambient state is one you cannot reason about: - **You cannot reproduce a defect.** Running it again with the same arguments gives a different effect, so the bad write cannot be re-created on demand. - **You cannot test it meaningfully.** An assertion about its effect is an assertion about the clock at that instant. - **You cannot repair a half-applied effect.** When a program errors part-way, its earlier writes stay, and the repair is usually to re-run it; re-running a program whose result depends on the moment writes a *different* result on top of the first one. - **You cannot audit it.** "What did this do at 03:14?" has no answer that the arguments alone explain. A deterministic program is, in effect, a pure function of arguments and read values, and gets all the reasoning benefits that implies. ## The repair: pass the non-determinism in The repair is never to give up the behaviour. It is to move the ambient input **out of the store and into the argument list**, where it is recorded with the call: 1. The caller reads its own clock and passes the timestamp or the deadline as a number. 2. The caller draws the random value, or generates the identifier, and passes it in. 3. The program branches on those values and on what it read, and writes. Now the program is deterministic: given that argument list and those stored values, it does one thing. If it is replayed anywhere, it replays with the arguments that were recorded alongside it, so it decides the same way. The cost is that the caller's clock is now the clock of record for that decision, and callers' clocks disagree with each other. That is a real trade and worth saying aloud — but a disagreement you can see in the arguments is strictly better than one hidden inside an execution you cannot inspect. ## What the rule does not say It does not say the program may not read the store. Reading entries is a normal, deterministic input: the program read what was there at that moment, and the store applied the whole program as one unit, so nothing changed underneath it mid-run. It also does not say the program may not write time-dependent data — it may, as long as the time arrived as an argument rather than from the machine it landed on.
- The decision genuinely needs the current time, for example to stamp an entry with a deadline. How do you keep the program deterministic?The caller reads its clock and passes the instant, or the already-computed deadline, in as an argument. The program branches on that number and writes. The call's arguments then fully explain its effect, and any re-execution elsewhere uses the same number. The trade is that the caller's clock is now the clock of record, and callers' clocks disagree — visibly, in the arguments.
- Is reading a second entry inside the program also ambient state?No. What it read during the run is a legitimate input, and the store applied the whole program as one unit, so nothing changed under it mid-run. The constraint on reading other entries is a different one: where the keyspace is split across nodes, the entries a single unit touches have to be co-located, which is the partitioning question rather than the determinism one.
saying these in an interview costs you the question
- Reads wall-clock time inside the program and calls it harmless.
- Assumes every store ships only the writes a program produced.
- Thinks reading a stored entry is what makes a program non-deterministic.
- Seeds a random draw inside the program rather than passing the value in.
- Believes determinism only matters when replication is configured.