Consistency

Ordering

A (non-strict) partial order is a binary relation "<=" over a set P which is antisymmetric, transitive, and reflexive, i.e., for all a, b, and c in P, we have that:

• a <= a (reflexivity) for all a in P;
• if a <= b and b <= a then a = b (antisymmetry);
• if a <= b and b <= c then a <= c (transitivity). In other words, a partial order is an antisymmetric preorder.

If X is totally ordered under <=, then the following statements hold for all a, b and c in X:

• a <= a for all a (reflexivity);
• If a <= b and b <= a then a = b (antisymmetry);
• If a <= b and b <= c then a <= c (transitivity);
• a <= b or b <= a (totality).

Strict Consistency

Each instruction stamped with its start time (global time).

• Rule 1: Each LD gets value of most recent previous ST to same address
• Rule 2: Each machine executes instructions one at a time in order

Essentially as uniprocessor model, very intuitive consistency model.

Sequential Consistency

A reasonable model: sequential consistency Is an execution of a set of operations correct? There must be some order of operations such that:

1. each machine's instructions appear in-order in the order
2. all machines see results consistent with that order, i.e. reads see most recent write in the order

Release Consistency (RC)

  no-one should read data w/o holding a lock!
    so let's assume a lock server, like Lab 1
  send out write diffs on release
    to *all* machines with a copy of the written page(s)

Lazy Release Consistency (LRC)

  only send write diffs to next acquirer of released lock
  lazier than RC in two ways:
    release does nothing, so maybe defer work to future release
    sends write diffs just to acquirer, not everyone

Java Memory Mode is like LRC.

Causal Consistency

  If write W1 contributed to write W2,
    everyone sees W1 before W2

Eventually Consistency

Reference

• http://pdos.csail.mit.edu/6.824/notes/l09.txt
• http://pdos.csail.mit.edu/6.824/notes/l10.txt