Jepsen Notes

Distributed system = type of concurrent system

“Process” also referred to in literature as: nodes, hosts, actors, agents, sites, or threads

Processes are single threaded

  • No two operations executed by the same process are ever concurrent
  • An operation that does not complete/crashes has no completion time => is concurrent with every operation after its invocation
  • A process with an operation in this state ^ can never invoke another operation again

Jepsen represents a history as an ordered list of invocation and completion operations This makes representation of concurrent operations and possible states more explicit

Consistency model = set of histories

violates serializability/ not serializable means that history is not in the set of serializable histories.

consistency model A implies B if A is subset of B.

  • ex: linearizability => sequential consistency because every history that is linearizable is also sequentially consistent.

Smaller, more restrictive consistency models are “stronger” More permissive ones are “weaker”

Not all models are directly comparable.


Elle: non predicate anomaly G0-2 is section 5.1 of paper http://pmg.csail.mit.edu/papers/icde00.pdf Isolation level PL-1 to PL-3

PL-1 disallows G0: Ti’s writes are completely isolated from the writes of other transactions PL-2 disallows G1: Ti has only read the updates of transactions that have committed by the time Ti commits PL-2.99 disallows G1 + G2-item: Ti is completely isolated from other transactions with respect to data items andhas PL-2 guarantees for predicate-based reads PL-3 disallows G1, G2: Ti is completely isolated from other transactions