This note summarizes research into the complexities that arise from maintaining state at scale when state is frequently being accessed by concurrent reads and writes.

This is fundamentally the domain of distributed databases, and understanding how they handle concurrent operations provides a foundation for reasoning about large-scale system design.

Transactions & Schedules

Key principles of transaction schedules and serializability:

  • Action Attribution: An action denotes to which transaction it belongs, and which data object is being read or written.
  • Schedule as Partial Order: A schedule represents a partial ordering of actions. It can be modeled as a Directed Acyclic Graph (DAG), or a set of ordered pairs (A, B) where action A precedes action B. Because not all actions across unrelated transactions need to be ordered relative to each other, a strict total order is not strictly required.
  • Serializability vs. Interleaving: The simplest schedule executes transactions sequentially (serialized). To maximize throughput and CPU utilization, operations from multiple transactions are interleaved.
  • Conflicts: Interleaving operations creates potential conflicts. Two operations conflict if and only if:
    1. They belong to different transactions.
    2. They access the exact same data object.
    3. At least one of the operations is a write.

Understanding conflict serializability allows systems to reorder non-conflicting actions dynamically without violating state consistency or transactional integrity.