Skip to content

Instantly share code, notes, and snippets.

@aphyr
Created May 1, 2019 18:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aphyr/fafdcd31a662f75cbb01432a04eaa18e to your computer and use it in GitHub Desktop.
Save aphyr/fafdcd31a662f75cbb01432a04eaa18e to your computer and use it in GitHub Desktop.
Let:
T1 = {:type :ok, :f :txn, :value [[:append 237 3] [:r 233 [1 3 5 6 7 8 9]] [:append 237 4] [:append 238 1]], :process 16, :time 207412818568, :index 4098}
T2 = {:type :ok, :f :txn, :value [[:append 233 10] [:r 239 [1]] [:append 237 5]], :process 22, :time 206702615066, :index 4054}
T3 = {:type :ok, :f :txn, :value [[:r 233 [1 3 5 6 7 8 9 10]] [:r 238 [2]] [:append 237 7] [:r 239 [1]]], :process 22, :time 206769955506, :index 4058}
T4 = {:type :ok, :f :txn, :value [[:append 238 3] [:append 237 8]], :process 22, :time 206852651070, :index 4060}
T5 = {:type :ok, :f :txn, :value [[:append 238 4] [:r 239 [1]] [:r 241 nil]], :process 22, :time 206919825209, :index 4064}
T6 = {:type :ok, :f :txn, :value [[:r 238 [2 3 4]] [:append 239 2] [:append 241 1] [:append 239 3]], :process 22, :time 206984932481, :index 4068}
T7 = {:type :ok, :f :txn, :value [[:r 241 [1 2 3]] [:r 239 [1 2 3]] [:append 238 6]], :process 22, :time 207330867948, :index 4090}
Then:
- T1 < T2, because T1 did not observe T2's append of 9 to 233.
- T2 < T3, because T3 observed T2's append of 10 to key 233.
- T3 < T4, because T4 appended 8 after T3 appended 7 to 237.
- T4 < T5, because T5 appended 4 after T4 appended 3 to 238.
- T5 < T6, because T6 observed T5's append of 4 to key 238.
- T6 < T7, because T7 observed T6's append of 3 to key 239.
- However, T7 < T1, because T1 appended 1 after T7 appended 6 to 238: a contradiction!
Let:
T1 = {:type :ok, :f :txn, :value [[:r 154 [1 2 3]] [:append 154 4] [:r 154 [1 2 3 4]] [:append 152 6]], :process 25, :time 179204093420, :index 2639}
T2 = {:type :ok, :f :txn, :value [[:append 154 5] [:append 155 2]], :process 19, :time 178853598775, :index 2622}
T3 = {:type :ok, :f :txn, :value [[:append 154 6]], :process 22, :time 179021417457, :index 2626}
Then:
- T1 < T2, because T1 did not observe T2's append of 3 to 154.
- T2 < T3, because T3 appended 6 after T2 appended 5 to 154.
- However, T3 < T1, because T1 appended 4 after T3 appended 6 to 154: a contradiction!
Let:
T1 = {:type :ok, :f :txn, :value [[:append 73 9] [:append 76 1] [:r 75 [2 3 1 4]] [:r 72 [1 2 4 3 6]]], :process 16, :time 150731478623, :index 1360}
T2 = {:type :ok, :f :txn, :value [[:append 75 7] [:r 73 [1 2 3 5 4]] [:r 73 [1 2 3 5 4]]], :process 13, :time 149852777683, :index 1312}
T3 = {:type :ok, :f :txn, :value [[:append 74 4]], :process 13, :time 150468396218, :index 1336}
T4 = {:type :ok, :f :txn, :value [[:r 76 [2 4 3]] [:r 74 [1 2 3 5 6 4]]], :process 13, :time 150544254238, :index 1346}
T5 = {:type :ok, :f :txn, :value [[:append 76 6]], :process 14, :time 150648519390, :index 1354}
Then:
- T1 < T2, because T1 did not observe T2's append of 4 to 75.
- T2 < T3, because T2 completed at index 1312, 0.000 seconds before the invocation of T3, at index 1313.
- T3 < T4, because T4 observed T3's append of 4 to key 74.
- T4 < T5, because T4 did not observe T5's append of 3 to 76.
- However, T5 < T1, because T1 appended 1 after T5 appended 6 to 76: a contradiction!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment