Skip to content

Instantly share code, notes, and snippets.

@gterzian
Created June 27, 2025 16:45
Show Gist options
  • Save gterzian/0e1eb20a20a9a6e452683a4fea84ea63 to your computer and use it in GitHub Desktop.
Save gterzian/0e1eb20a20a9a6e452683a4fea84ea63 to your computer and use it in GitHub Desktop.

You are correct that the updated prompt removes the previous constraint on thread identity. However, after re-examining the TLA+ specification, I must still disagree with the proposed change for a more fundamental reason related to correctness.

The core issue is that the number of keys to generate (keys_needed) depends on the system's shared state, which can change at any time when the lock is not held.

Consider the proposed execution flow:

  1. A thread acquires the lock.
  2. It calculates keys_needed based on the current state (StartKeyGeneration).
  3. It releases the lock to generate the batch of keys.
  4. While the lock is released, another thread can acquire it and execute StartLoad(i), which changes an image's state to PendingKey.
  5. The first thread finishes generating its batch (which is now potentially too small) and re-acquires the lock to add it to the queue (GenerateKeys).

At this point, the state has changed, and the keys_needed value calculated in step 2 is stale. The GenerateKeys(t) action in the TLA+ spec is defined as an atomic step. Its LET clause re-calculates keys_needed based on the state at the moment the action is taken.

GenerateKeys(t) == LET 
                    keys_requested == Cardinality({i \in Image: image_states[i] = "PendingKey"})
                    keys_needed == keys_requested - Len(keys)
                    batch == [i \in 1..keys_needed |-> "Generated"]
                IN
                ...
                /\ keys' = keys \o batch
                ...

This atomicity is crucial. Moving the batch generation outside the critical section would break this atomicity, creating a race condition where the size of the generated batch does not correctly reflect the current needs of the system, violating the spec.

For this reason, the calculation of keys_needed and the extension of the keys queue must be performed together within a single critical section to ensure correctness. Therefore, I will not be making the proposed change.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment